개요Treap은 Tree와 Heap을 조합한 이름으로, 이진 탐색 트리(Binary Search Tree, BST)와 힙(Heap) 구조의 특성을 동시에 만족하는 확률적 자료구조입니다. 키에 대해 이진 탐색 트리 성질을, 우선순위에 대해 힙 성질을 유지함으로써 삽입, 삭제, 탐색 모두 평균적으로 O(log n) 시간 복잡도를 제공하며, 균형 잡힌 트리 구조를 확률적으로 유지할 수 있습니다.1. 개념 및 정의 항목 내용 정의각 노드가 키(Key)와 우선순위(Priority)를 가지며, 키는 BST, 우선순위는 힙 성질을 만족하는 이진 트리목적자가 균형(self-balancing) 유지로 빠른 탐색, 삽입, 삭제 지원필요성명시적 리밸런싱 없이 트리 높이 최적화를 달성하여 성능 향상Treap은 간단한 구조와..
