한양과기고 에듀테크 수업도구 대시보드

회전 규칙 대신 "동전 던지기"로 균형을 잡는 트리

일반 이진 탐색 트리는 1, 2, 3, 4, 5…처럼 정렬된 값을 순서대로 넣으면 오른쪽으로만 길게 뻗어 사실상 연결 리스트가 되고 검색이 O(n)까지 느려진다. AVL 트리와 레드-블랙 트리는 삽입·삭제마다 엄격한 회전 규칙을 검사해서 이걸 막았다. 트립(Treap)은 전혀 다르게 접근한다 — 규칙 대신 무작위성(randomness)을 이용해 "어차피 무작위 순서로 삽입된 BST는 대개 낮다"는 확률적 사실에 균형을 맡긴다.

1 핵심 아이디어 — key는 BST, priority는 힙

key

사용자가 넣는 실제 값. 보통의 BST 규칙 그대로 왼쪽 < 나 < 오른쪽을 지킨다.

priority

삽입할 때마다 무작위로 뽑는 값. 부모의 priority가 항상 자식보다 작아야 하는 min-heap 규칙을 지킨다.

왜 무작위인가

priority 기준으로 힙을 만드는 것은 수학적으로 "무작위 순서로 삽입한 BST"를 만드는 것과 동치다. 순서를 내가 정하지 못하게 만드는 셈이다.

기대 높이

무작위 순서로 삽입된 BST의 기대 높이는 O(log n)이다(직관: 특정 값이 계속 최악의 순서로만 들어올 확률은 n이 커질수록 지수적으로 희박해진다).

2 삽입 시뮬레이터 — priority를 뽑고, 힙 규칙 위반이면 회전으로 끌어올린다

트리가 비어 있다. 숫자를 넣으면 무작위 priority가 자동으로 붙는다.

노드 수: 0 트리 높이: 0 완전 균형 시 최소 높이: 0 누적 회전 횟수: 0

💡 각 노드 아래 노란 숫자가 priority다(작을수록 힙에서 위쪽 — 즉 루트에 가깝다). 새 노드는 먼저 BST 규칙대로 리프에 삽입된 뒤, priority가 부모보다 작으면 회전(rotate)으로 한 칸씩 위로 끌어올려진다 — 파란 테두리가 이동 중인 노드, 주황 테두리가 회전의 중심(부모)이다.

# 삽입: BST 자리를 찾아 내려간 뒤, 올라오면서 힙 규칙을 검사·회전한다 def insert(node, key, priority): if node is None: return Node(key, priority) if key < node.key: node.left = insert(node.left, key, priority) if node.left.priority < node.priority: # 힙 규칙 위반 node = rotate_right(node) elif key > node.key: node.right = insert(node.right, key, priority) if node.right.priority < node.priority: node = rotate_left(node) return node

3 삭제 — priority를 "무한대"로 보고 리프까지 밀어낸다

트립 삭제는 신기할 만큼 간단하다. 지울 노드의 priority가 무한대라고 가정하면 힙 규칙상 그 노드는 자식들보다 아래로 내려가야 한다. 그래서 priority가 더 작은 자식 쪽으로 계속 회전(rotate down)시키다 보면 어느 순간 리프가 되고, 그때 그냥 잘라내면 끝이다. BST 순서는 회전 내내 그대로 유지된다. 위 시뮬레이터의 삭제 버튼으로 직접 확인해 보자.

# 삭제: 자식 중 priority가 작은 쪽으로 계속 rotate해서 리프까지 내린 뒤 잘라낸다 def delete(node, key): if node is None: return None if key < node.key: node.left = delete(node.left, key) elif key > node.key: node.right = delete(node.right, key) else: if node.left is None: return node.right if node.right is None: return node.left if node.left.priority < node.right.priority: node = rotate_right(node); node.right = delete(node.right, key) else: node = rotate_left(node); node.left = delete(node.left, key) return node

4 AVL · 레드-블랙 · 스플레이 · 트립 비교

	AVL 트리	레드-블랙 트리	스플레이 트리	트립
구현 난이도	중간 — 회전 4케이스(LL/RR/LR/RL)	높음 — 색 규칙 + 회전·재색칠 케이스	중간 — zig / zig-zig / zig-zag	가장 낮음 — 회전 2개 + priority 비교뿐
삽입·삭제 코드 길이	보통	가장 김 (케이스 분기 多)	보통	가장 짧음
성능 보장	항상 O(log n), 상수 가장 작음 (≈1.44 log₂n)	항상 O(log n), 상수 조금 큼 (≈2 log₂n)	분할상환 O(log n), 단일 연산은 최악 O(n) 가능	기댓값 O(log n) — 확률적 보장, 이론상 최악 O(n) 가능(확률은 매우 낮음)
삭제 용이성	복잡 — 삭제 후 루트까지 올라가며 재검사	가장 복잡 — 케이스가 가장 많음	비교적 쉬움 — 찾아서 splay 후 서브트리 join	가장 쉬움 — priority=∞로 보고 내리기만 하면 끝
대표 활용	DB 인덱스, 읽기 위주 자료구조	C++ `std::map`, Java `TreeMap`, 리눅스 커널	캐시, 최근 접근 위주 워크로드	경쟁 프로그래밍, 빠르게 구현해야 하는 균형 트리

요약하면 트립은 코드가 제일 짧고 이해하기 쉬운 대신, 성능이 "항상"이 아니라 "기댓값"으로만 보장된다는 트레이드오프를 갖는다. 실전에서 priority를 진짜 난수로 뽑는 한, 최악의 경우가 실제로 나올 확률은 사실상 무시해도 될 만큼 작다.

5 관련 페이지

AVL 트리 레드-블랙 트리 스플레이 트리

한 줄 정리 — 트립은 노드마다 무작위 priority를 힙 규칙으로 유지시켜, "정렬 규칙(회전 조건)"이 아니라 "무작위 순서로 삽입된 BST는 기대 높이가 O(log n)"이라는 확률적 사실로 균형을 잡는다. 그 덕에 삽입·삭제 코드는 가장 짧지만, 보장은 항상이 아니라 기댓값이다.