|
|
| 1번째 줄: |
1번째 줄: |
| 트립 이진 탐색 트리(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.
| |
| [[분류:수학]]
| |
| [[분류:알고리즘]]
| |
| [[분류:트리]]
| |
