AVL Rotations

-

Rotation is required only in the nodes which are imbalance, imbalance means that | height of right sub-tree - height of left sub-tree | > 1. Balancing reduce the height of tree like a tree with node n have maximum height (n-1) but after rotation it will be about log(n).

 There are generally 4-types of rotation in AVL tree ->

  1. LL Rotation
  2. RR Rotation
  3. LR Rotation
  4. RL Rotation
            Naming of rotation here used on the basis of insertion position (can be named anything). Like in LL rotation the inserted element is as position Given_Node->left->left, in RL rotation the inserted element is at location Given_Node->right->left. During insertion only a single get unbalanced and after balancing that node the whole tree get balanced again.

If we consider a<b<c, then -> 








Comments

Post a Comment

Popular posts from this blog

Insertion/Deletion in 2-3 Tree

-
Image
Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and right as child               So the final tree will be:      Insert 50:               50 is greater than 40 and after 40 a blank space so insert 50 in that blank space:     Insert 60:               60 is greater than 50 but there is no space for 60 so split, after splitting the root element will move to the root that contain 30 b/c there is an empty space in that node, so final tree will be:     Insert 10:               10 is smal
Read more