Treap Split and Merge

Worked Example: Splitting and Merging

Let's consider inserting the keys [4, 2, 6, 1, 3, 5, 7] with a fixed set of priorities: 1:40, 2:20, 3:50, 4:10, 5:35, 6:30, 7:60.

First, the node with key 4 and priority 10 becomes the root, as it has the minimum priority. The tree continues to build based on BST insertion followed by rotations to restore the heap property. The resulting tree structure will have 4 at the root (priority 10), 2 on the left (priority 20) and 6 on the right (priority 30).

If we split this tree around key `k = 4`:

1. All nodes with keys < 4 (which are 1, 2, and 3) form the Left Tree. Size = 3.
2. All nodes with keys ≥ 4 (which are 4, 5, 6, and 7) form the Right Tree. Size = 4.

When merging the two trees back together, the root of the Right Tree (key 4, priority 10) has a smaller priority than the root of the Left Tree (key 2, priority 20). Thus, node 4 becomes the root, and we recursively merge the Left Tree with node 4's left subtree. The final restored tree contains all 7 keys.

Experimenting with Treap Dynamics

You can interactively explore the effects of different insertion sequences and split keys:

1. Open the Treap Split and Merge module.
2. Set the Keys control to "Seven" and the Priorities control to "Fixed".
3. Adjust the Split key control to 3. Notice that the Left split size becomes 2 and the Right split size becomes 5.
4. 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.

Limitations

The true power of a Treap comes from assigning random priorities, which gives an expected height of O(log n). In this module, we use fixed, deterministic priorities to create repeatable examples and demonstrate specific structures. Therefore, the "Fixed" and "Tied" priority modes do not imply that a Treap is always balanced in the worst case; they illustrate how specific priority assignments dictate the exact structure of the tree. If all priorities are equal (as in the "Tied" case), the Treap degenerates into a Linked List when keys are inserted in order.

References

The implementation and conceptual properties of the Treap structure in this module are based on the standard randomized binary search tree definitions found in fundamental computer science literature.

• Open Data Structures.Chapter 7: Random Binary Search Trees. Describes the Treap data structure, its properties, and the expected bounds when priorities are randomly generated.