Question

If the elements of (39,50, 92,70,27,37] were inserted into a self-balancing tree (in the same order as presented here), then where would each value be located at. • Note: Remember, 'null' is a possible answer for any of the blanks. • IMPORTANT: Please be sure to fill in each black with a number or the word 'null' (without any quotations). • Do NOT spell out each number. . For example, if one of the answers is '10, then your answer should NOT be "ten", it should simply be '10' (without the quotation marks). number 1 is number_2 is number_3 is number 4 is number_5 is number 6 is number_7 is [number_1]

Answer 1

Self balancing tree is the tree in which the balanced factor of every node is either -1,0 or +1.

The balanced factor of node = height of left subtree - height of right subtree

[39,50,92,70,27,37] are to be inserted in balancing tree.

STEP 1)First node 39 is inserted in the empty tree

Balanced factor of node 39 = height of left subtree - height of right subtree

Since node 39 is first node so it's both height of left and right subtree is 0

Balanced factor of node 39=0-0=0

This tree after adding node 39 is shown in figure 1 in image

FIGURE 1 FIGURE 2 FIGURE 3 39 39 39 50 921 FIGURE 3 FIGURE 4 39 50 IR (RR)=L7 50 (29 92 az) FIGURE 6 FIGURE_5 - 1 50 50 1 920 92 39 (39 27 70 70 csscanned with Carlscanner

FIGURE 7 FIGURES 50 50 92 92 O 39 LR 37 Rotation 70 70 27 27 39 37 FINAL TREE AFTER INSERTION 50 37 92 27 39 (70 Nuu FIGURE 9 C Scanned with CamScanner

STEP 2)Node 50 is inserted in the tree as according to binary search tree property 50 is more than 39 so it will come on right side of 39

Balanced factor of node 39=0-1=1

Balanced factor of node 50=0-0=0

The balanced factor is 1 and 0 after adding 50 so the tree is balanced as shown in image in figure 2

STEP 3)Now 92 is added according to binary search tree property it will come on right of node 50 because 92 greater than 50

Balanced factor of node 39=0-2=-2

Balanced factor of node 50= 0-1=-1

Balanced factor of node 92= 0-0=0

The tree after inserting 92 is shown in image in figure 3

But the tree is not balanced because balanced factor of node 39 is -2 as three are two right insertions(RR) so tree needs to balanced by making 1 left rotation L on node 39

The new tree after left rotation show in figure 4 which is balanced.

STEP 4) Node 70 is inserted in the balanced tree as 70<92 so it will come on left  side of the node 92.

Balanced factor of node 50=0-1=-1

Balanced factor of node 39=0-0=0

Balanced factor of node 92=1-0=1

Balanced factor of node 70=0-0=0

Since all balanced factor is 0 ,1 and -1 so tree is balanced

The tree is shown in image in figure 5

STEP 5)Node 27 is inserted in the balanced tree as 27<39 so it will be on the left side of node 39

Balanced factor of node 50=2-2=0

Balanced factor of node 39=1-0=1

Balanced factor of node 27=0-0=0

Balanced factor of node 92=1-0=1

Balanced factor of node 70 =0-0=0

Since all balanced factor is 0 and 1 so tree is balanced as shown in image in figure 6

STEP 6) Node 37 is inserted in the tree to right of node 27 according to binary search tree property as 37>27 so come on right side of node 27 as shown in image in figure 7.

Balanced factor of node 50=3-2=1

Balanced factor of node 39=2-0=2

Balanced factor of node 27=0-1=-1

Balanced factor of node 37=0-0=0

Balanced factor of node 92=1-0=1

Balanced factor of node 70=0-0=0

So the tree is not balanced as the node 39 has balanced factor 2 due to one left and one right insertion (LR) so two rotation are made on tree one left and one right rotation to give final tree in image in figure 8

Now the tree is balanced so the final tree after insertion shown in image in figure 9

Number_1 is 50

Number_2 is 37

Number_3 is 92

Number_4 is 27

Number_5 is 39

Number_6 is 70

Number_7 is null

FIGURE 1 FIGURE 2 FIGURE 3 39 39 39 50 921 FIGURE 3 FIGURE 4 39 50 IR (RR)=L7 50 (29 92 az) FIGURE 6 FIGURE_5 - 1 50 50 1 920 92 39 (39 27 70 70 csscanned with Carlscanner

FIGURE 7 FIGURES 50 50 92 92 O 39 LR 37 Rotation 70 70 27 27 39 37 FINAL TREE AFTER INSERTION 50 37 92 27 39 (70 Nuu FIGURE 9 C Scanned with CamScanner

FIGURE 1 FIGURE 2 FIGURE 3 39 39 39 50 921 FIGURE 3 FIGURE 4 39 50 IR (RR)=L7 50 (29 92 az) FIGURE 6 FIGURE_5 - 1 50 50 1 920 92 39 (39 27 70 70 csscanned with Carlscanner

We were unable to transcribe this image

FIGURE 1 FIGURE 2 FIGURE 3 39 39 39 50 921 FIGURE 3 FIGURE 4 39 50 IR (RR)=L7 50 (29 92 az) FIGURE 6 FIGURE_5 - 1 50 50 1 920 92 39 (39 27 70 70 csscanned with Carlscanner

FIGURE 7 FIGURES 50 50 92 92 O 39 LR 37 Rotation 70 70 27 27 39 37 FINAL TREE AFTER INSERTION 50 37 92 27 39 (70 Nuu FIGURE 9 C Scanned with CamScanner