트립 이진 탐색 트리

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

개요

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

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

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

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

예시 (직관적 설명)

다음과 같은 (key, priority) 쌍을 순서대로 삽입한다고 가정하자.

• (50, 0.8)
• (30, 0.3)
• (70, 0.9)
• (20, 0.6)

과정

1. 첫 번째로 (50, 0.8)은 루트가 된다.
2. (30, 0.3)은 key 기준으로 왼쪽에 삽입되고, priority가 0.3으로 더 작으므로 오른쪽 회전이 발생해 (30, 0.3)이 루트로 올라간다.
3. (70, 0.9)는 key 기준으로 오른쪽에 붙고, priority가 더 크기 때문에 회전은 발생하지 않는다.
4. (20, 0.6)은 (30, 0.3)의 왼쪽에 붙는다. priority는 부모보다 크므로 회전은 없다.

이와 같은 방식으로 삽입할 때마다 BST 조건을 먼저 만족시키고, priority 위배 시 회전을 통해 힙 조건을 보장한다.

연산

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

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

시간 복잡도

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

예제 (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.