SE250:lab-7:sdal039

Balanced order:

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

There are quite a few more, all starting with d as the root. This is enough to give the idea however...

Rotations to get from right skewed to left skewed tree:

Rotate left on root until finished.

Rotations to get from right skewed tree to balanced:

right, right, right, right
rotate left - at e
root
rotate left - at a
root, right
rotate left - at c
root
rotate left - at b

Difficulty in this was determining which node was the selected, as the (*) was sometimes positioned ambiguously.

Add in two new elements and balance insert h insert i

Need to make e the root

starting at root:
right - now at f
rotate right 
root - now at d
rotate left
root
right
right - now on g
rotate left

Tree is now of minimum height.

When an element is added or deleted, the insert function traverses a path from the root to the leaf. Is it always possible to rebalance the tree by performing rotations only on nodes along this path?

This isn't always true. If you have the tree

   d
 b   e
       f
         g
           h

and add in the element 'a' the resulting tree will be

     d
   b   e
 a       f
           g
             h

It is not possible to rebalance this tree without rotating elements in the roots right sub tree.