SE250:lab-7:jpar277

Overview

Starting off with compiling the code, it didn't work in visual studio so I had to turn to the gcc compilier. But then I had issues with emacs when trying to run it. So I just ran off the compiled lab7.exe file.

I managed to do tasks 1-7 in the lab time (awesome!) ... and then I got to task 8 at 12pm and got rather confused. To be honest, I was too hungry to wrap my head around it >< ... hence I haven't done it.

I think the lab itself was pretty fun and cruisy.

Task 1

Getting familiar with the "left" "right" "parent" and "root" commands were pretty simple not hard to figure out what they do. Left goes to the current node's left child and that becomes the current node. Similarly for the right command, it goes to the right child and makes that the current node. Parent SHOULD go to the parent node of the current node, however, it goes to the parent's parent (moves up 2 levels instead of 1). The root command will change your current node to the root no matter which node you are at.

Also, any short version of the commands will work. For example, left, lef, le and l do the same thing.

Task 2

There are many ways in which you can insert the letters a-g and get a perfect tree.

However ::::

• The first letter to be inserted MUST be d.
• The next to be inserted must be b or f - order does not matter. This is where the order can change in many variations.
• a and c can only be inserted after b (order does not matter, a then c or c then a).
• e and g can only be inserted after f (order does not matter, e then g or g then e).

Task 3

I skewed the tree from Task 2 to the right (seeing as you can't go lower than a ~_~). I got the order

Tree[a,b,c,*d*,e,f,g,h,i,j,k,l]. Then I rotated it to the left as asked and got the order

Tree[a,b,c,*d*,e,f,g,h,i,j,k,l]. As you can see the rotate function did not change the order of the elements.

Task 4

Its quite easy to understand how left and right rotation works. The left rotation command takes the current node's right child and makes it it's parent. The node then becomes the left child. And vice versa for the right rotation, it takes the current node's left child and makes it it's parent. The node then becomes the right child.

Task 5

Using the same tree from Task 2, I used the "skew" command to get a tree that is completely right skewed. Then using the left rotation command and the root command, I turned it into a left skewed tree.

• rl
• root
• rl
• root, etc.

Task 6

Again using that right skewed tree from Task 2 using the left and right rotation and the change node commands, right and root, I turned it into a perfectly balanced tree.

Sequence of commands ::::

• rl
• root
• right
• rl
• root
• rl
• root
• right
• rl

Task 7

Using the balanced tree from Task 6, I added in 2 new elements, h and i. Unfortunately, with these new elements we can't get a perfectly balanced tree with all the branches being the same height. So the arguement is what we consider to be a balanced tree with these 2 extra elements. The height of the tree is obviously going to be 3 but the question is where are these level 4 elements going to be placed. However, the task asks for the MINIMUM number of rotations, hence there can ONLY be ONE answer. Our skewed tree looks like this ::::

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

then you enter the commands ::::

• right
• right
• rl

and with just ONE rotation command, you get the balanced tree that looks like this ::::

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

Task 8

@_@