SE250:lab-7:hbar055

• a-g were added in the order:

d, b, f, a, c, e, g to achieve a perfectly balanced tree.

The justification for this is that if seen in alphabetical order" a b c d e f g

d is the middle and is thus the most ideal root to allow for even spread as potentially, half of the nodes may end up on the left side and the other half on the other. subsequently, b and f were added as they are in the middle of the sets of letter larger and smaller than d. Thus, the remaining letters will only be inserted in the 3rd level of the tree. Hence any combination of these letter insertions will achieve a perfectly sorted tree as long as d b and f are inserted at first in the order.

• 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 Before rotation: Tree[a,*b*,c,d,e,f,g]

The skewed tree before and after rotation are displayed above. The display output has a strange way of ordering the nodes. A node adjacent to another node is less than the node in question if it is displayed above, and greater than if displayed below.

The order of the rotation has not changed even though the structure has changed.

   * changing from left skew to right skew 

This involved repeating the commands "root" and "rotate left" repeatedly until left skew is achieved:

           a
         b
       c
     d
   e
 f

g (*)

   * perfect balance from right skew 

   a
 b
   c 

d(*)

   e
 f
   g

This was achieved by first making 'd' the root by doing half of the process of achieving left skew. Once this is done, the selected node was set to the first node on the right of the root node 'd' (node e) and the Rotate Left command was used. This half of the tree then becomes balanced. After this, the selected node was set to the first node on the left of the root (node c) and a Rotate Right command was used. Thus, perfect balance was achieved.