called AVL trees after their Russian inventors Adelson-Velskii and Landis.

It can be proved that in AVL trees: Height < 1.5logN

So if we restrict ourselves to AVL trees the crucial operations of searching, inserting, and deleting are absolutely guaranteed to be O(logN) - providing that height-balance can be maintained in O(logN) time. It can!

In working with AVL trees, operations must preserve two properties:

- (height balanced) heights of left and right subtrees are within 1
- (BST) values in left subtree are smaller than root value, which is smaller than the values in the right subtree.

The INSERTION strategy is this:

- Add the new value in the tree where it belongs (normal BST
insertion).
- Check if all subtrees are still height-balanced. If they are
not, re-balance the tree by
*changing its shape*(i.e. moving around nodes or even whole subtrees).

Let's look at some simple examples. Suppose we start with the empty tree.

Insert 3:

Insert 6:

Insert 2:

So far things have been easy! Insert 1:

Insert 0:

The subtrees under `2' are not height balanced. Compute the balance at each node to see this. This is the deepest `unbalanced' node. Fix it.

When we have an imbalance, one of the subtrees is *tall* or
*long* the other subtree is *short*. To re-balance, we
need to shorten the *tall* side and/or lengthen the *short*
side. This can be done by what is called a *rotation*. In our
example, `1' rotates *up* into `2's position, `2' goes down on
the opposite side:

Now the left side is 1 shorter and the right side is 1 taller. This re-balanced subtree is joined back to its place in the main tree.

Continuing on, suppose we now insert -1.

Computing the balance at each node, we see that everything is balanced except the top node... so we rotate the

But what do we do with `1's

**Answer:** *it becomes the left subtree of the node
that rotated down.*

Rotation is the operation that is used to restore balance in an AVL
tree. For INSERTION, it can be shown that you never need to do more
than *two* rotations (one rotation is not always enough) to
restore balance, no matter how large the tree is. For DELETE, rotation
is also used to restore balance, but in this case there are
circumstances in which fixing the balance in one part of the tree
creates an imbalance higher up in the tree. So, in the worst case, you
might have to do O(height) rotations during a single DELETE operation.

That is all we have time to say about height-balanced binary search trees. The rotation operation itself is very fast and simple, and is an excellent illustration of the usefulness of the PRUNE and JOIN operations.