| | |
Show the traces for each sort requested below when applied to the array shown.
{ 'b', 'f', 'c', 'h', 'a', 'e', 'g', 'd' }The recursive form of the cost function for the quick sort in its worst case is given by $C(n) = C(n-1) + n$, and $C(1) = 0$.
Show how to solve this recurrence relation to derive the Big-O cost for the quick sort in the worst case.
In the recursive form of the cost function, describe what the two terms C(n-1) and n count.
Give the order in which the nodes of the following tree are visited when visited in:
If nodes are added to an empty binary search tree with the following keys and in the following order, draw the tree that results.
4, 1, 2, 7, 9, 3, 8, 9, 3, 5Consider the following list: K, C, H, -, I, M, X, - , A, E, Y, -, and an initially empty priority queue implemented with a heap (where the highest priority is given to the letter closest to "Z" in the alphabet). Working from left to right, if the element is a letter, it is inserted into the priority queue -- if it is "-", the highest priority element is removed. Show the state of the heap in array form after each insertion/removal.
The keys D A, B, G, I, C, H, J, K, E, are inserted into an initially empty red-black tree in that order. Draw the structure of the tree after each insertion.
Draw an example of a binary search tree with 7 nodes/keys where the average number of comparisons needed to find any key in the tree is maximized.
Draw an example of a binary search tree with 15 nodes/keys where the average number of comparisons needed to find any key in the tree is minimized.
For a binary search tree where the keys have been inserted in random order, what is the Big-O form for the average number of comparisons needed to find any given key?
Draw the three trees below that would result upon Hibbard deletion of the node with key 1, 5, and 11, respectively.
For the following questions, consider this implementation of a BST:
public class BST, Value> { private class Node{ private Key key; private Value val; private Node left; private Node right; private int count; // number of nodes in subtree // topped by this node public Node(Key key, Value val) { this.key = key; this.val = val; } } private Node root; // You may assume the below methods with { ... } bodies have been implemented: public void put(Key key, Value val) { ... } // inserts a node with key-val pair into this BST, it replaces // the associated value if the key is already in the BST public Node put(Node n, Key key, Value val) { ... } // inserts a node with key-val pair into the subtree of this BST // topped by node n, and returns the (possibly new) top node for // this subtree public int size() { ... } // returns the number of nodes in this tree public int size(Node n) { ... } // returns the number of nodes in the subtree topped by node n public Value get(Key key) { ... } // returns the value associated with key in this BST public int rank(Key key) { ... } // returns the number of nodes with keys less than the given key // in this BST public int rank(Key key, Node n) { ... } // returns the number of nodes with keys less than the given key // in the subtree topped by node n public Key select(int rank) { ... } // returns the key that has the given rank public Node select(Node n, int rank) { ... } // returns the node that has rank keys less than its associated key in // the subtree topped by node n public Node deleteMin(Node n) { ... } // deletes the node with minimum rank in the subtree topped by node n // and returns the (possibly new) top node for this subtree public void delete(Key key) { root = delete(root, key); //(see part b) } }
Complete the following method (to be added to the aforementioned BST class) so that it returns the "level" of a given node n. Recall, the level of a node n is the length of the shortest path between n and the root. So the root has level 0, its children have level 1, its children's children have level 2, and so on…
public int level(Node n) {
}
Complete the following method (to be added to the aforementioned BST class) so that the delete method mentioned previously performs the appropriate Hibbard deletion.
private Node delete(Node n, Key key) {
}
|
+--------4-----+
| |
-1--+ +--7-----+
| | |
-2--+ -5- +--9-
| |
-3- -8-
inserting D:
|
-D
inserting A:
|
+==D
‖
-A
inserting B:
|
+--B--+
| |
-A -D
inserting G:
|
+--B-----+
| |
-A +==G
‖
-D
inserting I:
|
+=====G--+
‖ |
+--B--+ -I
| |
-A -D
inserting C:
|
+========G--+
‖ |
+--B-----+ -I
| |
-A +==D
‖
-C
inserting H:
|
+========G-----+
‖ |
+--B-----+ +==I
| | ‖
-A +==D -H
‖
-C
inserting J:
|
+--------G-----+
| |
+--B-----+ +--I--+
| | | |
-A +==D -H -J
‖
-C
inserting K:
|
+--------G-----+
| |
+--B-----+ +--I-----+
| | | |
-A +==D -H +==K
‖ ‖
-C -J
inserting E:
|
+-----G-----+
| |
+=====D--+ +--I-----+
‖ | | |
+--B--+ -E -H +==K
| | ‖
-A -C -J
Answers will vary, but the "tree" should be a single linear chain (essentially a linked list, where every node has only one child, with the other reference being empty)
Answers will vary, but the tree must be perfectly balanced (15 nodes can fit into 4 levels), and in symmetric order.