Treap Example: enforce the invariants: Binary Heap : Priority Parent > Priory Children Binary Tree : Left child < node < right child Operation * : rotation ( left ) for a Node to be left rotated ( marked * in example below) caller code: ... Node = rotate_left(Node) ... function rotate_left(Node): tmp = Node->right Node->right = tmp ->left tmp -> left = Node Node = tmp return Node Example: Initially, this is a valid binary tree, but not a valid binary heap. Insert Xenophon(Priority=56) into tree with root Sally(Priority=66) Sally | 66 / \ Harry| 33 Ted | 44 / \ Victor | 33 \ William | 22 ---------------------------------- Step 1: do a usual binary tree insert into a empty leaf. Sally | 66 / \ Harry| 33 Ted | 44 / \ Victor | 33 \ William | 22 \ Xenophon | 56 (a)/ In-order traversal : visit left tree, visit node, visit right subtree H S T V W X
Now the heap invariant has to be established, starting with the recently inserted node.
If there is a pointer between child node to parent, then
while parent priority < node priority: if right child of parent, do left rotate at parent else /* left child of parent */ do right rotate at parent
Otherwise, a post insertion check is done
treap_insert( node, current): if (current = null) return node if ( node.key < current.key) current.left = treap_insert( node, current.left) else current.right = treap_insert( node, current.right) if current.left != null and current.left.priority > current.priority and ( current.right == null or current.right.priority < current.left.priority ) then current = right_rotate(current) else if current.right != null and current.right.priority > current.priority current = left_rotate(current) return current
NB move by rotating , instead of exchanging parent and node, as in normal binary heap.
Sally | 66 / \ Harry| 33 Ted | 44 / \ Victor | 33 \ Xenophon | 56 / William | 22 \ (a) William is parent and is left rotated with Xenonphon. Xenophon was Williams right child, now becomes parent and William is left child, whereas Xenophon's left child (a) is now William's right child (a). In-order traversal H S T V W X
Sally | 66 / \ Harry|33 Ted | 44 / \ Xenophon | 56 / Victor | 33 \ William | 22 \ (a) Victor is left rotated with Xenophon In-order traversal is still H S T V W X
Sally | 66 / \ Harry| 33 Xenophon | 56 / / Ted | 44 \ Victor | 33 \ William | 22 Ted is left rotated with Xenophon, Victor , X's left child becomes T's right child, which was formerly X, and T becomes X's new left child. In-order traversal H S T V W X
Xenophon does not have greater priority than parent (Sally) so while loop exits.
Although this example doesn't look perfectly balanced, when a treap is used to randomly rotate the tree at each insertion, overall, the greater number of trees inserts will produce a well-balanced tree, as compared to a normal binary tree produced from say a non-decreasing ordered sequence of key inserts ( which looks like a linked list ).Last modified on 30 November 2010, at 14:34