SE250:lab-7:twon069

Task 1

Familiarizing with the given codes were tough. However the commands and introduction given were rather simple, however I find it irritating how the tree are displayed in the cmd prompt, it was REALLY irritating to navigate through, even for a short tree.... as the tree aren't displayed properly and you would have to first navigate through them to figure out which values went where...

• Note: the "parent" command seen to not work..., jumping 2 nodes above instead of 1.
• Note: actually, after going through Task 2, the tree's appearance seen to become clear, except the orientation of the nodes seen to be off, right = down, left = up. Whereas if right = up, left = down, makes more sense as tilting your head on the side gives you the tree.

Task 2

• Inserting the char in the given order "d b f a c e g" gives a perfectly balanced tree:

         d
      __/ \__
     b       f
    / \     / \
   a   c   e   g

• Inserting the char in an order such that:

"d" is inserted first
"b" and "f" are inserted next
"a" "c" "e" "g" are inserted last

gives a perfectly balanced tree, ie. inserting the tree in "level order".

• Any other order simply will not work due to the code not manipulating the tree and comparing the values to be inserted with the parent of the base nodes.

Task 3

• Skewing the tree gives the expected shape of a linked list:

a
 \
  b
   \
    c
     \
      d
       \
        e
         \
          f
           \
            g

• Rotating left on Node a, should give:

  b
 / \
a   c
     \
      d
       \
        e
         \
          f
           \
            g

which was right when the tree is printed:

  a (*)
b
  c
    d
      e
        f
          g

Task 4

Again, this was all fun and game, rotating each nodes left and right... blah blah blah...

Task 5

This was pretty random... the following commands were repeated until the last nodes is flipped into position.

• rl //rotating the root node left
• root //moves the targeted nodes to the new root node
• rl
• root

. . . . . . .

Result should look like:

             g
            /
           f
          /
         e
        /
       d
      /
     c
    /
   b
  /
 a

Result printed in cygwin:

            a
          b
        c
      d
    e
  f
g (*)

Task 6

In order to achieve a perfectly balanced tree from a right skewed tree, the following were done.

1)Point the node to the root. 2)Rotate left. 3)Repeat 1) and 2) until the root node is d. 4)Place the node to c (the left children of the root node d). 5)Rotate right on root c, putting c under b and in the same level as a. 6)Place the node to e (the right children of the root node d). 7)Rotate left on root e, putting e under f and in the same level as g.

Task 7

Starting with the balanced tree, adding h and i.

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

Reshaping the tree in such a way that e is the root node with left children and right children at it's longest length(ie back tracking task 6).

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

Then perform a similar procedure as task 6, to achieve a balanced tree.

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

Alternatively, a "balanced" tree with the same length could b obtained simply by rotating left on node g in the first diagram to produce the following.

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

Task 8

Yes, it is possible, because when removing or adding elements into the tree, only the subtree containing the added/removed element are altered. Therefore it can be balanced simply by transversing along the subtree that is affected.