Question

Please add thenodes given below to construct the AVL tree show all the necessarysteps,

Answer 1

Answer:

30,33,37,18,23,34,15,38,40,17

To construct the AVL tree, follow these steps and diagrams are shown in the image:

• Add 30 to the tree as the root node. Then add 33 as the right child because of 33 is greater than 30 and AVL tree is a binary search tree.

• Then add 37 as the right child of 33. Here the balance factor of node 30 becomes 0-2 = -2, unbalanced.

Use RR rotation, make node 33 the root node, 30 as the left child of 33 and 37 as the right child of 33.

• Now add 18 as the left child of 30. And 23 as the right child of 18. Here the balance factor of 30 becomes 2-0 = 2. It’s unbalanced.

Use LR rotation, make 23 the parent of 18 and 30.  

• Now add 34 as the left child of 37 and 15 as the left child of 18. Add 38 as the right child of 37. And then add 40 as the right child of 38.

• Now adding 17 as the right child of 15 makes the tree unbalanced at 18.

Use LR rotation, make 17 as the parent of 15 and 18.

Explanation:

The balance factor of a node can be either 0,1 or -1. Else the tree is called unbalanced at the node.

If the inserted node is in the left subtree of the left subtree of the unbalance node, then perform LL rotation.

If the inserted node is in the right subtree of the right subtree of the unbalance node, then perform RR rotation.

If the inserted node is in the left subtree of the right subtree of the unbalance node, then perform RL rotation.

If the inserted node is in the right subtree of the left subtree of the unbalance node, then perform LR rotation.