SE250:lab-6:llay008

Task One

Task one was straightforward. I had no major problems with this other than some small syntactical errors in my code that were easily remedied and the fact that it seemed to take a long time...

an excerpt from my code:-

  for (size = 10; size < maxSize ; size+=10) {
	for(i = 0; i < n; i++) {
	    randomTree = makeRandomTree(size);
	    treeHeight += height(randomTree);
	}
	aveHeight = treeHeight/n;
	printf("size = %d average heigth = %f\n", size, aveHeight);
    }

This gave the output:-

size = 10 average heigth = 5.640000
size = 20 average heigth = 13.440000
size = 30 average heigth = 22.370000
size = 40 average heigth = 32.300000
size = 50 average heigth = 43.070000
size = 60 average heigth = 54.530000
size = 70 average heigth = 66.970000
size = 80 average heigth = 79.490000
size = 90 average heigth = 92.230000

The relationship appears to be that the larger the tree, longer the the height in relation to the tree size. I plotted a graph but was unsure how to load it on to the wiki.

Edit: I later realised that these results are erroneous because I forgot to set the average height back to 0.

State4Plasma was here... *height* you mean? ;p (just mucking around a bit XD)

Task Two

This again was straightforward. My code is as follows:-

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

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

Task Three

After getting off onto the wrong track (for only a short time luckily) by forgetting about the properties of empty, I created this code:-

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