Treap data structure
A treap is a binary search tree in which each node has both a key and a priority: nodes are
ordered in an inorder fashion by their keys and are
heap-ordered by their priorities.
To implement randomized binary search trees, random priorities are assigned to each node
when an insertion is performed. Insertion uses the standard algorithm for inserting the new
node as a leaf, and then restores heap ordering by "bubbling up" the node through a sequence
of rotations. Deletion reverses this procedure by first "bubbling down" the node until it is a
leaf, and then pruning it off the tree. One can show that the expected depth of any node in this
tree is about ln n, and the expected number of rotations per insertion or deletion is about 2.
-
-
-
Brief description of data structure
-
-
Randomized Binary Search Trees
-
Kym Horsell /
Kym@KymHorsell.COM
ADVISORY:
Email to these sites is filtered. Unsolicited email may
be automajically re-directed to the relevant postmaster.