AVL Tree & B - Tree
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis. Since AVL trees are height balance trees, operations like insertion and deletion have low time complexity. AVL tree checks the height of the left and the right sub-trees and assures that the difference is not more than 1. This difference is called the Balance Factor . Balance Factor Balance factor of a node in an AVL tree is the differenc e between the height of the l eft subtree and that of the right subtree of that node Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree) The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1. If the difference in the ...