SE250:lab-7:hlin079

task1

root-> the starting node left->left hand side of the current node right->right hand side of the current node parent->parent node of the current node

i toke me a while to figured out how to insert elements

task2

the order i used for this task is (d,b, a,c,f,e,g). the order of insertion can be start with the right hand side of d (f). the order of the insertion of (a&c)and (e&g) do not matter.

task3&task 4

rl command moved the right of the current node to parent postion. rr command moved the left of the current node to parent positon. the elements are in the same order before and after rl and rr command. skewed and rotated left: Before rotation:

a (*)
  b
   c
     d
       e
         f
           g

Order Before rotation: Tree[a,b,c,d,e,f,g]

After rotation:

 a
b (*)
  c
    d
      e
        g

Order after rotation: Tree[a,b,c,d,e,f,g] . rl command moved the right of the current node to parent postion. rr command moved the left of the current node to parent positon. the elements are in the same order before and after rl and rr command.

task5

after right skew the tree, i used

move the node to b             use rl
move the node to a by root     use two rl
move the node to c by root     use two rl
move the node to e by root     use rl
move the node to f by root     use rl

task 6

changing from right

a
 b
  c
   d
    e 
     f
      g (*)

to perfect balance tree

   a
  b
   c 
d(*)
   e
  f
   g

This was achieved by

move the node to b        use rl
move the node to a            use two rl
move the node to the new root c   use a rl then a rr
move to d by root command          
move to right ->e         use rl
move the node to g          use rl

Thus, perfect balance was achieved.

task7

adding 2 elements larger than the largest node into a perfectly balanced tree and using minimum rotations to achieve a perfectly balanced tree

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

To balance this tree i moved the node to g and used the rl command to produced this tree:

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

Is it always possible to rebalance the tree by performing rotations only on nodes along this path?