User:Klod004

Lab 7

OMG my lab report just crashed, damn it. I got to start all over again. Let me try to remember as much as I can. Firstly, the lab couldn't run on visual, so we had to gcc compiler in command prompt. For me, multiple insert was not really working for some reason. The first task was dealing with building a tree with a random order of numbers. The tree that Mark had shown to us in one of the lectures has gotten imprinted in my brain and I used that tree for the insertion.

The order was : {4, 6, 7, 5, 2, 1, 3};

Another possible order of insertion was: {4, 6, 2, 3, 1, 7, 5};

The general rule is still nearly the same, to insert the root of each subtree before inserting its elements, that is, insert the median of the data so that becomes the root before inserting the rest of the data.

The next task was playing around with a skewed tree and trying to figure out how the controls work. This was easily accomplished.

The next task was starting with a right skew tree, and ending up with a left skew with the rotate controls.

This was rather easy, using rotate right on the root everytime gave a left skew tree.

So rotate right first, then go back to the root, and rotate right again and repeat till you get the left skew.

The next task was balancing the right skew using the commands, which also proved easy as the controls were rather simple to use:

This was the order of the commands used:

*rotate right 
*root
*rotate right
*root
*rotate right
*rotate left
*root
*left
*rotate right

            1
          2
        3
      4
    5
  6
7 (*)

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

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

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

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

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

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

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

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

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

Next thing, I added was 8 and 9.

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

Then I went, to the node which has 7 in it, and I simply used rotate left to give me:

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

For the last task, I deleted the node with 6, and what this did was take 7 and put that as the root of that tree.

    1
  2
    3
4 (*)
    5
  7
    8
      9

As seen, this is a sort of balanced tree, called a AVL tree. (I couldn't remember the name - Mark helped me remember).

And now the lab is over. This lab was fun and easy to do and completed with ample time. This also deepened my understanding of the binary tree, and how the the mechanics of this works.