演算法/左旋轉

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 在每次插入時隨機旋轉樹時，總體而言，更多的樹插入將產生一棵平衡良好的樹，相比之下，從例如非遞減有序的鍵插入序列（看起來像一個連結串列）生成的普通二叉樹。