Question: AVL tree and four categories of rotations.
0

AVL tree:

  • AVL tree is a self balancing binary search tree, in which the heights of the two sub trees of a node may differ by at most one.

  • Due to this property, the AVL tree is also known as height balance tree.

  • The key advantage of using an AVL tree is that, it takes O (log n) time to perform search, insert and delete operations in an average case as well as the worst case (because the height of the tree is limited to O (log n)

  • It is a binary search tree in which node has a balance faster of -1, 0 or 1 is said to be height balanced.

  • There are four types of re-balancing rotations and applications of these rotations depends on the position of the inserted node with reference to the critical node.

  • The four categories of rotations are:

a] LL rotation : The new node is inserted in the left sub tree of the left sub tree of the critical node.

b] RR rotation: The new node is inserted in the right sub tree of the right sub tree of the critical node.

c] LR rotation: The new node is inserted in the right sub tree of the left sub tree of the critical node.

d] RC rotation: The new node is inserted in the left sub tree of the right sub tree of the critical node.

Example:

44 17 32 78 50 88 48 62 54

Step 1: Insert 44

enter image description here

Step 2: Insert 17

enter image description here

Step 3: Insert 32

enter image description here

Step 4: Insert 78

enter image description here

Step 5: Insert 50

enter image description here

Step 6: Insert 88

enter image description here

Step 7: Insert 48 Step 8: Insert 62

enter image description here

Step 9: Insert 54

enter image description here

renu • 20 views
ADD COMMENTlink
written 25 days ago by gravatar for RB RB100
Please log in to add an answer.