You should study the midterms and practice questions for the midterm. Here are a few questions about binary search trees to augment those questions.
How long, to within a constant factor, does it take to insert a new value into a height-balanced binary search tree that has n values in it?
log2(n)
Suppose that you insert 25 into the following tree using the algorithm that does rotations to keep the tree height-balanced. What is the resulting tree?
81
/ \
20 100
/ \
16 65
81 65
/ \ / \
20 100 20 81
/ \ / \ \
16 65 16 25 100
/
25
before rotations after rotations
The answer is the tree on the right. It is obtained from the
tree on the left by doing a double rotation at the root.
Consider the following tree with integer keys.
25
/ \
10 30
/ \
26 50
Is this tree a binary search tree? That is, does it obey the ordering requirements?
Yes.
Ignoring the keys, is this tree height-balanced?
Yes.
If you were to use the standard (unbalanced) binary search tree insertion algorithm, show what this tree would look like after inserting 40.
25
/ \
10 30
/ \
26 50
/
40
Is the tree height-balanced after inserting 40, without rebalancing?
No.
The binary search tree implementation that was discussed in class was nonpersistent; the insert operation, for example, changed the tree. It is possible to implement binary search trees in a persistent way also, so that they compute new trees from old ones.
Here is a type TreeNode of nodes for a binary search tree.
struct TreeNode {
int key;
TreeNode* left;
TreeNode* right;
TreeNode(TreeNode* l, int k, TreeNode* r)
{
left = l;
key = k;
right = r;
}
};
Using this type for tree nodes,
write a function removeMin(t) that returns the
tree that would result from removing the smallest value from tree t, but
that does not alter tree t. If t is empty, then
removeMin(t) should return an empty tree. For example, if
t is the tree
81
/ \
20 100
\
65
/ \
50 70
then removeMin(t) should
return the following tree, without altering tree t.
81
/ \
65 100
/ \
50 70
Do not rebalance the tree.
The new tree that you construct can share
subtrees with t, as long as it does not change the subtrees.
TreeNode* removeMin(TreeNode* t)
{
if(t == NULL) return NULL;
else if(t->left == NULL) return t->right;
else return new TreeNode(removeMin(t->left), t->key, t->right);
}