算法/左旋转

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

现在需要建立堆不变性，从最近插入的节点开始。

如果子节点到父节点之间存在指针，则

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

否则，进行插入后检查

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

注意：通过旋转移动，而不是像在普通二叉堆中那样交换父节点和节点。

         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 的优先级不如父节点（Sally）高，因此循环退出。

虽然这个例子看起来并不完全平衡，但当使用 Treap 在每次插入时随机旋转树时，总体而言，更多的树插入将产生一棵平衡良好的树，相比之下，从例如非递减有序的键插入序列（看起来像一个链表）生成的普通二叉树。