AVL Trees -Data Structures

AVL Trees

For ideal searching in a binary search tree, the heights of the left and right sub-trees of any node should be equal. But, due to random insertions and deletions performed on a binary search tree, it often turns out to be far from ideal. A close approximation to an ideal binary search tree is achievable if it can be ensured that the difference between the heights of the left and the right sub trees of any node in the tree is at most one. A binary search tree in which the difference of heights of the right and left sub-trees of any node is less than or equal to one is known as an AVL tree. AVL tree is also called as Balanced Tree. The name "AVL Tree" is derived from the names of its inventors who are Adelson-Veilskii and Landi. A node in an AVL tree have a new field to store the "balance factor" of a node which denotes the difference of height between the left and the right sub-trees of the tree rooted at that node. And it can assume one of the

three possible values {-1,0,1}.