Suppose that you use the merge/together algorithm discussed in class to manage connections in a graph. Show how the boss array changes as each of the following operations are done. Use the algorithm that does not do either of the improvements -- the basic algorithm. Use the variant where merge always makes its first parameter's leader the new boss of the second parameter's leader.
In the diagram, the merge function is abbreviated m. So, for example m(2,4) indicates that you should merge 2 and 4.
i boss[i] i boss[i] i boss[i] i boss[i]
1 0 1 ____ 1 ____ 1 ____
2 0 2 ____ 2 ____ 2 ____
m(1,5) m(5,2) m(5,4)
3 0 --------> 3 ____ --------> 3 ____ --------> 3 ____
4 0 4 ____ 4 ____ 4 ____
5 0 5 ____ 5 ____ 5 ____
Using the type TreeNode shown, write a function called PrintEvens that prints the even numbers in a binary search tree in descending order, one number per line, skipping the odd numbers in the tree. (Number n is even if n%2 == 0.) For example, if t is the tree shown in problem 5, then PrintEvens(t) would print the numbers 100, 20 and 16, one per line, in that order. The function should not modify the tree.
struct TreeNode {
int item;
TreeNode* left;
TreeNode* right;
TreeNode(int i, TreeNode* L, TreeNode* R)
{
item = i;
left = L;
right = R;
}
};
void PrintEvens(const TreeNode* T)
{
The binary search tree functions that we wrote in class modify the tree. It is also possible to write functions that do not modify a tree, but instead build a new tree, leaving the old on intact.
Using the type TreeNode of the previous problem, 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
The new tree that you construct can share
subtrees with t, as long as it does not change the subtrees.
TreeNode* removeMin(TreeNode* t)
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?