| | |
Show the traces for each sort requested below when applied to the array shown.
{ 'f', 'b', 'a', 'h', 'c', 'd', 'g', 'e' }Describe an improvement that could be made to the basic in-place quick sort algorithm that would reduce its recursive overhead.
The cost function for merge sort can be written as follows. Show how to solve this recurrence relation to derive the Big O cost for merge sort. $$C(n) = 2 C(\frac{n}{2}) + n \quad ; \quad C(1) = 0$$
Write the recurrence relation for the cost function that gives the number of comparisons in sorting $n$ elements using quick sort, in both best case and worst case.
If the items are inserted into a binary search tree in random order, the worst-case height can be O( __ ), but the expected height is O( __ ). (Fill in the blanks)
A binary search tree is a tree in which:
node class and addNode() method (note the additional reference to parent):
public class Node {
int x;
Node left;
Node right;
Node parent;
public Node(Node p, int v){
parent = p;
x = v;
}
}
static void addNode(Node n, int v) {
if (v < n.x) {
if (n.left == null) {
n.left = new Node(n, v);
}
else {
addNode(n.left, v);
}
}
else {
if (n.right == null) {
n.right = new Node(n, v);
}
else {
addNode(n.right, v);
}
}
}
Part I - Draw the binary search tree that the main method below would generate:
public static void main(String[] args) {
Node root = new Node(null, 8);
addNode(root, 3);
addNode(root, 2);
addNode(root, 1);
addNode(root, 4);
addNode(root, 9);
}
Part II - List the node keys of the following example binary search tree in pre-order, in-order, and post-order, respectively.
Part III - Describe an algorithm (or write down the pseudocode) for a method called findBLT which finds the biggest value strictly less than some $x$ in a binary search tree.
If there is no value less than $x$ the method should return -1. The main below gives examples of using this method against the example tree in Part II, above.
Note: x is not necessarily in the tree. Also, assume all numbers in the tree are positive. Finally, the method should run O$(\ln n)$ i.e. do not traverse the whole tree.
public static void main(String[] args) {
Node root = new Node(null, 10);
//...
System.out.println(findBLT(root, 20)); //prints 19
System.out.println(findBLT(root, 6)); //prints 4
System.out.println(findBLT(root, 4)); //prints -1
System.out.println(findBLT(root, 16)); //prints 15
}
Consider the following list: Q, R, F, -, Y, B, N, - , Q, M, F, -, 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.
Show the state of the following tree after using Hibbard deletion (involving successors) to:
B, and thenR.
|
+--------U--+
| |
+--------------N-----+ -V-
| |
+--B--------+ +--R-
| | |
-A- +-----L--+ -O-
| |
-E--+ -M-
|
-F-
The keys T, F, B, S, D, I, Y, N, Q, M are inserted into an initially empty red-black tree in that order. Draw the structure of the tree after each insertion.
Order before mergesort application: f b a h c d g e 0 1 2 3 4 5 6 7 ------------------------ b f a h c d g e a b f h c d g e a b f h c d e g a b c d e f g h Order after mergesort application: a b c d e f g h
Order before quicksort application:
f b a h c d g e
lo pivot hi 0 1 2 3 4 5 6 7
-------------------------------------
f b a h c d g e
f b a h c d g e <-- if we had shuffled things,
f b a e c d g h it would have been at this point
0 5 7 d b a e c f g h
d b a c e f g h
0 3 4 c b a d e f g h
0 2 2 a b c d e f g h
0 0 1 a b c d e f g h
6 6 7 a b c d e f g h
Order after quicksort application:
a b c d e f g h
|
+-----8--+
| |
+--3--+ 9
| |
+--2 4
|
1
pre-order: 10, 6, 4, 9, 14, 20, 15, 19
in-order: 4, 6, 9, 10, 14, 15, 19, 20
post-order: 4, 9, 6, 19, 15, 20, 14, 10
While answers will vary, the essential cases one must consider are the following:
(recall, the priority queue keeps track of its size, so null elements of the array at positions greater than size are not shown, although the first position is empty, as indicated by the "-"'s below) -Q -RQ -RQF -QF -YFQ -YFQB -YNQBF -QNFB -QQFBN -QQMBNF -QQMBNFF -QNMBFF
B:
|
+--------U--+
| |
+-----------N-----+ -V-
| |
+--E-----+ +--R-
| | |
-A- +--L--+ -O-
| |
-F- -M-
R:
|
+-----U--+
| |
+-----------N--+ -V-
| |
+--E-----+ -O-
| |
-A- +--L--+
| |
-F- -M-
inserting T:
|
-T
inserting F:
|
+==T
‖
-F
inserting B:
|
+--F--+
| |
-B -T
inserting S:
|
+--F-----+
| |
-B +==T
‖
-S
inserting D:
|
+--F-----+
| |
+==D +==T
‖ ‖
-B -S
inserting I:
|
+=====S--+
‖ |
+--F--+ -T
| |
+==D -I
‖
-B
inserting Y:
|
+=====S-----+
‖ |
+--F--+ +==Y
| | ‖
+==D -I -T
‖
-B
inserting N:
|
+========S-----+
‖ |
+--F-----+ +==Y
| | ‖
+==D +==N -T
‖ ‖
-B -I
inserting Q:
|
+-----N-----+
| |
+--F--+ +--S-----+
| | | |
+==D -I -Q +==Y
‖ ‖
-B -T
inserting M:
|
+--------N-----+
| |
+--F-----+ +--S-----+
| | | |
+==D +==M -Q +==Y
‖ ‖ ‖
-B -I -T