무작위 이진 탐색 트리

무작위 BST(randomized binary search tree)는 명시적인 균형 조건 없이 무작위성을 활용하여 평균적으로 균형 잡힌 이진 탐색 트리를 구성하는 자료구조이다. Treap 외에도 다양한 구조가 있으며, 이들은 각기 다른 방식으로 무작위성을 도입하여 O(log n) 평균 시간복잡도를 유지한다.

1 주요 종류

• 트립
  • 노드에 무작위 우선순위를 부여하여 힙 + BST 구조 유지
  • 삽입, 삭제 연산은 회전을 통해 힙 속성을 보존하면서 이루어짐

• Randomized Binary Search Tree (RBST)
  • 새 노드를 루트로 삽입할 확률을 1 / (n + 1)로 설정
  • 루트로 삽입 시 기존 트리를 좌우로 분할(split), 새 노드 아래로 병합(join)
  • 단순하고 효율적인 구현으로 유명

• Skip List 기반 트리 (예: Skip Tree)
  • 여러 층의 연결 리스트로 구성된 구조를 트리처럼 응용
  • 탐색, 삽입, 삭제 시 각 노드의 높이를 무작위로 결정

• Scapegoat Tree (부분 무작위)
  • 노드 삽입 시 불균형이 감지될 때만 부분적으로 트리 재구성
  • 무작위는 직접 사용하지 않지만, 삽입 순서가 무작위일 때 성능이 안정적

• Treap 변형
  • Cartesian Tree: 배열을 기반으로 Treap과 유사한 트리 구성
  • Implicit Treap: 키 대신 배열 인덱스를 기반으로 Treap 구성

• Randomized Meldable Heap 기반 BST
  • 트리를 명시적인 구조 없이 포인터만으로 표현하며 병합(meld) 연산으로 유지
  • 병합 시 무작위 결정에 따라 왼쪽/오른쪽 서브트리를 선택

2 비교

구조	특징	삽입/삭제 복잡도	트리 높이 평균
Treap	우선순위 힙 + BST	O(log n)	O(log n)
RBST	루트 삽입 여부를 확률로 결정	O(log n)	O(log n)
Meldable Heap 기반 BST	병합 연산 중심 구조	O(log n)	O(log n)
Skip Tree	계층적 구조, 정렬된 리스트 기반	O(log n)	O(log n)

3 장점

• 명시적인 균형 유지 불필요 → 구현이 간단
• 평균적으로 성능이 안정적이며, 삽입/삭제/탐색 모두 O(log n)
• 랜덤 삽입이 보장될 경우 이론적으로 자가균형 트리와 유사한 성능

4 단점

• 최악의 경우 O(n) 시간복잡도 발생 가능
• 난수 생성 품질이 트리 성능에 영향을 미칠 수 있음
• 결정적이지 않아 디버깅이나 동기화가 어려울 수 있음

5 같이 보기

• 트립 (이진 탐색 트리)
• Randomized Binary Search Tree
• 이진 탐색 트리
• AVL 트리
• 레드-블랙 트리
• 확률적 알고리즘

6 참고 문헌

• Seidel, R., & Aragon, C. R. (1996). Randomized search trees. Algorithmica, 16(4), 464–497
• Blelloch, G. E., & Reid-Miller, M. (1998). Fast Set Operations Using Treaps. Workshop on Algorithms and Data Structures (WADS)
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press