SE250:lab-7:dols008

Task 1

I just messed around with a few commands to begin with. Parent seemed to go directly to the root, rather than the actual parent, which was odd. I decided to investigate further, and found that it just steps up 2 levels instead of 1.

Task 2

To obtain a perfectly balanced tree of letters a-g, I inserted them as follows: d, b, a, c, f, e, g. There are plenty of other ways of inserting them, e.g. by layer: d, b, f, a, c, e, g. Once you have inserted a node, you can insert it's left or right in either order. You can also add to each subtree in any order, without affecting other subtrees. All orders result in the same tree.

Task 3

Um... Here you go:

> rl
  a (*)
b
  c
    d
      e
        f
          g

> print
Tree[*a*,b,c,d,e,f,g]

Task 4

I played with it for a while. Rotate left takes the right child and makes it the parent, shifting other nodes around as needed.

Task 5

To go from right skew to left skew, I used the following commands: rl, root, rl, root, rl, root, rl, root, rl, root, rl

Task 6

To balance the right skewed tree, I did the following: rl, root, rl, root, rl, rr, root, right, rl

Task 7

I'm not sure exatly what the criteria for rebalancing were supposed to be, but it only took 1 rotation to make it the minimum height.

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

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

Task 8

It seems like it should be possible to balance the tree only using rotations along that path, since inserting or deleting an element can only put each subtree along that path out of balance by one node.