Treap

Treap

트리(Tree)와 힙(Heap)의 성질을 동시에 만족하는 자료구조로, 각 노드가 키(key)와 우선순위(priority)를 가지며 키는 BST 속성, 우선순위는 힙 속성을 따르는 랜덤화된 균형 이진 탐색 트리

목적: 간단한 균형 트리, 랜덤화로 균형 유지, 분할/병합 효율

특징: BST + 힙, 랜덤 우선순위, 회전 기반, 기대 O(log n), 구현 단순

구성요소: 키(key - BST 순서), 우선순위(priority - 힙 순서, 랜덤 생성), 회전 연산

동작: 삽입 시 BST처럼 삽입 → 우선순위 위반 시 회전으로 힙 복구 / 삭제 시 회전으로 리프까지 내림 → 제거

회전: 우선순위 높은 부모가 위로 오도록 좌/우 회전 → 힙 속성 유지

시간 복잡도: 기대(Expected) O(log n), 최악 O(n) - 우선순위 불운 시

공간 복잡도: O(n)

장점: 구현 간단(AVL/Red-Black보다), 분할/병합 O(log n), 랜덤화로 균형, 암묵적 키 지원

단점: 최악 O(n), 우선순위 랜덤 필요, AVL보다 느린 검색

적용사례: 분할/병합 빈번한 연산, 암묵적 키 집합, 교육용 균형 트리

비교: Treap(랜덤/단순) vs AVL(결정적/빠름) vs Skip List(확률적/다층)

연관: BST, 힙, 회전, 랜덤화, 분할/병합