IN THIS PROBLEM SET, ALL BINOMIAL QUEUES AND THEIR VARIANTS SHOULD BE REPRESENTED NOT AS BINARY TREES BUT IN THEIR ORIGINAL FORMAT (WHERE THE ROOT OF A TREE IN COLUMN K HAS K CHILDREN).
1. Give the binomial queue that results when the keys E A S Y Q U E S T I O N are inserted into an initially empty binomial queue.
2. [THIS IS THE ONLY DIFFICULT PROBLEM. DO IT LAST.] We showed in class how to remove any node from a binomial queue as long as it is the root of one of the trees. What if it is not? Here is a fairly naive solution: detach the node from its parent; remove it, and meld back the pieces hanging from it. The problem with this approach is that it's impossible to prove O(log N) time bounds any more.
2.1 Describe a sequence of inserts and deletes that produces a tree with N nodes and N distinct trees (ie, there are N columns).
The problem is that our deletion method may leave big gaping holes in the existing trees. To fix this, define a defective node as one that has exactly two missing children. Now, when we remove a node v (using the old method) we check what happens to its parent w. If w becomes defective (which would imply that one of v's siblings has already been deleted) then let W be the subtree rooted at w. We detach w from its parent (assuming it has one) meld W back into the queue. If that action itself causes its parent (ie, the grandparent of the original node) to be defective, then we repeat, and so on.
2.2 Note that the trees of the queue are now characterized by the fact that no parent can be missing more than one child. Prove that a tree in column k has at least c^k nodes (for some constant c<2). Hint: you may use induction to set up a recurrence relation on the minimum number of nodes such a tree can have. What's your best estimate on the constant c?
2.3 Bonus: what would you call such a priority queue?
2.4 Prove that operations INSERT-ITEM and DELETE-MAX still take O(log N) time, and that DELETE-ITEM (the new operation) takes O((log N)^2) time.
3. Binomial queues are designed by analogy with base-k integer representation, for k=2. What would be a queue look like if we chose k=3 instead? (How many nodes does a tree in column m have?). Explain how you could go about melding two queues. (No need for C code. A clear explanation in plain English with artistically hand-drawn pictures will do.)
4. Draw the binary search tree that results when you insert the following keys in that order into an initially empty tree, using the standard algorithm (no rotations) (program 12.7 in Sedgewicks's book). N O T H E R X M P L
5. Starting from the BST above, insert Q using the root insertion method. (This is the method that rotates at every node and does not use any randomization) (program 12.12 in Sedgewick's book).