Cartesian Tree

개요

Cartesian Tree는 주어진 수열을 기반으로 구성되는 이진 탐색 트리 구조로, 배열의 순서와 값의 최소(또는 최대) 조건을 동시에 만족하는 이진 트리다. 이는 RMQ(Range Minimum Query), LCA(Lowest Common Ancestor) 등 다양한 알고리즘 문제의 전처리 단계에서 유용하게 사용된다.

---

1. 개념 및 정의

Cartesian Tree는 다음 두 가지 성질을 모두 만족하는 트리다:

1. 이진 탐색 트리(Binary Search Tree): 노드의 중위 순회가 원래 수열과 일치해야 함
2. 힙 속성(Min-Heap 또는 Max-Heap): 부모 노드의 값이 자식보다 작거나 커야 함

• 목적: 값 기반 정렬과 순서 기반 조회를 동시에 처리
• 필요성: RMQ와 같은 문제에서 빠른 질의 처리를 위한 선형 전처리 필요

---

2. 특징

특징	설명	관련 구조와 비교
선형 시간 구성	배열을 한 번 순회하며 트리 구성 가능	일반 BST는 평균 O(n log n)
힙 + 순서 동시 보장	Min-Heap + 중위순회 = 원래 배열	Heap, BST 각각은 하나의 성질만 만족
RMQ 및 LCA 전처리 효율	최소값 쿼리 전처리에 활용	Segment Tree보다 빠름 (O(n) 구성)

Cartesian Tree는 정렬 기반 알고리즘을 트리 구조로 표현하는 데 강점을 가진다.

---

3. 구성 요소

구성 요소	설명	예시
노드(Node)	배열의 각 원소에 해당하는 트리의 노드	A = [3, 1, 4, 0, 2] → 각 값이 노드
왼쪽/오른쪽 서브트리	최소값 기준 분할 → 좌/우 하위 수열	0 기준 왼쪽: [3,1,4], 오른쪽: [2]
부모-자식 관계	부모는 해당 구간의 최소값 위치	구간 최소값이 루트로 설정됨

배열에서 최소값을 찾고 좌우를 분할하는 방식으로 트리를 재귀적으로 구성한다.

---

4. 기술 요소

기술 요소	설명	활용 방식
스택 기반 선형 구축	O(n) 시간에 트리 생성	오른쪽으로 확장하며 스택 조작
RMQ → Cartesian Tree → LCA	쿼리 전처리 최적화 순서	배열 → 트리 → 쿼리 적용
중위순회 → 원 배열 재구성	원본 배열 추출 가능	힙 구조에서는 불가능한 기능

특히 RMQ의 O(1) 질의 처리를 위한 Sparse Table 등의 보조 자료구조와 함께 사용된다.

---

5. 장점 및 이점

장점	설명	기대 효과
효율적인 전처리	RMQ/LCA 문제에서 빠른 초기화	복잡도 O(n), 쿼리 O(1) 가능
간결한 논리 구조	구현이 간단하고 직관적	수열 정렬과 연결된 트리 구성 학습 효과
힙 + 순서 동시 지원	다양한 알고리즘 문제에 유연하게 사용	Tree + Array 융합형 구조로 응용성 큼

Cartesian Tree는 최소값 기반 분할 정복 문제 해결의 핵심 기반 구조다.

---

6. 주요 활용 사례 및 고려사항

사례	설명	고려사항
RMQ (Range Minimum Query)	구간 최소값을 빠르게 찾는 문제	쿼리 최적화를 위한 Euler Tour 연계 필요
LCA (Lowest Common Ancestor)	트리에서 두 노드의 공통 조상 찾기	깊이 기반 배열과 동기화 필요
압축된 트리 시각화	대규모 수열에서 구조적 핵심 파악	시각화 도구/라이브러리 필요

적용 시 스택 사용 방식, 분할 기준 설정, 최소/최대 트리 선택 등이 중요하다.

---

7. 결론

Cartesian Tree는 수열 기반 문제를 트리로 전환하여, 정렬 정보와 값 정보 모두를 활용할 수 있는 유연한 구조이다. 특히 RMQ, LCA와 같이 알고리즘 대회나 시스템 내부 최적화에 자주 등장하는 문제에서 효과적으로 활용될 수 있으며, 트리와 배열의 융합적 사고를 요구하는 훌륭한 알고리즘 학습 도구이기도 하다.