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 ...
Read more