Mark: 19 revision(s)

2008-11-03T05:20:16Z

19 revision(s)

New page

==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.
<pre>
Order:
d b a c f e g
d f e g b a c
d b f a c e g
</pre>

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.
<pre>
a
b
c
d (*)
e
f
g
</pre>
Using the '''print''' command I get the following output:
<pre>
Tree[a,b,c,*d*,e,f,g]
</pre>
What happens when I try to perform a left rotation on the root? I get this output:
<pre>
a
b
c
d (*)
e
f
g
</pre>
As you can see the tree has rotated so that ''f'' is now the root.
The '''print''' command gives:
<pre>
Tree[a,b,c,*d*,e,f,g]
</pre>
As was expected, the order of the elements has not changed.

==Right Skew Tree==
==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.
<pre>
Order:
d b a c f e g
d f e g b a c
d b f a c e g
</pre>

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.
<pre>
a
b
c
d (*)
e
f
g
</pre>
Using the '''print''' command I get the following output:
<pre>
Tree[a,b,c,*d*,e,f,g]
</pre>
What happens when I try to perform a left rotation on the root? I get this output:
<pre>
a
b
c
d (*)
e
f
g
</pre>
As you can see the tree has rotated so that ''f'' is now the root.
The '''print''' command gives:
<pre>
Tree[a,b,c,*d*,e,f,g]
</pre>
As was expected, the order of the elements has not changed.

==Right Skew Tree to Left Skew Tree==
<pre>
a (*)
b
c
d
e
f
g
</pre>
To do this task, use '''rl''' to rotate the tree left. Then use '''parent''' so that the current node is now the root.
<pre>
a
b (*)
c
d
e
f
g
</pre>
Repeat this process until your tree is left skewed!
<pre>
a
b
c
d
e
f
g (*)
</pre>

==Right Skew Tree to Balanced Tree==
Start
<pre>
a (*)
b
c
d
e
f
g
</pre>
Rotate Left and Change Current Node to Root ('''rl''' and '''parent''') * 2

Rotate Left
<pre>
a
b
c (*)
d
e
f
g
</pre>
Then Rotate Right
<pre>
a
b
c (*)
d
e
f
g
</pre>
Parent
<pre>
a
b
c
d (*)
e
f
g
</pre>
Right
<pre>
a
b
c
d
e (*)
f
g
</pre>
Rotate Left
<pre>
a
b
c
d
e (*)
f
g
</pre>
Finished!!
<pre>
a
b
c
d (*)
e
f
g
</pre>

==Add Two Elements and Then Balance Tree==
To start, insert the elements ''h'' and ''i''.
<pre>
a
b
c
d (*)
e
f
g
h
i
</pre>
Move Right.

Rotate Right.
<pre>
a
b
c
d
e
f (*)
g
h
i
</pre>
Parent

Rotate Left
<pre>
a
b
c
d (*)
e
f
g
h
i
</pre>
Left

Rotate Left
<pre>
a
b (*)
c
d
e
f
g
h
i
</pre>
Parent

Rotate Right
<pre>
a
b
c
d (*)
e
f
g
h
i
</pre>
Parent

Right

Rotate Left

Finished!!!
<pre>
a
b
c
d
e
f (*)
g
h
i
</pre>

SE250:lab-7:llay008 - Revision history

Mark: 19 revision(s)