SE250:lab-7:llay008

Getting Started

I arrived early to start this lab, but all in vain because it wouldn't compile. I tried emacs numerous times and even tried Visual Studio, but all I got were errors. In the end I used the command window. I was quite rusty on this - I have not used this since last year but was fine once I got going.

The first thing that struct me was that the tree was rotated on its side... and that the directions were the wrong way round. When I rotated the screen left was right and vice versa, so I just thought of it as up is left and down is right. It took some playing around to see how it all fit together.

One error(?) that I noticed was unless the current node was one branch away from the root, the parent command, instead of moving to the current node's parent, it moved to its parent's parent.

Creating a Perfectly Balanced Tree

Since there are only 7 elements, it is easy to see how to do this. We did a similar example in class. It was with numbers, not letters, but the principle was the same. Obviously there are a few variations with the same idea that will also give you a perfectly balanced tree.

Order:
d   b a c   f e g
d   f e g   b a c 
d   b   f   a c  e g

etc... Obviously, it is also possible to create the tree by creating a skewed tree and then balance it by rotating, but this I believe it the next task...

Skewing the Tree

Here is my tree from the last task.

    a
  b
    c
d (*)
    e
  f
    g

Using the print command I get the following output:

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

What happens when I try to perform a left rotation on the root? I get this output:

      a
    b
      c
  d (*)
    e
f
  g

As you can see the tree has rotated so that f is now the root. The print command gives:

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

As was expected, the order of the elements has not changed.

Getting Started

I arrived early to start this lab, but all in vain because it wouldn't compile. I tried emacs numerous times and even tried Visual Studio, but all I got were errors. In the end I used the command window. I was quite rusty on this - I have not used this since last year but was fine once I got going.

The first thing that struct me was that the tree was rotated on its side... and that the directions were the wrong way round. When I rotated the screen left was right and vice versa, so I just thought of it as up is left and down is right. It took some playing around to see how it all fit together.

One error(?) that I noticed was unless the current node was one branch away from the root, the parent command, instead of moving to the current node's parent, it moved to its parent's parent.

Creating a Perfectly Balanced Tree

Since there are only 7 elements, it is easy to see how to do this. We did a similar example in class. It was with numbers, not letters, but the principle was the same. Obviously there are a few variations with the same idea that will also give you a perfectly balanced tree.

Order:
d   b a c   f e g
d   f e g   b a c 
d   b   f   a c  e g

etc... Obviously, it is also possible to create the tree by creating a skewed tree and then balance it by rotating, but this I believe it the next task...

Skewing the Tree

Here is my tree from the last task.

    a
  b
    c
d (*)
    e
  f
    g

Using the print command I get the following output:

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

What happens when I try to perform a left rotation on the root? I get this output:

      a
    b
      c
  d (*)
    e
f
  g

As you can see the tree has rotated so that f is now the root. The print command gives:

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

As was expected, the order of the elements has not changed.

Right Skew Tree to Left Skew Tree

a (*)
  b
    c
      d
        e
          f
            g

To do this task, use rl to rotate the tree left. Then use parent so that the current node is now the root.

  a
b (*)
  c
    d
      e
        f
          g

Repeat this process until your tree is left skewed!

            a
          b
        c
      d
    e
  f
g (*)

Right Skew Tree to Balanced Tree

Start

a (*)
  b
    c
      d
        e
          f
            g

Rotate Left and Change Current Node to Root (rl and parent) * 2

Rotate Left

 
      a
    b
  c (*)
d 
  e
    f
      g

Then Rotate Right

    a
  b
    c (*)
d
  e
    f
      g

Parent

    a
  b
    c
d (*)
  e
    f
      g

Right

    a
  b
    c
d
  e (*)
    f
      g

Rotate Left

    a
  b
    c
d
    e (*)
  f
    g

Finished!!

    a
  b
    c
d (*)
    e
  f
    g

Add Two Elements and Then Balance Tree

To start, insert the elements h and i.

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

Move Right.

Rotate Right.

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

Parent

Rotate Left

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

Left

Rotate Left

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

Parent

Rotate Right

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

Parent

Right

Rotate Left

Finished!!!

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