AVL Tree and Binary Tree
AVL Tree AVL tree is a self-balancing binary search tree in which each node maintains an extra information called as balance factor whose value is either -1, 0 or +1 Balance Factor Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of 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. An example of a balanced AVL tree is: Operations on an AVL tree Various operations that can be performed on an AVL tree are: Rotating the subtrees in an AVL Tree In rotation operation, the positions of the nodes of a subtree are interchanged. There are two types of rotations: Left Rotate In left-rotation, the arrangement of the nodes on the right is transformed into the ...