SE250:lab-6:hpan027

Task One

newTree = makeRandomTree(i);
printf("%d\n", i);

• Data was collected using a loop
• At first a arbitrary large number is used to get a rough idea of the relationship

for( i = 1; i < 10000; i *= 10 )

• However it seems like the height does not vary much when dealing with larger numbers
• Hence backtrack to get results for smaller tree sizes

for( i = 1; i < 100; i++ )

• Plotted result using excel - relationship seems to be logarithmic

Task Two

while ( node->left != empty )
	node = node->left;
return node;

• The minimum value of a tree resides in the leftmost node

while ( node->right != empty )
	node = node->right;
return node;

• Like minimum except to the right

Task Three

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

Task Four

if( node == empty ) //empty tree
	return empty;

if( node->left == empty && node->right == empty ) { //case for leaf
	while( node->parent != empty) { //backtrack
	    if( node == node->parent->left && node->parent->right != empty)
		return node->parent->right;
	     node = node->parent;
	}
	return empty;
    }

else { //case for parent/root
	if( node->left != empty)
	    return node->left;
	return node->right; //else

}

• Took a while due to several incorrect solutions which assumed every parent had 2 child

if( node == empty ) //empty tree
	return empty;

while( node->parent != empty ) {
	if( node == node->parent->left)
	    return node->parent;
	else { //if right
	    if( node->parent->left == empty)
		return node->parent;
	    node = node->parent->left;
	    while( node->left != empty || node->right != empty ) { //find the last value in the left subtree
		if( node->right == empty )
		    node = node->left;
		node = node->right;
	    }
	    return node;
	}
}
return empty;

• Phew

Task five

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

Task six

#include <math.h>
    int height = ceil( log( n + 1 ) / log( 2 ) - 1 );
    Node* newTree = mkNode( pow(2, height), empty );
    int i,j;
    i = height - 1;
    while( i >= 0 ) {
	j = 0;
	while( pow(2, i) + j * pow(2, (i+1)) < n ) {
	    insert( pow(2, i) + j * pow(2, (i+1)), &newTree );
	    j++;
	}
	i--;
    }
    return newTree;

• Note that this code does not give a well balanced tree, but does give the minimum height possible