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