ITPE * JackerLab

개요Link-Cut Tree는 동적으로 연결되거나 분리되는 트리 구조에서 효율적으로 경로 질의 및 갱신 연산을 수행할 수 있도록 설계된 고급 트리 기반 자료구조입니다. Sleator와 Tarjan에 의해 1983년 제안된 이 자료구조는 splay tree를 기반으로 하며, 각 노드의 서브트리나 루트까지의 경로에 대해 로그 시간 내 연산을 지원합니다. Union-Find, Euler Tour Tree보다 더 복잡한 트리 동작이 필요한 알고리즘에 적합합니다.1. 개념 및 정의 항목 설명 정의Link-Cut Tree는 포레스트(트리들의 집합) 구조에 대해 노드 간 연결(Link), 분리(Cut), 경로 질의(Query), 경로 갱신(Update)을 동적으로 처리하는 트리 자료구조입니다.목적트리 구조가 변동하..

개요Cartesian Tree는 주어진 수열을 기반으로 구성되는 이진 탐색 트리 구조로, 배열의 순서와 값의 최소(또는 최대) 조건을 동시에 만족하는 이진 트리다. 이는 RMQ(Range Minimum Query), LCA(Lowest Common Ancestor) 등 다양한 알고리즘 문제의 전처리 단계에서 유용하게 사용된다.1. 개념 및 정의Cartesian Tree는 다음 두 가지 성질을 모두 만족하는 트리다:이진 탐색 트리(Binary Search Tree): 노드의 중위 순회가 원래 수열과 일치해야 함힙 속성(Min-Heap 또는 Max-Heap): 부모 노드의 값이 자식보다 작거나 커야 함목적: 값 기반 정렬과 순서 기반 조회를 동시에 처리필요성: RMQ와 같은 문제에서 빠른 질의 처리를 위한 ..