=============================================================================
CSC 263 Tutorial 3 Winter 2019
=============================================================================
Suppose we want to use a Binary Search Tree to store only keys (without any
additional information), and we want to allow duplicate keys. For example, if
we insert the key 12 twice, the BST should behave exactly as if there were
two separate copies of the key 12 stored in the tree.
1. The algorithm that we covered in lecture for TreeInsert does not handle
this situation right now: it explicitly disallows duplicate keys. Modify
the TreeInsert algorithm from lecture so that duplicate keys can be
inserted: treat equal keys the same way as larger keys (or smaller keys
-- just pick one and use it consistently, to keep the algorithm simple).
Write the complete algorithm and point out the changes you made. (Yes,
this involves mostly copy-and-pasting the algorithm from class and making
small changes -- it is meant to make you write down the complete
algorithm and understand it, as preparation for the later questions.)
Then, give a careful worst-case analysis of the running time of your
algorithm when it is used to insert n identical keys into a BST that is
initially empty.
This is a little different from what we've done up until now: we don't
want you to analyse the complexity of just one TreeInsert operation;
we want you to analyse the *total* time taken by *all* n calls to
TreeInsert.
In the rest of this tutorial, you will explore different ways that you can
improve on the running time of TreeInsert when duplicate keys are allowed.
2. First strategy: ensure duplicate keys are not always inserted on the same
side. Store a boolean flag goLeft in each node, initially set to True.
During insertion, when the key to be inserted is equal to the current
node's key, use the value of the current node's goLeft to determine
whether to insert the key in the left subtree or in the right subtree,
and flip the value of the current node's goLeft.
Write the complete algorithm and point out changes from your answer to
question 1.
Then, give a careful worst-case analysis of the running time of your
algorithm when it is used to insert n identical keys into a BST that is
initially empty. As before, analyse the *total* time taken by *all* n
calls to TreeInsert.
3. Second strategy: during insertion, when the key to be inserted is equal
to the current node's key, determine whether to insert in the left
subtree or the right subtree at random -- with equal probabilities for
left and right.
Write the complete algorithm and point out changes from your answer to
question 1. Then, analyse the worst-case performance of your algorithm
when it is used to insert n identical keys into a BST that is initially
empty, as before (this should be quick).
Finally, give an informal analysis of the expected running time of your
algorithm.
4. Can you come up with a better strategy? There are at least two simple
ideas that will work better for the particular case we are considering
(inserting n identical keys in an initially empty BST).
Describe your strategy in one concise paragraph, then write the complete
algorithm (point out changes from previous parts) and give a careful
worst-case analysis of your algorithm when it is used to insert n
identical keys into a BST that is initially empty (as before).