SE250:lab-6:stsa027

None of the functions written have actually been tested, but I've put thought into them, so the idea behind them should be right...

Also, some of the functions seem to be rather... inelegant. But, seeing as I don't have a better way to do it, this is the best I could come up with.

Comments were written with the code, basically to remind myself why I did what. They may be helpful in understanding what I wrote.

Task 1

Found the make random tree function, and the height function after a bit of searching. Then, created 2 for loops, with one nested within another. The outer one is for creating trees of different sizes, and the inner one to perform multiple trials for several times.

Had some problems with the syntax. Also had some problems with total height of the tree returning 4 regardless of the number of elements in the tree. Realised the problem was that I was using a double for 'totalHeight', but using '%d" in the printf statement.

CODE:

int main(){
    int i;
    int repeat;
    Node* randomTree;
    double totalHeight = 0;

    for(i = 10; i <= 100; i+=10){
	for (repeat = 0; repeat<10;repeat++){
	    randomTree = makeRandomTree(i);
	    totalHeight += height(randomTree);
	}
	printf ("treeSize = %d, averageHeight = %f \n", i, totalHeight/10);
    }
    return 0;
}


DATA GENERATED:

treeSize = 10, averageHeight = 5.700000 
treeSize = 20, averageHeight = 13.700000 
treeSize = 30, averageHeight = 22.100000 
treeSize = 40, averageHeight = 31.900000 
treeSize = 50, averageHeight = 42.600000 
treeSize = 60, averageHeight = 54.000000 
treeSize = 70, averageHeight = 65.700000 
treeSize = 80, averageHeight = 78.000000 
treeSize = 90, averageHeight = 89.800000 
treeSize = 100, averageHeight = 103.200000 

As you can see, as tree size increases, so too does average height of the tree. As treeSize increases, averageHeight increases at a rate that is faster than linear... This might be because the tree is becoming very unbalanced, so that the elements are only being added to a few branches of the tree.

Task 2

Fairly easy. Has the same kinda method to it as linked lists. Though lack of test cases poses a problem of not being able to be sure whether the function was written correctly, even if there were no complier errors. So, I made a random tree and just see if it gave the right kind of values.

All the code basically does is move down either the left branch (for minimum) or right branch (for maximum) until the leaf, where there are no more children.

Node* minimum( Node* node ) {
  if (node == empty)
    return empty;

  while(node->left != empty){
    node = node->left;
  }
  return node;
}

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

Task 3

I used a while loop to detect when a node has the key required, or when we have reached a leaf. Two 'if' statements were also used to decide which branch to take when the key was not found, by comparing the key required with the key in the node.

This task was not too difficult.

Node* lookup( int key, Node* node ) {
  while (key!=node->key & node!=empty){
    if (key >= node->key)
      node = node->right;
    if (key < node->key)
      node = node->left;
  }
  return node;
}

Task 4

At first, thought this task was rather straight foward. However, as I worked on it, more and more problems arose. Different cases of (possibly) missing nodes or reaching leaves or reaching the root of the tree all had to have different sets of instructions in order to reach the next or first node.

Got around the problem of not using key comparisons to determine whether the root given was in a left or right child of its parent by using "node->parent->right==node" or "node->parent->left == node".

After sorting out the next_pre, used a similar approach to complete the prev_pre function, where I just thought through the different arrangement of nodes, and how I should getto the previous node.

Also, as I did atsks 4, 5 and 6, realised that there were only a limited number of types of nodes -

• left leaf
• right leaf
• left node with only a left child
• left node with only a right child
• left node with two children
• right node with only a left child
• right node with only a right child
• right node with two children

Of course, for each method of tree traversals, there are several types that can be ignored, for example, don't need to care about the left subtree of a node if a node already has a right subtree when looking for the next node in order or post order.

Node* next_pre( Node* node ) {
  if (node->left!=empty)                     // if left node not empty, the next node is simply the left one.
    return node->left;
  if (node->right!=empty)                    // if there is no left node, the next node is the one at the right (if present).
    return node->right;                      // if a node passes both if statements, the node must be a leaf.
  while (node->parent->right == empty | node->parent->right == node){      //if the node's parent does not have a right child OR if this node is a right child, 
    node = node->parent;                     //move up the tree by 1 level.
    if (node->parent == empty)               //if we reached the root of the tree, there is no next node, so return empty.
      return empty;
  }
  return node->parent->right;                //we move up until the parent has a right child, which is the next node in preorder.
}


Node* prev_pre( Node* node ) {
  if (node->parent == empty)
    return empty;
  if (node->parent->left == node | node->parent->left == empty)
    return node->parent;
  return maximum(node->parent->left);  //this line is wrong.  Must consider possibility of having only a left subtree.
}

Task 5

Once I did Task 4, task 5 was easier, since the approaches used for both tasks were similar.

Node* next_in( Node* node ) {
  if (node==empty | maximum(node) == node)       //if node is the largest in tree, no next node.
    return empty;
  if (node->left == empty & node->right = empty & node->parent->left == node)       //if node is a left leaf, it's parent is the next node.
    return node->parent;
  if (node->right!=empty){                     // if the node has a right child, the right subtree's smallest node is the next elelment.
    node->right;                               // note that the a left child/subtree is ignored, because of the nature of 'in order'.
    return minimum(node);
  }
  if (node->parent->right == node){            // if node is a right node, then it's parent's parent is the next node.
    return node->parent->parent;               // note that the maximum node has already been taken care of by the first if statement.
  }
  return empty;
}

Node* prev_in( Node* node ) {
  if (node==empty | (minimim(node) == node)       //similar reasoning as next_in;
    return empty;
  if (node->left == empty & node->right = empty & node->parent->right == node)
    return node->parent;
  if (node->left != empty)
    return maximum(node->left);
  if (node->parent->left = node)
    return node->parent->parent;
}

Post order was not too hard, just a lot of thinking...

Node* next_post( Node* node ) {
  if (node == empty | node->parent == empty)    // no previous node for a root.
    return empty;
  if (node->right == empty & node->parent->right == node)  //if node is a right node, next element is its parent.
    return node->parent;                        //note we ignore the left subtree, because we don't (or need to) go back (post order is left->right->root).
  if (node->right == empty & node->parent->left == node)   // for a left node, the next node is the minimum node on the right subtree of it's parent.
    return minimum(node->parent->right);
  return minimum(node->parent->right);               //if the node has a right child, then that means both left (if present) and right subtrees have been done, so we move up, then down.
}

Node* prev_post( Node* node ) {
  if (node == empty | minimum(node) == empty)  // no previous node for minimum value of tree.
    return empty;
  if (node->right != empty)         // if node has right child, that is the previous node, whether or not it has a left child.
    return node->right;
  if (node->left != empty)          // if node has no right child, but a left child, then that is the previous node.
    return node->left;
  if (node->left == empty & node->right == empty & node->parent->right == node)  //for a right leaf, the previous node is the parent's left node.
    return node->parent->left;
  if (node->left == empty & node->right == empty & node->parent->left == node){  //for a left leaf,
    while(node->parent->right == node)                                           //the previous node is all the way up...
      node->parent;
    return node->parent->left;      //then it's the left child of that high node's parent.
  }
  return empty
}

Task 6

Incomplete.

Came up with a few ideas. The best was using the median as the first root, and the upper and lower quartile as the level 2 roots, as briefly discussed in lectures. However, couldn't figure out a way to implement it.