Mark: 14 revision(s)

2008-11-03T05:20:09Z

14 revision(s)

New page

== Lab 6 ==

=== Task 1 ===

Raw results:

<pre>
Size Height
3000 28
1500 25
600 21
300 18
150 13
100 12
50 10
10 5
0 0

</pre>

Graph:

Couldn't upload to wiki, will host on intranet later.

Its clear that the relationship between the tree size and height is logrithmetic.

=== Task 2 ===

Minimum & Maximum codes are pretty straight forward, but it looks like the random tree isn't seeded hence the minimum was always 41 for me. Time to seed the random generator kthx.

Minimum code

<pre>
Node* minimum( Node* node ) {
Node* min = empty;

while(node != empty) {
if(node->left == empty)
min = node;
break;
node = node->left;
}

return min;
}
</pre>

Maximum code

<pre>
Node* maximum( Node* node ) {
Node* max = empty;

while(node != empty) {
if(node->right == empty) {
max = node;
break;
}
node = node->right;
}
return max;
}
</pre>

=== Task 3 ===

Tested with the random tree, searching for nodes larger and smaller than parent. Also tested for non existing keys.

<pre>
Node* lookup( int key, Node* node ) {
Node* result = empty;

while(node != empty) {
if(node->key == key) {
result = node;
break;
}
if(key < node->key) {
if(node->left == empty)
break;
node = node->left;
} else if(key > node->key) {
if(node->right == empty)
break;
node = node->right;
}
}
return result;
}
</pre>

=== Task 4 ===

This task took me awhile to figure out, was thinking on using recursive functions at first but it seems the most logical way is the following:
I had a few problems are first with the node going up to its parent but it was going back to itself, then I added &&node->parent->right != node to stop it from going back to itself

Next in Preorder
<pre>
Node* next_pre( Node* node ) {

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;
}
}

return empty;
}
</pre>

Previous in Preorder

<pre>
Node* prev_pre( Node* node ) {
if(node->parent != empty && node->parent->left != empty && nod) {
return node->parent->left;
}
if(node->parent != empty) {
return parent;
} else {
return empty;
}
}
</pre>

SE250:lab-6:sshi080 - Revision history

Mark: 14 revision(s)