Algorithms/Left rotation
Jump to navigation
Jump to search
 |
A reader requests that the formatting and layout of this book be improved. Good formatting makes a book easier to read and more interesting for readers. See Editing Wikitext for ideas, and WB:FB for examples of good books. Please continue to edit this book and improve formatting, even after this message has been removed. See the discussion page for current progress. |
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 ).