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?
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:
A rotation performed at A to the left.
As result B becomes root node.
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.
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:
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.