SE250:lab-7:vpup001

This lab is about balancing binary search trees. The code is run by using GNU compiler.

Task 1

I have inserted the numbers, "4,5,6,7,3,2" and the tree looks like this...

     2
   3
 4 (*)
   5
     6
       7

The '(*)' next to the element '4' means it is the node.

When we use the command 'left' the node moves one step down to left child (left child is selected).

     2
   3 (*)
 4 
   5
     6
       7

When we use the command 'right' the node moves one step down to right child (right child is selected).

     2
   3
 4 
   5 (*)
     6
       7

If there is no right or left child to that particular node then nothing is selected.

When we use the command 'root', the root of the tree should be selected (in this case 4).

     2
   3
 4 (*)
   5
     6
       7

When we use the command 'parent', the parent should be selected. For example if (*) is next to '6' and we used parent command, it should be displayed next to '5' (since 5 is the parent of 6)

     2
   3
 4 
   5 (*)
     6
       7

• The command 'delete' is supposed to delete the element '(*)' is pointing to but its deleting the root!!!!
• The parent is not working properly. If the (*) is pointing to 7 and we used parent command it is pointing to 5 when it is suppose to point to 6 (since 6 is the parent of 7).

Task 2

Inserting elements a-g such that the tree is perfectly balanced.

The order of insertion was... "d,b,c,a,f,g,e"

     a
   b
     c 
 d (*)
     e
   f
     g

There are other orders of inserting elements which result in a perfectly balanced tree but the root should always be 'd' and the children of 'd' should always be 'b' and 'f'. We can insert the other elements in any order.

The other orders of insertion are...

"d,b,a,c,f,e,g"

"d,f,b,g,e,c,a" and so on...

• The order of insertion differs but the order is always the same which is "Tree[a,b,c,*d*,e,f,g]".

Task 3

The perfectly balanced tree...

     a
   b
     c 
 d (*)
     e
   f
     g

The order of the tree is printed by using 'print' command.

Tree[a,b,c,*d*,e,f,g]

The tree is skewed by using 'skew' and it looks like this...

a (*)
  b
    c
      d
        e
          f
            g

The order...

Tree[*a*,b,c,d,e,f,g]

When a left rotation is performed on the root...

     a 
  b (*)
    c
      d
        e
          f
            g

The order is...

Tree[*a*,b,c,d,e,f,g]

• The order of the tree is the same before and after the rotation. It is the structure of the tree that changes (root changes).

Task 4

"rotate left" rotates the selected node to left and "rotate right" rotates the selected node to right.

> rl
  a (*)
b
  c
    d
      e
        f
          g
> root
  a
b (*)
  c
    d
      e
        f
          g

> rl
    a
  b (*)
c
  d
    e
      f
        g

> parent
    a
  b
c (*)
  d
    e
      f
        g

> rr
  a
b
  c (*)
    d
      e
        f
          g

> rl
  a
b
    c (*)
  d
    e
      f
        g

• In the last tree, I have used 'rl' when 'c' was selected so the tree rotates from c (the whole tree doesn't rotate)!!