AVL Tree And B Tree
AVL Tree An AVL tree is a subtype of binary search tree. Named after it's inventors Adelson, Velskii and Landis, AVL trees have the property of dynamic self-balancing in addition to all the properties exhibited by binary search trees. ~ Height of a node: -The height of an empty subtree is 0. -The height of a leaf is 1. -The height of an internal node is the maximum height of its children plus 1. ~ Balance factor: -The difference height of its LEFT subtree and its RIGHT subtree . The balance factor of all nodes in AVL tree should be at most 1. AVL Tree Example Right Rotation Left Rotation AVL Insertion Process If there is an imbalance in left child of right subtree, then you perform a left-right rotation. If there is an imbalance in left child of left subtree, then you perform a right rotation. If there is an imbalance in right child of right subtree, then you perform a left rotation. If there is an imbalance in right chi...