Monthly Archives: December 2014

AVL Tree

Data structures,

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 →

Binary search tree

Data structures, ,

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

 

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