Question

Example of Insertion in AVL Tree

Answer 1

Example of Insertion in AVL Tree

Consider an AVL Tree with following numbers:

50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48

Step 1: Insert 50

Step 2: Insert 20

As 20 < 50, so insert 20 in 50’s left sub tree.

Step 3: Insert 60

As 60 > 50, so insert 60 in 50’s right sub tree.

Step 4: Insert 10

• As 10 < 50, so insert 10 in 50’s left sub tree.
• As 10 < 20, so insert 10 in 20’s left sub tree.

Step 5: Insert 8

• As 8 < 50, so insert 8 in 50’s left sub tree.
• As 8 < 20, so insert 8 in 20’s left sub tree.
• As 8 < 10, so insert 8 in 10’s left sub tree.

To balance the tree,

• Find the first imbalanced node on the path from the newly inserted node (node 8) to the root node.
• The first imbalanced node is node 20.
• Now, count three nodes from node 20 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.

Step 6: Insert 15

• As 15 < 50, so insert 15 in 50’s left sub tree.
• As 15 > 10, so insert 15 in 10’s right sub tree.
• As 15 < 20, so insert 15 in 20’s left sub tree.

To balance the tree,

• Find the first imbalanced node on the path from the newly inserted node (node 15) to the root node.
• The first imbalanced node is node 50.
• Now, count three nodes from node 50 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.

Step 7: Insert 32

• As 32 > 20, so insert 32 in 20’s right sub tree.
• As 32 < 50, so insert 32 in 50’s left sub tree.

Step 8: Insert  46

• As 46 > 20, so insert 46 in 20’s right sub tree.
• As 46 < 50, so insert 46 in 50’s left sub tree.
• As 46 > 32, so insert 46 in 32’s right sub tree.

Step 9: Insert 11

• As 11 < 20, so insert 11 in 20’s left sub tree.
• As 11 > 10, so insert 11 in 10’s right sub tree.
• As 11 < 15, so insert 11 in 15’s left sub tree.

Step 10: Insert 48

• As 11 < 20, so insert 11 in 20’s left sub tree.
• As 11 > 10, so insert 11 in 10’s right sub tree.
• As 11 < 15, so insert 11 in 15’s left sub tree.

To balance the tree,

• Find the first imbalanced node on the path from the newly inserted node (node 48) to the root node.
• The first imbalanced node is node 32.
• Now, count three nodes from node 32 in the direction of leaf node.
• Then, use AVL tree rotation to balance the tree.

---

For more Data Structures & Algorithms Tutorials Click here

---