Mark: 19 revision(s)

2008-11-03T05:20:05Z

19 revision(s)

New page

== 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

SE250:lab-6:hpan027 - Revision history

Mark: 19 revision(s)