Treap
-
[ Open Data Structures ] - Treap - 2DataStructure 2021. 1. 14. 11:09
전에 언급했던 것처럼 Random Binary Search Tree는 Unbalanced하며 Add/Remove 등의 Operation의 수행이 힘들다는 치명적인 단점(Tree가 한쪽으로 치우친다는 단점)이 있어서 Dynamic한 활용이 어렵다고 했습니다. 게다가 Sorted Set을 위한 Interface의 지원이 불가능합니다. 이를 해결하기 위한 다양한 방법 중에는 가장 쉽고 적용이 빠른 Treap이 있습니다. 기존의 Random Binary Search Tree(이하 RBST)의 각 Node는 Left/Right Subtree를 위한 Data값(혹은 Search Key)를 가지고 있었습니다. Treap을 위한 Treap node는 여기에 추가적으로 Prioriy를 나타내는 임의의 integer/fl..