트립 (이진 탐색 트리)

트립 이진 탐색 트리(Treap Binary Search Tree)는 이진 탐색 트리(BST)의 정렬 규칙과 힙(Heap)의 우선순위 규칙을 동시에 만족하는 확률적 자료구조이다. 삽입 시 각 노드에 난수 형태의 우선순위를 부여함으로써, 별도의 재균형 알고리즘 없이도 평균적으로 균형 잡힌 트리를 구성할 수 있다.

개요

트립은 '트리(Tree)'와 '힙(Heap)'의 합성어로, 각 노드에 키(key)와 우선순위(priority)를 부여하여,

• 키에 대해서는 이진 탐색 트리(BST, Binary Search Tree)의 조건을,
• 우선순위에 대해서는 힙(Heap)의 조건을 만족시킨다.

특히 우선순위가 무작위로 주어지는 경우, 평균적인 연산 성능이 우수하다.

구조

트립의 각 노드는 다음 두 가지 값을 가진다:

• 키(key): BST의 규칙(왼쪽 < 루트 < 오른쪽)을 따름
• 우선순위(priority): 최대 힙(max-heap) 조건을 따름. 부모의 우선순위 ≥ 자식의 우선순위

연산

• 삽입
  • key를 기준으로 BST 규칙에 따라 트리에 삽입
  • 삽입 후 priority가 부모보다 작으면 회전(rotations)을 통해 힙 성질을 만족시킴

• 삭제
  • 삭제할 노드를 찾은 뒤, 자식과 회전하며 리프 노드로 내리고 삭제
  • 회전은 힙 조건을 유지하도록 수행됨

시간 복잡도

• 평균적으로 삽입, 삭제, 탐색 모두 O(log n)
• 최악의 경우 O(n)일 수 있으나, priority가 무작위로 부여되므로 매우 드뭄

기대 비용 분석

• 키 검색(Search)
  • 임의의 키 k에 대한 검색 비용은 루트에서 k까지의 경로 길이(d_k)
  • 우선순위 순열 σ가 균등하게 무작위일 때, 기대 깊이 E[d_k] = H_k + H_n−k+1 − 1***여기서 H_m = 1 + 1/2 + … + 1/m 은 조화급수(harmonic number)
  • 키 k를 균등하게 선택할 경우 전체 기대 깊이:
    • E[d] = (1/n) ∑_k=1ⁿ (H_k + H_n−k+1 − 1) = 2(H_n − 1) = O(log n)

• 삽입/삭제 시 회전 횟수
  • 삽입 시 TREAPIFY 과정에서 발생하는 회전 횟수를 X라 할 때, E[X] ≤ 2 (Corollary 41)
    • Over-treap에 의한 부모 방향 회전: 기대 1회
    • Under-treap에 의한 자식 방향 회전: 기대 1회
  • 삭제 역시 동일하게 기대 회전 횟수 ≤ 2*결론**모든 기본 연산의 평균 시간 복잡도는 O(log n)

시뮬레이션 예시

이 시뮬레이션은 삽입 시 BST 속성을 유지하면서, 우선순위에 따라 회전을 통해 힙 속성도 유지하는 트립의 동작 원리를 보여준다.

• 초기 삽입 리스트 (키, 우선순위): (A, 3), (C, 8), (F, 6), (B, 9), (E, 5), (D, 7)

트립이 형성되는 과정 (각 삽입 후 TREAPIFY 수행):

1단계: 삽입 (A,3)

트리:

(A,3)

2단계: 삽입 (C,8)

• C는 A보다 크므로 오른쪽에 삽입

삽입 직후:
(A,3)
   \
   (C,8)

• 우선순위 8 > 3 → 회전하여 C가 루트가 됨

트리:

 (C,8)
  /
(A,3)

3단계: 삽입 (F,6)

• F는 C보다 크므로 오른쪽에 삽입
• 우선순위 6 < 8 → 힙 조건 만족, 회전 없음

트리:

   (C,8)
  /     \
(A,3) (F,6)

4단계: 삽입 (B,9)

• B는 C보다 작고 A보다 큼 → A의 오른쪽에 삽입

삽입 직후:

     (C,8)
   /       \
(A,3)     (F,6)
   \
   (B,9)

• 우선순위 9 > 3 → 회전하여 B가 A 위로

TREAPIFY 1단계 (B의 우선순위 9 > A → 좌회전 at A):

    (C,8)
   /     \
 (B,9) (F,6)
 /
(A,3)

• B의 우선순위 9 > C → 다시 회전하여 B가 루트

트리:

    (B,9)
   /     \
(A,3)   (C,8)
           \
           (F,6)

5단계: 삽입 (E,5)

• E는 B < C < F → F의 왼쪽에 삽입

트리:

    (B,9)
   /     \
 (A,3) (C,8)
           \
          (F,6)
           /
        (E,5)

• 우선순위 5 < 6 → 힙 조건 만족, 회전 없음

6단계: 삽입 (D,7)

• D는 B < C < F > E → E의 왼쪽에 삽입

삽입 직후:

  (B,9)
 /     \
(A,3) (C,8)
           \
          (F,6)
         /
      (E,5)
     /
  (D,7)

• TREAPIFY 1단계 (D의 우선순위 7 > E → 우회전 at E):

  (B,9)
 /     \
(A,3) (C,8)
           \
          (F,6)
         /
      (D,7)
           \
          (E,5)

• TREAPIFY 2단계 (D의 우선순위 7 > F → 우회전 at F):

최종 트리:

  (B,9)
 /     \
(A,3)  (C,8)
           \
          (D,7)
              \
             (F,6)
              /
          (E,5)

예제 (Python)

import random

class TreapNode:
    def __init__(self, key):
        self.key = key
        self.priority = random.random()
        self.left = None
        self.right = None

def rotate_left(root):
    new_root = root.right
    root.right = new_root.left
    new_root.left = root
    return new_root

def rotate_right(root):
    new_root = root.left
    root.left = new_root.right
    new_root.right = root
    return new_root

def insert(root, key):
    if root is None:
        return TreapNode(key)
    if key < root.key:
        root.left = insert(root.left, key)
        if root.left.priority < root.priority:
            root = rotate_right(root)
    else:
        root.right = insert(root.right, key)
        if root.right.priority < root.priority:
            root = rotate_left(root)
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(f"({root.key}, {round(root.priority, 2)})", end=" ")
        inorder(root.right)

# 예제 실행
root = None
for k in [50, 30, 70, 20, 60]:
    root = insert(root, k)

inorder(root)

장점

• 확률적 균형 트리로 삽입/삭제가 평균적으로 빠름
• 구현이 AVL, 레드-블랙 트리에 비해 단순함
• 정렬과 힙 구조를 동시에 만족하므로 다양한 연산에 효율적

단점

• 최악의 경우 불균형 발생 가능
• 난수 기반 구조이므로 실행마다 결과 트리가 달라질 수 있음
• 재현성과 결정성이 중요한 환경에는 부적합

같이 보기

• 이진 탐색 트리
• 힙
• AVL 트리
• 레드-블랙 트리
• 무작위화 알고리즘

참고 문헌

• Seidel, R., & Aragon, C. R. (1996). Randomized Search Trees. Algorithmica, 16(4–5), 464–497.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.