SE250:lab-6:npit006

Task 1 - Measuring/Plotting Expected Height of Binary Search Trees Based on Number of Elements

At the start of the lab, I read over the code to familiarise myself with what was going on... a few of the methods were pre-written for us.

After doing that, Task 1 was very straightforward. I implemented a main method and worked from there. In order to calculate the expected height I used height(makeRandomTree(i)) for values of i from 0-99. I performed each operation 10 times and averaged the results. From my results below, I would suggest that the height is proportional to log size.

<html>

</html>

Task 2 - Implementation of minimum() and maximum() Functions

My code for these functions is below. These were very easy to write, as we know from lectures that the node with the minimum key will always be as far left as we can go. And the node with the maximum key will be as far right as we can possibly traverse.

I also used the makeRandomTree() function to create a tree whose handle I passed to these functions, so that I could test it. Since the key values are random, I cannot verify whether the minimum and maximum nodes (and their values) returned were actually correct. But I inferred that my methods worked properly based on the fact that minimum() always returned a smaller value than maximum(). It would have been nicer to write a more comprehensive test for this.

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 3 - Implementation of lookup() Function

For this task, we were required to write a lookup() function which would find the node in which a key (provided as an argument) was found - the function should return an empty node if there are no nodes in the tree.

I used a recursive solution to this problem and I probably could have trimmed my code down by a few lines since there seems to be a bit of repetition there, but it does work.

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

I spent a moment or two thinking about a test case for this. In the end, I called used minimum() on a random tree to find the node with the minimum key, then I performed a lookup with that key to check that it returned the same node that minimum() returned. And I repeated 10 times for experiment's sake. Code is below:

int i,a;
double sumHeight;
	
Node* ourRandomTree = empty;
Node *minimumNode, *maximumNode, *nodeWithValue;
	

for (i=1;i<10;i++){
        ourRandomTree = makeRandomTree(i);
		
	minimumNode = minimum(ourRandomTree);
	maximumNode = maximum(ourRandomTree);
	nodeWithValue = lookup(minimumNode->key,ourRandomTree);

	printf("\n\n The minimum value of the tree is %d", minimumNode->key);
	printf("\n The maximum value of the tree is %d", maximumNode->key);

	printf("\n The key of the node returned by lookup should be %d. It is actually: %d",minimumNode->key,nodeWithValue->key);
}

Task 4 - Implementing next_pre() and prev_pre() Functions

It was at this point in the lab where I started to have trouble. In the end I half-finished most functions for Task 4 and 5 before deciding to have a go at Task 6.

Task 5 - Implementing next_in(), prev_in(), next_post() and prev_post() Functions

Task 6 - Implementing insertMinHeight() Function

For this task, I started planning my function out on paper - I knew I'd have to think about how to calculate medians for the integers 1...n until I had inserted them all into the tree. By this point, I ran out of time.

Conclusion

This was the hardest lab for me as it's the first I haven't been able to finish. I feel that I probably should have researched binary search trees a bit more before embarking on this lab. Nevertheless, I plan to do that and return to this lab later on to finish the tasks and reinforce my understanding. I'm like scissors, you can't run with me.