SE250:lab-6:bvic005
Task1
For task 1 we had to find the expected height of a binary search tree filled randomly.
To do this, for each tree size(between 1 and 500) i used the provided makeRandomTree function 100 times, checking the height, and averaged the results. I then plotted the size/height pairs in excel, and fitted a curve to it.
code
void task1() {
int i, size, average;
Node* randomTree;
for(size = 1; size < 501; size++){
average = 0;
for(i = 0; i < 100; i++){
randomTree = makeRandomTree(size);
average += height(randomTree);
}
printf("Size = %3d Height = %2d\n", size, average/100);
}
}
results
Due to the fact that 500 lines takes up a considerable amount of vertical space, i have only posted every 10th result:
Size = 1 Height = 1 Size = 11 Height = 5 Size = 21 Height = 7 Size = 31 Height = 9 Size = 41 Height = 10 Size = 51 Height = 10 Size = 61 Height = 11 Size = 71 Height = 11 Size = 81 Height = 12 Size = 91 Height = 13 Size = 101 Height = 13 Size = 111 Height = 13 Size = 121 Height = 14 Size = 131 Height = 14 Size = 141 Height = 14 Size = 151 Height = 14 Size = 161 Height = 14 Size = 171 Height = 15 Size = 181 Height = 15 Size = 191 Height = 15 Size = 201 Height = 15 Size = 211 Height = 15 Size = 221 Height = 16 Size = 231 Height = 16 Size = 241 Height = 16 Size = 251 Height = 16 Size = 261 Height = 17 Size = 271 Height = 16 Size = 281 Height = 17 Size = 291 Height = 16 Size = 301 Height = 17 Size = 311 Height = 17 Size = 321 Height = 17 Size = 331 Height = 17 Size = 341 Height = 17 Size = 351 Height = 18 Size = 361 Height = 18 Size = 371 Height = 18 Size = 381 Height = 18 Size = 391 Height = 18 Size = 401 Height = 18 Size = 411 Height = 18 Size = 421 Height = 18 Size = 431 Height = 18 Size = 441 Height = 19 Size = 451 Height = 18 Size = 461 Height = 19 Size = 471 Height = 19 Size = 481 Height = 19 Size = 491 Height = 19
The best fit line, according to excel, was logarithmic, and has the equation:
height = 3.4896ln(size) - 3.0508
Task2
For this task we had to implement functions to return the node with the smallest, and largest, keys in a tree. This was quite easy, as all you had to do was follow the left branches for the min value, and right branches for the max value, due to the nature of binary search trees.
code
Node* minimum( Node* node ) {
while (node->left != empty)
node = node->left;
return node;
}
Node* maximum( Node* node ) {
while (node->right != empty)
node = node->right;
return node;
}
void task2() {
Node *min, *max;
Node* tree = makeRandomTree(9);
min = minimum(tree);
max = maximum(tree);
printf("min:\n");
printf("%d\n", min->key);
printf("\nmax:\n");
printf("%d\n", max->key);
printf("\nwhole tree:\n");
show_tree(0, tree);
}
results
min:
424238335
max:
1957747793
whole tree:
424238335 [2]
596516649 [4]
719885386 [3]
846930886 [1]
1649760492 [3]
1681692777 [2]
1714636915 [3]
1804289383 [0]
1957747793 [1]
As you can see, the code appears to give the correct results.
Task3
This task required the implementation of the lookup function, which looks for a specified key in a tree. The only mildly challenging part in this was realizing that you needed to check to see if the node you where looking at was an empty node, before checking if it had the key you where looking for. IE, you have to make sure the function doesn't try to read the key of empty, which would happen if the key wasn't in the index, and you didn't check for this, resulting in a segmentation fault. As it happens, the way i ended up printing the results of the lookup in my tests resulted in a segmentation fault anyway, but in real apps, results would be checked to see if the key was actually found, so this is not a problem.
I suppose i could have used recursion for this, but decided against it as there is almost no difference in code size, recursion is harder to write and for others to understand quickly, and it is often less efficient than loops at runtime anyway.
code
Node* lookup( int key, Node* node ) {
while ((node != empty) && (key != node->key))
if(key < node->key)
node = node->left;
else
node = node->right;
return node;
}
void task3() {
Node* tree = makeRandomTree(9);
Node* result;
printf("Tree:\n");
show_tree(0, tree);
result = lookup(719885386, tree);
printf("\n Lookup 719885386: %d\n", result->key);
result = lookup(1681692777, tree);
printf("\n Lookup 1681692777: %d\n", result->key);
result = lookup(1804289383, tree);
printf("\n Lookup 1804289383: %d\n", result->key);
result = lookup(5, tree);
printf("\n Lookup 5: %d\n", result->key);
}
results
Tree:
424238335 [2]
596516649 [4]
719885386 [3]
846930886 [1]
1649760492 [3]
1681692777 [2]
1714636915 [3]
1804289383 [0]
1957747793 [1]
Lookup 719885386: 719885386
Lookup 1681692777: 1681692777
Lookup 1804289383: 1804289383
Segmentation fault
Task4
In this task we had to write functions to find the next or previous nodes in a "preorder", well, order. This was quite hard, as what preorder was was not defined at all. After quite a bit of digging, i managed to get a good enough idea of what i was to come up with this code.
code
Node* next_pre( Node* node ) {
if(node != empty) {
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;
node = node->parent;
}
}
return empty;
}
Node* prev_pre( Node* node ) {
if((node != empty) && (node->parent != empty)) {
if(node->parent->left == node)
return node->parent;
if(node->parent->left == empty)
return node->parent;
node = node->parent->left;
while (node->right != empty)
node = node->right;
return node;
}
return empty;
}
I didn't have time to write any test code, especially as that would be quite hard. I would have had to create a custom tree, and then manually work out the preorder, to make sure it was giving the correct results. However, i was able to draw up a quick tree on a piece of paper, and work out the preorder for that(i think). This is what i used to work out the function logic, so as far as i can tell, the code should work.
This is all i have time for, though i would like to finish the lab at some point, as it is quite challenging.
Bvic005 02:26, 7 May 2008 (NZST)