트립 (이진 탐색 트리)

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

1 개요

트립(Treap)은 Tree와 Heap의 합성어로, 각 노드가 다음 두 가지 속성을 가진다.

• key: 이진 탐색 트리에서의 정렬 기준 키
• priority: 힙에서의 우선순위 키 (보통 난수로 부여)

트립은 다음 두 가지 조건을 동시에 만족한다.

• 이진 탐색 트리(BST) 조건: 왼쪽 서브트리의 key는 현재 노드보다 작고, 오른쪽은 크다.
• 힙(Heap) 조건: 각 노드의 priority는 자식 노드들보다 작다 (최소 힙 기준).

2 예시

2.1 삽입 과정

다음은 (key, priority) 쌍을 순서대로 삽입하는 예제이다.

삽입 순서: (50, 0.8) → (30, 0.3) → (70, 0.9) → (20, 0.6)

1단계: (50, 0.8) 삽입

• 최초 노드이므로 루트

(50, 0.8)

2단계: (30, 0.3) 삽입

• key 기준 왼쪽 자식에 위치
• priority 0.3 < 0.8 → 힙 조건 위배 → 오른쪽 회전

회전 전:
      (50, 0.8)
     /
(30, 0.3)

회전 후:
(30, 0.3)
         \
       (50, 0.8)

3단계: (70, 0.9) 삽입

• key 기준 오른쪽 → 오른쪽 자식의 오른쪽에 삽입됨
• priority 0.9 > 0.8 → 회전 불필요

(30, 0.3)
         \
       (50, 0.8)
               \
             (70, 0.9)

4단계: (20, 0.6) 삽입

• key 기준 왼쪽 자식 → priority 0.6 > 0.3 → 회전 없음

         (30, 0.3)
        /         \
 (20, 0.6)      (50, 0.8)
                       \
                    (70, 0.9)

2.2 삭제 과정

삭제할 노드: (30, 0.3)

1. 삭제 대상은 루트
2. 자식 노드 중 priority가 더 낮은 쪽((20, 0.6))과 회전하여 root 자리에서 내려감
3. 다시 남은 자식((50, 0.8))과 회전 후 삭제

초기 상태:
         (30, 0.3)
        /         \
 (20, 0.6)      (50, 0.8)
                       \
                    (70, 0.9)

1차 회전 (오른쪽 회전):
         (20, 0.6)
               \
             (30, 0.3)
                      \
                   (50, 0.8)
                           \
                         (70, 0.9)

2차 회전 (왼쪽 회전):
         (20, 0.6)
               \
             (50, 0.8)
            /
     (30, 0.3)
               \
             (70, 0.9)

삭제 후 (30 제거):
         (20, 0.6)
               \
             (50, 0.8)
                     \
                   (70, 0.9)

3 연산

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

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

4 시간 복잡도

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

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)

6 장점

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

7 단점

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

8 같이 보기

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

9 참고 문헌

• 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.