SE250:lab-6:sshi080

Lab 6

Task 1

Raw results:

Size	Height
3000	28
1500	25
600	21
300	18
150	13
100	12
50	10
10	5
0	0

Graph:

Couldn't upload to wiki, will host on intranet later.

Its clear that the relationship between the tree size and height is logrithmetic.

Task 2

Minimum & Maximum codes are pretty straight forward, but it looks like the random tree isn't seeded hence the minimum was always 41 for me. Time to seed the random generator kthx.

Minimum code

Node* minimum( Node* node ) {
  Node* min = empty;

  while(node != empty) {
	  if(node->left == empty)
		  min = node;
		  break;
	node = node->left;
  }

  return min;
}

Maximum code

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

Task 3

Tested with the random tree, searching for nodes larger and smaller than parent. Also tested for non existing keys.

Node* lookup( int key, Node* node ) {
	Node* result = empty;

	while(node != empty) {
		if(node->key == key) {
			result = node;
			break;
		}
		if(key < node->key) {
			if(node->left == empty)
				break;
			node = node->left;
		} else if(key > node->key) {
			if(node->right == empty)
				break;
			node = node->right;
		}
	}
	return result;
}

Task 4

This task took me awhile to figure out, was thinking on using recursive functions at first but it seems the most logical way is the following: I had a few problems are first with the node going up to its parent but it was going back to itself, then I added &&node->parent->right != node to stop it from going back to itself

Next in Preorder

Node* next_pre( Node* node ) {

	if(node->left != empty) {
		return node->left;
	}
	if(node->right != empty) {
		return node->right;
	}
	while(node->parent != empty) {
		if(node->parent->right != empty && node->parent->right != node) {
			return node->parent->right;
		}
	}

	return empty;
}

Previous in Preorder

Node* prev_pre( Node* node ) {
	if(node->parent != empty && node->parent->left != empty && nod) {
		return node->parent->left;
	}
	if(node->parent != empty) {
		return parent;
	} else {
		return empty;
	}
}