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?
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
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?
Ignoring the keys, is this tree height-balanced?
If you were to use the standard (unbalanced) binary search tree insertion algorithm, show what this tree would look like after inserting 40.
Is the tree height-balanced after inserting 40, without rebalancing?
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 70then removeMin(t) should return the following tree, without altering tree t.
81 / \ 65 100 / \ 50 70Do 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) {