SE250:lab-7:dsan039

Task One

Getting up to here took the most time, having to sort out emacs, which was having issues running the program but none compiling it. the Cygwin shell performed the task well and so in about 5 minutes i had the commands for the BST's sorted and began the tasks.

Task two

there are definately more than just 1 way(s) to make the BST such that no balancing is required. i Think that there's only one way to add the first one, 2 ways to add the second one, and 4! ways to order the addition of the remaining 4. Hence there are 48 different possible ways to add the letters a, b, c, d, e, f, g and still have a balance 7 node BST.

    a
  b
    c
d 
    e
  f
    g

Task Three

Before transformation:

a (*)
  b
    c
      d
        e
          f
            g

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

After Transformation:

  a (*)
b
  c
    d
      e
        f
          g

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

Just typing commands and copying the out-put to here..

Task Four

This task seemed simple - the tree starts off right skewed and it requires 6 "rotate left" commands (with corresponding "ROOT" commands in between) to make the tree left-skewed.

Task Five

this one was a little interesting, I'm not exactly sure if my answer is correct in the sense that it involves the fewest commands possible, infact it probably doesn't.

in order, after using the skew command:

1. rotate left
2. root
3. rotate left
4. root
5. rotate left
6. root
7. right
8. rotate left
9. root
10. left
11. rotate right

No. of rotations = 5

Task Six

This was relatively simple, i added the letters h and i to the tree (which previously had the letters a-g). i Then rotated the letter g left and the tree matched that found using the BALANCE command.

Task Seven

Only nodes along the path of the nodes (and the children of those nodes) in question are affected by a deletion/insertion. This means only they need to be adjusted if balancing is required.