# AVL Tree

AVL tree is a self-balancing binary search tree, which was invented by soviet mathematicians Georgy Adelson-Velskii and Evgenii Landis’. To the basic rules of BST added a new property which states that heights of the two sub-trees differ by at most one. This property helps to avoid the worst case in which search, insert and delete operations has linear complexity in the binary search tree. As you can see on the diagram above the root node of the unbalanced three has left and right sub-tree. But, the right sub-tree is two levels deeper that the left sub tree.As result if want to lookup a node with key “6” we need 3 comparisons or if we need a node with key ”5″ then we need 4 comparisons. In a balanced tree: we need only one comparison to find node with key “6” and 3 comparisons to find node “5”. Not so bad right?

###### Balancing

Balanced means the height of tree is always O(log N). To maintain tree balanced we need to keep heights of the sub-trees at every node or we can keep difference which is sometimes named balance factor. Using heights we can rotate unbalanced nodes, just like that: Rotation is a operation which changes tree structure and basically, there are four possible cases of rotation:

Left rotation

A rotation performed at A to the left. As result B becomes root node.

Right rotation

This rotation performed at C to the right, so that the B becomes root node. Double right rotation

This is the case when we need two rotations instead of one and this operation sometimes called right-left rotation. Double left rotation

This rotation is a mirror operation of the double right rotation, another name for it is left-right rotation. ###### Implementation

AVL has the same basic operations as the binary search tree. The only difference is that we need to store heights and perform rotation if needed right after insertion, deletion or any other operation which modifies tree.

Java example based on BST:

###### Conclusion

AVL tree avoids worst case linear complexity for its operations, so it can be used in practice. For instance, you can use it to implement set or priority queue.

## 2 thoughts on “AVL Tree”

1. Benedict McNamara says:

You don’t actually need to store the heights of subtrees and in fact this is a bad idea. You simply need to store an enum stating LeftHigh, RightHigh or Balanced.

1. Volov Alexander says:

Hi Benedict, many thanks for your comment. I believe it’s not bad idea because pre calculated height allows you to lookup it at any time and without any traversals.