Tag Archives: AVL tree

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