SE250:lab-7:sshi080

Lab 7 Report

First I played around with the commands and figured out how everything worked. The visual display of the tree is pretty weird since its on its side and upside down. But if you draw it on paper it all makes sense.

Balanced Tree

I used the numbers 0 - 6 and inserted the median first, then the median of the two sub groups to make the tree balanced. (And so forth)

Basically if you do it that way, you can have any odd number of elements and it will be a perfectly balanced tree.

My tree was like this:

    0
  1
    2
3  (*) 
    4
  5
    6

Right Skew into Left Skew

The skew command turned the 7 element tree of mine (0,1,2,3,4,5,6) into a tree that is right skewed like this:

> skew

0 (*)
  1
    2
      3
        4
          5
            6

Then I used the following commands to make the tree into a completely left skew tree:

> rl
> ro
> rl
> ro
> rl
> ro
> rl
> ro
> rl
> ro
> rl
> ro

Now the tree is completely left skewed:

            0
          1
        2
      3
    4
  5
6 (*)

Right Skew into Min Height

I drew the tree on paper first, step by step.

Commands:

> rl
> ro
> rl
> ro
> rl
> rr
> ro
> r
> rl

Now the tree is perfectly balanced (min height).

    0
  1
    2
3  (*) 
    4
  5
    6

Balanced tree with 2 additional nodes skew back to balanced

The Tree

    0
  1
    2
3  (*) 
    4
  5
    6
      7
        8

Once again I drew it out on paper then figured out the commands to do the balance.

Commands: (Starting from root)

> r
> rr
> ro
> rl
> ro
> r
> r
> rl

This isn't completely balanced, as you can't get a single median out of the two sub groups from 9 elements.