Mark: 18 revision(s)

2008-11-03T05:20:03Z

18 revision(s)

New page

= Lab 6 =
== Intro ==
In this lab we had to explore Search trees , and the order of the elements inserted. We had to conduct this lab so that we could find relationships of expected height and the insertion of the elements.

== Task 1 ==
int main(){

int h, i;
Node *randomTree;
printf("Size, Height\n");

for (i = 0; i < 1000; i=i+5){
randomTree = makeRandomTree(i);
h = height(randomTree);
printf("%d\n", h);
}

return 0;
}

== Task 2 ==

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

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

== Task 3 ==
==== Look up function ====
Node* lookup( int key, Node* node ) {

while(node != empty){
if (node == empty)
return node;

if (node->key == key){
return node;
}else if(node->key < key){
node = node->right;
}else{
node = node->left;
}
}
}

== Task 4 ==
==== next_pre ====

Node* next_pre( Node* node ) {
if (node == empty){
return empty;
}
if ( (*node)->right == empty){
return node;
}
else{
node = (*node)->right;
return (minimum(node));
}

}

==== prev_pre====

Node* prev_pre( Node* node ) {
if (node == empty){
return empty;
}
if ( (*node)->left == empty){
return node;
}
else{
node = (*node)->left;
return (maximum(node));
}
}
== Task 5 ==
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 6 ==
''#include <math.h> had to be included in this so that the function could operate properly ''
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;

== Conclusion ==

This lab was quite long, i only finished up to exercise 3 in the allocated time and then tried these later on. I'm not 100% sure they will be correct but Ive tried my best to get it done.

SE250:lab-6:asin185 - Revision history

Mark: 18 revision(s)