SE250:lab-7:sbha077

Lab 7 Report

Things became a little easier for me once I understood what was required.

Task 1

Task 1 was rather straight forward. Left simply jumped to the next parent/child node on the left ( going up ). Right did the exact opposite. Root took you straight to the starting root of the tree. Parent goes to the parent node of the children that are " active " by using the right and left command.

Task 2

The tree was made using level order - insert root, then parent node and then the children nodes in left to right order per parent. The result of entering the tree looks like below:

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

     a
  b
    c
d (*)
    e
  f
    g

Task 3

For task 3 we were required to skew [ command : skew ] the tree and then rotate it left [ command : rl ]. I printed it after performing each operation and yes as expected, the result was the same:

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

> print
Tree[*a*,b,c,d,e,f,g,h,i,j]

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

> print
Tree[*a*,b,c,d,e,f,g,h,i,j]

Task 4

Rotate left moves the right child of the parent node into the parent node position. The original parent node becomes the left child of the new parent and the original left child becomes the new left child of the new parent.

The exact opposite happens for the right rotation.

Task 5

The tree from Task 2 was skewed right and we were required to reshape the tree into a left skew. The commands were a series of repetitive commands : "rl" and "root"

Each element was pushed left ( up ) and ultimately it went from:

a (*)
  b
    c
      d
        e
          f
            g

to:

            a
          b
        c
      d
    e
  f (*)
g

Task 6

Here we had to re-order the right skewed tree from Task 2 into a perfectly balanced tree as it originally was.

from:

a (*)
  b
    c
      d
        e
          f
            g

to:

     a
  b
    c
d (*)
    e
  f
    g

The sequence of commands was as follows:

rl root right rl root rl root right rl

Task 7

Here we were required to add to elements - larger than any of the existing elements and balance the tree. I decided to simply add "h" and "i". The result of adding these elements was:

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

Now to balance the tree, all I had to do was go down to "g" and left rotate that subtree. The result was:

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

Interestingly, using the "HELP" command, I discovered I could simply type "balance" and it would automatically do it for me!! SHEESH! Why on earth did I go through all that trouble earlier XD ( lecturers are sneaky now aren't they lol )

Task 8

From what I've done so far, it seems possible to rebalance the tree by performing rotations only on nodes.