1. Binary search trees implementation (60 pts)
Three binary tree classes are provided in the skeleton code:
LinkedBinaryTree : base class for binary trees
SearchTree : binary search tree
AVLTree : hight-balanced binary search tree
.h files are the interface definitions (header), and .txx files are
their implementation. You are required to fill in ToDo parts in txx
files only, and you are not allowed to modify the header files.
Therefore, you only need to submit the following four files:
SearchTree.txx, AVLTree.txx, main.cpp, and a report (pdf).
In txx files, you are required to implement the following functions:
TPos eraser(TPos& v)
TPos finder(const K& k, const TPos& v)
TPos inserter(const K& k, const V& x)// replace if k
void erase(const K& k)
Iterator insert(const K& k, const V& x)// replace
if k exists
void rebalance(const TPos& v)
TPos restructure(const TPos& v)
1. insert operation in SearchTree and AVLTreemust replace
the existing key rather than duplicating same keys.
2. You will be able to find the most of the implementation of
the above functions from our textbook, so you may use
them. However, simple cut-and-paste would not work
because the code in the textbook may have some
errors/bugs. Make sure your code works correctly.
3. You can freely modify main.cpp for your experiment (see
2. Performance comparison of binary search trees (90 pts)
As you realize, SearchTree is not height-balanced while AVLTree is
height- balanced. Therefore, the performance of the trees might be
In order to see the performance difference, you need to conduct the
following experiment and report the result.
(a) insert only
(b) find only
(c) erase and find in a random order
For each test, you must generate random test sets with different
sizes (100, 1000, 10000, 100000, and 1000000). Assume the
key type is unsigned int, and the value type is float. Run (a), (b)
and (c) experiments using the random test sets, and measure the
running time using clock(). The provided main.cpp contains some
examples how to generate random data and use clock to measure
For experiments (b) and (c), you must start with a search tree
that is already filled with a test set from experiment (a).
For experiment (c), you should test various erase/findratios (for
example, 20:80, 40:60, 50:50, 60:40, and 80:20). You must apply
erase and find in a random order with a random dataset.