CS:3330:001 Algorithms Project 2: Due 3/7/2019
Computer Science is both a theoretic and experimental science.
Theoretic analysis tells us whether an algorithm is efficient or not in theory.
Experiments can help us to identify whether an idea is useful or not in practice.
To conduct an experiment, we may learn from how a
is conducted. Basically, you need to use random examples, not to choose examples in your favour, and
compare different ideas in the same environment.
In this project, we will study binary search trees. To help you get started, we provide the following java
bst.zip which contains the implementations of normal binary search tree (treeNode.java), AVL tree
(avltree.java), red-black tree (redblacktree.java), and splay tree (splaytree.java).
Study these codes and have them run on your computer is the first step of your project.
You are asked to complete the following tasks:
The remove method is missing in redblacktree.java. Provide an
implementation of remove in redblacktree.java and make sure it keeps
the red-black tree properties (the parent point is not allowed in
treeNode.java). Once this is complete, allow the remove operation to
be performed on red-black tree in the method test in bst.java. Compare the
performances of AVL tree, red-black tree, and splay tree by running
them on the same set of 100 examples with 5,000,000 mixed operations as
given in the method question0 (and used by test) in bst.java. Summerize the total running times for each
tree. The code for collecting running
times will be in the method question1 in bst.java.
Suppose we want to sort the array keys in bst.java by using
binary search trees. That is, we will insert each number in keys
into a search tree and then vist the tree in in-order traversal,
collecting the numbers along the way into another array, say res
(you may reuse ops in bst.java for res). To fulfil this goal, you are
asked to provide the method inorder in treeNode.java, with the interface
public int inorder(int i, int res)
where i is the first position available in res, and the method inorder
returns the next available position in res after it adds all the numbers in the subtree rooted by the current (this) node
into res. In a similar way as in the method test, create another
method in bst.java with the following interface:
public static void sort(int keys, int res, long times)
which collects the running time of creating a binary search tree
(i.e., avl, rbt, or spt), inserting all N keys in keys into the
tree and collecting all numbers in the tree in the sorted order
into res. Create 100 arrays of random numbers of size 500,000 to
test the performance of each tree, summarize the total running
time (the same set of arrays is used by
each tree). The code for collecting running times will be in the
method question2 in bst.java.
For both tasks, please give a summary of your experiments and draw conclusions from the experimental data.
Submit everything in the ICON dropbox for Project 2 before the