SE250:lab-7:tlou006

1

Inserting the elements in the order: d b f a c e g produces the tree

    a
  b
    c
d (*)
    e
  f
    g

As explained during class; this was done by inserting the median first (in the sequence abcdefg), followed by the upper and lower medians. No other orders for this particular sequence will produce a balanced tree. I think

2

Taking the balanced tree

    a
  b
    c
d (*)
    e
  f
    g

then rotating left produces

      a
    b
      c
  d (*)
    e
f
  g

Skewing the sequence

a (*)
  b
    c
      d
        e
          f
            g

then performing the left rotation produces

  a (*)
b
  c
    d
      e
        f
          g

The order appears to be the same: a b c d e f g

Only the root nodes are different, this is expected because skewing the sequences sets the root at a while the balanced tree has the root at d, the median. Perhapes I misunderstood the question?

3

I looked up the HTTB and got a good idea of how rotations work.

Starting with a right skew

a (*)
  b
    c
      d
        e
          f
            g

Ending with a left skew

            a
          b
        c
      d
    e
  f 
g (*)

I understood that a left skew will start with the highest value as the root and move down decreasing. At first I inserted the values in the order of g f e d c b a to produce a left skew, then i realised it wasn't what the question was asking.

i used the commands

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

4

Starting with a balanced tree

    a
  b
    c
d (*)
    e
  f
    g

>right

>right

>right

>right

a
  b
    c
      d
        e (*)
          f
            g

> rotate left

a
  b
    c
      d
          e (*)
        f
          g

>root

>rotate left

>root

>rotate left

>root

>rotate left

      a
    b
  c (*)
d
    e
  f
    g

>rotate right

    a
  b
    c
d (*)
    e
  f
    g