Chapter 26.8, Problem 26.8.1CP

Explanation of Solution

AVL tree: It is a self-balancing binary search tree. If the tree is not balanced, the tree performs rotation operation.

Insertion of the nodes 1, 2, 3, 4, 10, 9, 7, 5, 8, 6:

Insertion of 1 and 2:

• First the value 1 is inserted as the node.
• The value 2 is greater than 1 and it becomes the right child of 1.

Insertion of 3:

• Next the value 3 is greater than 1 and it goes to the right of 1.
• The value 3 is again greater than 3 and it goes to the right of 2.

• Now the tree gets rebalanced.
• After inserting 3, the tree becomes,

Insertion of 4:

• The value 4 is greater than 1 and it goes to the right of 1.
• The value 4 is greater than 3 and it goes to the right of 3.

Insertion of 10:

• The value 10 is greater than 1 and it goes to the right of 1.
• The value 10 is greater than 3 and it goes to the right of 3.
• The value 10 is greater than 4 and it goes to the right of 4.

• Now the tree gets rebalanced.
• After inserting 10, the tree becomes,

Insertion of 9:

• The value 9 is greater than 2 and it goes to the right of 2.
• The value 9 is greater than 4 and it goes to the right of 4.
• The value 9 is lesser than 10 and it goes to the left of 10.