Mark: 4 revision(s)

2008-11-03T05:20:06Z

4 revision(s)

New page

== Binary Seach Trees ==

For the first task, I investigated the relationship between Tree Size and Tree Height for a randomly generated Tree. I wrote some code to test the height of a random tree for tree sizes between one and one hundred. My results can be seen here: http://studwww.cs.auckland.ac.nz/~jsmi233/graph.jpg

The graph shows that there is a strong relationship between the variables. Thanks to excel, I have found a rather fitting model for this relationship. Tree Height = 1.8378 * Tree Size ^ 0.4463

For the coding tasks, one key decision that I had to make for each function was whether to write it recursively. In some cases this was more clear cut than others. For the first of these however - the min and max functions - it was pretty much a toss of the coin, and I chose not to write them recursively. Here is my code:

Node* minimum( Node* node ) {
if (node == empty)
return empty;
for (; node->left != empty; node = node->left);
return node;
}

Node* maximum( Node* node ) {
if (node == empty)
return empty;
for (; node->right != empty; node = node->right);
return node;
}

The lookup function was fairly straight-forward. This one I implemented recursively:

Node* lookup( int key, Node* node ) {
if (node == empty)
return empty;
else if (key == node->key)
return node;
else if (key < node->key)
return lookup(key, node->left);
else return lookup(key, node->right);
}

My first attempt at writing the next_pre function was insufficient, as I realised later. I had failed to handle the case where the node passed into the function was a leaf node but not the last leaf node. I made changes to fix this, but the function ended up looking quite messy.

SE250:lab-6:jsmi233 - Revision history

Mark: 4 revision(s)