SE250:lab-7:stsa027

Got started pretty quickly at the beginning, luckily, using the cmd.

Wrote report as I went up to task 4, then everything got deleted by accident. So... it'll be a brief report up until then.

Task One

Got familiar with moving around the tree using elements 1 to 7. The tree was a bit weirdly displayed. If you rotate the entire tree right 90 degrees, then 'left' and 'right' makes sense... Also, parent goes to the parent's parent. Which was a bit unexpected.

    1
  2
    3
4 (*)
    5
  6
    7

Task Two

Did that already with task one. Make a balanced tree by inserting the median of the ordered elements as the root. Then, the left and right children must be the median of the upper and lower 3 elements. The leaves may then be inserted in any order.

Another way to do this'd be first adding all the elements of the right or left subtree first, then doing the other subtree.

Task Three

Used 'skew' and 'rotate left' as instructed. The result of skew gives a tree of maximum height, with each only only having a right child. Rotate left causes the right child to replace the node rotate is performed on, and the replaced node is moved to the left subtree.

> skew
1 (*)
  2
    3
      4
        5
          6
            7

> rotate left
  1 (*)
2
  3
    4
      5
        6
          7

Task Four

The way rotate right and left is pretty simple if you're using it on a node with only one child, as seen in task 3. When rotating right, if there are two two children on the node that is moving towards the root, then the node's left subtree is removed, then after the rotation, the elements are added back to the tree. The left subtree of the node rotate is performed on remains as the left sub-tree of the node. Rotate left seems to simply be a mirroring of rotate right.

> i 7
    1
  2
    3
4 (*)
    5
  6
    7

> rotate left
      1
    2
      3
  4 (*)
    5
6
  7

> rotate right
    1
  2
      3
    4 (*)
      5
6
  7

Task Five

Easy. Just use rotate left on the root of the right skewed tree until it's left skewed. In the case of 7 elements, use 'rotate left' followed by 'root' 6 times...

Task Six

Turning a left skewed tree into a balanced tree.

'rr' then 'root' 4 times to turn the median of the tree into the root. Similar process making the other nodes the right values.

'right'

'rl'

'root' then 'left'

'rr'

Task Seven

The balance function provided is misnamed. It simply produces a tree of minimum height, and not a balanced tree.

Did it in 4 rotations. Couldn't think of a way to do it in fewer rotations...

    1
  2
    3
4 (*)
    5
  6
    7
      8
        9
> rr
    1
  2
    3
4
  5
    6 (*)
      7
        8
> rl
      1
    2
      3
  4 (*)
5
  6
    7
      8
        9
> rl
      1
    2
      3
  4
5
    6 (*)
  7
    8
      9
> rr
    1
  2
      3
    4 (*)
5
    6
  7
    8
      9

Task Eight

Still thinking about it...