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

트립 이진 탐색 트리(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<sub>k</sub>)
**우선순위 순열 σ가 균등하게 무작위일 때, 기대 깊이 E[d<sub>k</sub>] = H<sub>k</sub> + H<sub>n−k+1</sub> − 1***여기서 H<sub>m</sub> = 1 + 1/2 + … + 1/m 은 조화급수(harmonic number)
**키 k를 균등하게 선택할 경우 전체 기대 깊이:
***E[d] = (1/n) ∑<sub>k=1</sub><sup>n</sup> (H<sub>k</sub> + H<sub>n−k+1</sub> − 1) = 2(H<sub>n</sub> − 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)==
<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.
[[분류:수학]]
[[분류:알고리즘]]
[[분류:트리]]