Treap

Random BST

The height of a BST depends on the order that the values are inserted in. For example, inserting 1,2,3,4 would result in the worst height of O(h).

Say you randomly shuffle the sequence: 4,3,1,2. The resultign BST would have a height closer to the best cast of h=O(lgn), a balanced binary search tree.

Suppose we have a priori, all the keys that wouldb e inserted. We know that if the keys are sorted, the BST will degenerate into a linked list. However, it can be proven that a shuffle of the keys is sufficient to make the BST balanced.

Treap data structure is designed around this obersvation and attempts to create the effects of shuffling the keys as they are inserted (or removed).

Treap

Treap combines a binary search tree and binary heap.

• Each entry (key-value pair) is assigned a random priority.
• BST ordering property is based on keys.
• The priorities are used to create a min or max heap.

Insertion

• Generate a random priorirty for the entry (key-value pair).
• Insert the entry as you would in BST (based on the "key" and ignoring the priorities).
• If priorities (inserted node and its parent) aren noti n the desiredorder (based on max or min heap), roate the node up and the parent down (instead of swim up).
  • If the child node is to the left, then you must rotate right.
  • If the child node is to the right, then you must rotate left.
• Repeat the last step until all priorities are in the desired order.

Removal

• Find the target following a lookup in BST (on the keys).
• Change the ppriority of the entry to be removed o a value that results in the entry sinking. For example, if priorities are non-negative, set the target's priority to -1.
• Rotate down the target until it cannot sink any further and it becomes a leaf, then remove it.

After any sequence of insertions and removal, the height of the tree is, with high probability, proportionnal t the logarithm of the number of entries.

Treap Analyss

Operation costs:

• find is O(h) where h is the height of he tree. (look-up in BST over keys, ignoring priorities).
• insert is O(h) where at most O(h) to find where the key must be inserted and O(h) rotation to bring a newy inserted node to the root (to fix heap order)
• remove is O(h) where it takes at most O(h) to find the target and O(h) rotation to bring the target to level 0.

Height

• O(lgn) in best case
• O(n) in worst case -O(lgn) in average case.

Treap, where the priorities are independent and uniformly distributed continuous random vairables, have an expected depth of O(lgn). The expected running time for any core operations is O(lgn).

In contras to Treap, AVL guarantees O(lgn) height. However, ther eis sno need to track nodes' height or calculate baancefactors in a treap. Tehre are fewer rotation types, and the direction of rotations is easier to determine.

• Treaps have shown to have good performance and often outperforms AVL tree.