SE250:lab-6:jsmi233

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.