Treap Split and Merge
Split and rejoin a search tree while its keys and heap priorities remain consistent.
Free theory articleSplit and rejoin a search tree while its keys and heap priorities remain consistent.
Concept & interpretation
A Treap (Tree + Heap) is a randomized binary search tree where each node has both a key and a priority. The keys obey the Binary Search Tree property, while the priorities obey the Heap property (typically a min-heap). This guarantees that the tree structure is identical to what would be formed if the nodes were inserted in order of their priorities.
Experimenting with Treap Dynamics
You can interactively explore the effects of different insertion sequences and split keys:
- Open the Treap Split and Merge module.
- Set the Keys control to "Seven" and the Priorities control to "Fixed".
- Adjust the Split key control to 3. Notice that the Left split size becomes 2 and the Right split size becomes 5.
- Change the Priorities control to "Tied". This simulates a degenerate case where all priorities are 1, causing ties to be broken by key value. Notice how the tree becomes completely unbalanced with a height of 7.