07-01-2010, 04:59 PM
CS301 – Data Structures
Assignment No.4
Question 1:
Show the result of inserting the following values into an empty AVL Tree.
You are required to show each step of insertion and rotation (to make the tree balance) in pictorial form with balance of each node.
19,21,22,17,18,23,27,25,30,34, 35
Solution:
CS301.jpg (Size: 23.93 KB / Downloads: 138)
First we insert node 19 to make an AVL tree.then we insert 21 and compare its with root .This compare will rotate that 21 will goes to right subtree of 19.Then we compare 22 with 21 and this will also goes to right subtree of 21 Now let’s see the balance of nodes at this stage. We can see that the level of node 19 is at 0 level. But the difference of the height of left and right subtree of 19 is -2and that is unbalance.so we will rotate according to pictorial form.
Now we will insert new node 17.after comparing it with node 19 we will insert it as left subtree of 19. After that we will insert node 18 at right subtree of 19. Then node 23 at right subtree of 22.now we can see that tree is balance yet. But when we will insert node 27 at right subtree of 23 again tree will be unbalance.so we will rotate left.
Question 2
Assignment No.4
Question 1:
Show the result of inserting the following values into an empty AVL Tree.
You are required to show each step of insertion and rotation (to make the tree balance) in pictorial form with balance of each node.
19,21,22,17,18,23,27,25,30,34, 35
Solution:
CS301.jpg (Size: 23.93 KB / Downloads: 138)
First we insert node 19 to make an AVL tree.then we insert 21 and compare its with root .This compare will rotate that 21 will goes to right subtree of 19.Then we compare 22 with 21 and this will also goes to right subtree of 21 Now let’s see the balance of nodes at this stage. We can see that the level of node 19 is at 0 level. But the difference of the height of left and right subtree of 19 is -2and that is unbalance.so we will rotate according to pictorial form.
Now we will insert new node 17.after comparing it with node 19 we will insert it as left subtree of 19. After that we will insert node 18 at right subtree of 19. Then node 23 at right subtree of 22.now we can see that tree is balance yet. But when we will insert node 27 at right subtree of 23 again tree will be unbalance.so we will rotate left.
Question 2