SE250:lab-7:gfun006

Took me 20 minutes to get going...because I couldn't get it to compile until I asked the lecturer who told me the command of

gcc lab-7.c

I was using cl /W4 previously which wouldn't work >_<

Task 1

1 (*)
  2
    3
      4
        5
          6
            7

I added those 7 distant elements in order...and then played around with the commands. My results are:

Left:

1
  2
    3
      4
        5
          6
            7

The star has disappeared...this must be because there is no left for it to go as everything has been added to the right of each node.

Right: 

1
  2 (*)
    3
      4
        5
          6
            7

If I had typed right instead, the star moves to the right once and therefore goes to the number 2.

Parent:

Root: 

1 (*)
  2 
    3
      4
        5
          6
            7

Root would always move the star back to the first node that was added, in this case it was 1.

Task 2

Insert in this order: d, b, f, a, c, e, g

This would give the following:

    a
  b
    c
d (*)
    e
  f
    g

However there are many other ways of doing this. 48 ways sounds logical because if you consider the last row, there are 4! ways of arranging them, and since there are 2 rows above that, that means 2 x 4! = 48. But this could be totally wrong so...yeah. For example d, b, f, e, g, a, c would give you the same thing.

Task 3

After skewing, it gave this result:

a (*)
  b
    c
      d
        e
          f
            g

Which makes sense because skew turns the tree to its maximum height.

After rotating left, it gave this result:

  a (*)
b
  c
    d
      e
        f
          g

Which also makes sense because it rotates the "a" to the left while moving "b" to the new root. This also reduces the height of the tree. I referred to the 2007 HTTB for some help on how rotation works. Both Tree[*a*,b,c,d,e,f,g] are shown, verifying the order is the same before and after.

Task 4

Hmm...by playing around with rotate left and right, I figured that if I rotated something left, I would obviously have to rotate the direction to the right if I wanted to get it back to the original. But I have to remember that I'm rotating the root everytime. For example, in the above example, to get it back to the original I would have to type "root", changing the root to "b", and then rotating right.

Task 5

To change the right skew tree into a left skew tree, I kept using rotate left and everytime changed the node back to the root first. Thus the commands were: rotate left, root, rotate left, root, rotate left, root, rotate left, root, rotate left, root, rotate left. This gives the result:

            a
          b
        c
      d
    e
  f (*)
g

Task 6

The commands to doing is: rotate left, root, rotate left, root, rotate left, root, left, rotate right, root, right, rotate left. Don't know if its the most efficient way but it's the way that I got working after a few trials.

Task 7

Starting with this tree:

    a
  b
    c
d (*)
    e
  f
    g

I then went and try and add a "h" and a "i"...My result was:

    a
  b
    c
d
    e
  f
      g (*)
    h
      i

I did this by first "i h", and "i i". I then used "right" until the * was on g. Then "rotate left". It was very simple and gave a balanced tree. I verified this by typing in balance which gave the same result.

Task 8

At this point I believe you can do so for insertion, but definitely not deletion. Due to the fact when you change something, that change will propagate up the tree. Although I could be totally wrong.