SE250:lab-6:asin185

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.