무작위 우선순위 하나로 이진 탐색 트리의 최악을 없앤다
Treap (Cartesian Tree)
Treap은 이진 탐색 트리와 이진 힙을 결합한 자료구조로, 키는 BST 규칙을, 무작위 우선순위는 힙 규칙을 따르게 한다. 우선순위가 유일하면 트리 모양이 하나로 결정되므로, 무작위로 뽑기만 해도 평균적으로 균형 잡힌 트리가 보장된다. Split과 Merge 두 보조 연산만으로 삽입·삭제·탐색·합집합을 모두 O(log n)에 구현하는 방법을 코드와 함께 설명한다.
우선순위가 없다면 treap은 그저 일반적인 이진 탐색 트리일 뿐이고, 하나의 값 집합이 연결 리스트 같은 퇴화된 트리로 만들어질 수도 있어 매우 느려진다.