Cartesian Tree (카르테시안 트리)

Cartesian Tree (카르테시안 트리)

배열의 힙 속성(부모가 자식보다 작음)과 BST 속성(인덱스 기준 정렬)을 동시에 만족하는 이진 트리로, O(n) 시간에 구축하며 RMQ 문제 해결에 활용

목적: Range Minimum Query(RMQ), 힙+BST 결합, 구간 최솟값 쿼리

특징: 유일한 구조, 힙 속성, BST 속성(인덱스), O(n) 구축

속성

• •힙 속성: 부모 노드 값 <= 자식 노드 값 (Min-Heap 기준)
• •BST 속성: 왼쪽 서브트리는 원본 배열에서 왼쪽, 오른쪽 서브트리는 오른쪽
• •유일성: 모든 원소가 다르면 유일한 Cartesian Tree 존재

구축 알고리즘 (O(n))

RMQ 활용: 구간 [i,j]의 최솟값 = LCA(i, j)의 값

RMQ ↔ LCA 변환: Cartesian Tree를 통해 RMQ를 LCA로 변환, O(n)-O(1) 가능

Treap 관계: Cartesian Tree에서 우선순위가 랜덤이면 Treap

장점: O(n) 구축, RMQ 문제 해결, 이론적 도구

단점: 동적 갱신 어려움, 실용적으로 Sparse Table이 더 간단

적용사례: RMQ 문제, 후위 순회 복원, 알고리즘 경시대회

비교: Cartesian Tree(구축O(n)) vs Sparse Table(전처리O(n log n)/쿼리O(1)) vs Segment Tree(전처리O(n)/쿼리O(log n))

연관: RMQ, LCA, Treap, 힙, BST