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.

avl_2

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:

avl_perfect

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:

avl_rotation

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.

avl_left_rotation

 

As result B becomes root node.

Right rotation

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

avl_right_rotation

Double right rotation

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

avl_dbl_left_rotation

Double left rotation

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

avl_dbl_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:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/AVLTree.java

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

Leave a Reply