AVL trees are binary search trees in which the difference between the height of the left and right subtree is either -1, 0, or +1.
AVL trees are also called a self-balancing binary search tree. It is named after its inventors (AVL) Adelson, Velsky, and Landis.
Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the tree will be unbalanced and need to be balanced.
Balance Factor (k) = height (left(k)) - height (right(k))
If balance factor of any node is 1, it means that the left sub-tree is one level higher than the right sub-tree.
If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain equal height.
If balance factor of any node is -1, it means that the left sub-tree is one level lower than the right sub-tree.
An example of a balanced avl tree is:
No comments:
Post a Comment