Question

root

1. [DSW] Create a balanced binary tree from the tree in figure 1 using DSW algorithm. Show step-by-step process including the process of
   1. creating backbone and   
   2. perfectly balanced tree  
2. [AVL]
   1. Delete node 9 from tree in figure 1, then determine balance factor for each remaining node, and create a balanced AVL tree from it.   
   2. Delete node 3 from tree in figure 1 by using Delete-by-Copying procedure, determine balance factor for each remaining node, and create a balanced AVL tree from it.
   3. Insert a node with 10 as the key to tree in figure 1, determine balance factor for each node after the insertion, and create a balanced AVL tree from it.

Answer 1

temp ay DSW. (a) 9x temp Tamp CREATING BACKBONE.

Oñol -6-4-4-a I 2- 2-4-5-6-off 4 -a 1 3 5 7 9 bt ç 3 BALANCING THE BACKBONE.

Balance fotor = Height (Left subs tous). Height (Right cub bul). Balance factor of ③ = 2-4 = -2 Bolame factor of 2-1-0-1 Balame factor of 0 - 0-0=0 Balance factor of 6 - 1-3= -2 Balance factor of 4 - 0-0-0 Balance factor of 6 - 0-2--2 Balance factor of 6 = 1-0-1 Bolamo fouter o ® - 0-0-0

Node 6 is imbalanced To balance we need R. L rotation. I after RL notation By i all modes have balance factor either 1,0,1 Heure the call in balanced

THE INORDER SUCCESSOR OF NODE IS NODE IS COPIED ON © and is DELETED HENCE THE TREE BECOMES o Oro Balame factor of © 2-4= -2 ☺ - 1-01 0 - 0-0-0 = 0-3=-3 6 - 0-2=-2 © = -1 = 0 - 0-0-0 9- 0-0-0

SINCE O IS UNBALANCED BY LLROTATION HENCE THE AVL TREE IS BALANCED.

(ii) BY BINARY SEARCH TREE INSERTION LOGIC. Balame factor of ☺: 2-52-3 0.0 6 = 1-4 = -3 -0 6 0 -3--3 = 0 0:0 G) 1-2--1

© IS UN BALANCED. BY RL ROTATION. 0 0.0 0 ® ILUNBALANCED BY LL ROTATION PLANCED oo 0 a BIS UNBALANCED By RL ROTATION OF

yu BALANC IN © by RR ROTATION BALANCING 4 BY LL ROTATION BALANCIN 4 BY LA ROTATION HENCE THE AVL TREE IS BALANCED.