트립 (이진 탐색 트리) 편집하기

트립 이진 탐색 트리(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) 삽입'''
* 최초 노드이므로 루트

<syntaxhighlight lang="text">
(50, 0.8)
</syntaxhighlight>'''2단계: (30, 0.3) 삽입'''
* key 기준 왼쪽 자식에 위치  
* priority 0.3 < 0.8 → 힙 조건 위배 → 오른쪽 회전

<syntaxhighlight lang="text">
회전 전:
      (50, 0.8)
     /
(30, 0.3)

회전 후:
(30, 0.3)
         \
       (50, 0.8)
</syntaxhighlight>'''3단계: (70, 0.9) 삽입'''
* key 기준 오른쪽 → 오른쪽 자식의 오른쪽에 삽입됨  
* priority 0.9 > 0.8 → 회전 불필요

<syntaxhighlight lang="text">
(30, 0.3)
         \
       (50, 0.8)
               \
             (70, 0.9)
</syntaxhighlight>'''4단계: (20, 0.6) 삽입'''
* key 기준 왼쪽 자식 → priority 0.6 > 0.3 → 회전 없음

<syntaxhighlight lang="text">
         (30, 0.3)
        /         \
 (20, 0.6)      (50, 0.8)
                       \
                    (70, 0.9)
</syntaxhighlight>

=== 삭제 과정 ===
'''삭제할 노드: (30, 0.3)'''

# 삭제 대상은 루트 
# 자식 노드 중 priority가 더 낮은 쪽((20, 0.6))과 회전하여 root 자리에서 내려감 
# 다시 남은 자식((50, 0.8))과 회전 후 삭제
<syntaxhighlight lang="text">
초기 상태:
         (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)
</syntaxhighlight>

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

*'''삭제'''
**삭제할 노드를 찾은 뒤, 자식과 회전하며 리프 노드로 내리고 삭제
**회전은 힙 조건을 유지하도록 수행됨
==시간 복잡도==
*평균적으로 삽입, 삭제, 탐색 모두 O(log n)
*최악의 경우 O(n)일 수 있으나, priority가 무작위로 부여되므로 매우 드뭄
==예제 (Python)==
<syntaxhighlight lang="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)
</syntaxhighlight>
==장점==
*확률적 균형 트리로 삽입/삭제가 평균적으로 빠름
*구현이 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.
[[분류:수학]]
[[분류:알고리즘]]
[[분류:트리]]