Monthly Archives: December 2014

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

Binary search tree

Binary search tree or BST is a family of tree-based data structures, with maximum of two children and which follow to the general restriction that any node in a tree is larger than all nodes in it’s left sub-tree and smaller than all nodes in it’s right sub-tree.



BST doesn’t support duplicates, thus it can be used to construct sets or associative arrays. Continue reading Binary search tree