SE250:lab-6:rwan064

Introduction

Task 1

Plan

Plan
- Measure the expected height of a binary search tree.
- Plot the height for a range of tree sizes.
- Propose a relationship between the size and height for such trees.

Variables:
- height
- tree size (number of elements)
- y-axis: height
- x-axis: tree size (0-1000)

Pseudo code:

int height;
for i = 0 to 1000
  Tree = makeRandomTree( i );
  height = height(Tree);
  Print ( height );
end

Using the given function makeRandomTree( int ) I made random trees of varying sizes and calculated the height of each of these trees and printed them to the screen. When I wanted to make the graph I just piped the output to a file using Cygwin.

Command to run program:

make && ./lab-6.exe >> output.txt

The code used to do this:

The Makefile

Results

Using the values in output.txt I made a graph using Excel.

Here is a graph of log(x) vs. x:

Comparing the two graphs it seems like it's a logarithmic relationship. Hence:

Height of Tree = Log( Tree size )

Task 2

These two functions were quite easy to implement since this is a Binary Search Tree. Therefore the minimum is the left-most Node. And the maximum is the right-most Node. Hence for the minimum I just need to keep getting the left Node until I reach the empty node. Then return the last Node before the empty Node. The same goes for the maximum function, except in that case I would go on the right side.

The code for the minimum and maximum functions:

Task 3

The lookup function was also quite simple. Starting at the root, check if the key at the root is what we want. If not, check if the key is smaller or greater than the key of the root. If it's smaller, go to the left Node. Otherwise, go to the right. If an empty Node is reached, it means the key cannot be found in this tree. So return the empty Node in that case.

The code for the lookup function looks like this:

SE250:lab-6:rwan064

Contents

Introduction

Task 1

Plan

Results

Task 2

Task 3

Task 4

Task 5

Task 6

Navigation menu