Mark: 30 revision(s)

2008-11-03T05:20:08Z

30 revision(s)

New page

== Introduction ==

== Task 1 ==

=== Plan ===

* Plan
** Measure the expected height of a binary search tree.
** Plot the height for a range of tree sizes.
** Propose a relationship between the size and height for such trees.

* Variables:
** height
** tree size (number of elements)
** y-axis: height
** x-axis: tree size (0-1000)

Pseudo code:
<pre>
int height;
for i = 0 to 1000
Tree = makeRandomTree( i );
height = height(Tree);
Print ( height );
end
</pre>

Using the given function '''makeRandomTree( int )''' I made random trees of varying sizes and calculated the height of each of these trees and printed them to the screen. When I wanted to make the graph I just piped the output to a file using Cygwin.

Command to run program:
<pre>
make && ./lab-6.exe >> output.txt
</pre>

The code used to do this:

<html>
<image src="http://studwww.cs.auckland.ac.nz/~rwan064/lab6/task1main.PNG" width="347" height="253" alt="task1" />
</html>

[[SE250:lab-6:rwan064:Makefile| The Makefile]]

=== Results ===

Using the values in [[SE250:lab-6:rwan064:output.txt | output.txt]] I made a graph using Excel.

<html>
<image src="http://studwww.cs.auckland.ac.nz/~rwan064/lab6/task1.png" width="609" height="358" alt="task1" />
</html>

Here is a graph of log(x) vs. x:

<html>
<image src="http://studwww.cs.auckland.ac.nz/~rwan064/lab6/xlogx.png" width="552" height="340" alt="task1" />
</html>

Comparing the two graphs it seems like it's a logarithmic relationship. Hence:

<pre>
Height of Tree = Log( Tree size )
</pre>

== Task 2 ==

These two functions were quite easy to implement since this is a Binary Search Tree. Therefore the minimum is the left-most Node. And the maximum is the right-most Node. Hence for the minimum I just need to keep getting the left Node until I reach the empty node. Then return the last Node before the empty Node. The same goes for the maximum function, except in that case I would go on the right side.

The code for the '''minimum''' and '''maximum''' functions:

<html>
<image src="http://studwww.cs.auckland.ac.nz/~rwan064/lab6/task2.PNG" width="336" height="507" alt="min-max" />
</html>

== Task 3 ==

The lookup function was also quite simple. Starting at the root, check if the key at the root is what we want. If not, check if the key is smaller or greater than the key of the root. If it's smaller, go to the left Node. Otherwise, go to the right. If an empty Node is reached, it means the key cannot be found in this tree. So return the empty Node in that case.

The code for the '''lookup''' function looks like this:

<html>
<image src="http://studwww.cs.auckland.ac.nz/~rwan064/lab6/lookup.PNG" width="388" height="379" alt="lookup" />
</html>

== Task 4 ==
== Task 5 ==
== Task 6 ==

SE250:lab-6:rwan064 - Revision history

Mark: 30 revision(s)