Last modified on 30 November 2010, at 14:34

Algorithms/Left rotation


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 ).