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. Continue reading AVL Tree →