Final Solutions
(1) The initial balance conditions are:
a: R b: L c: N d:R e: L f: L g: N
The deletion causes node d to be right-critical. Since node f is L-high, we
require a "grand-child" promotion to stabilize the situation. Node e is
promoted to the root, and E becomes the right subtree of d (now the left
child of e), F becomes the left subtree of f. The final balance conditions are
all N, except f which is R.
(2) It was surprising how few students realized that this could be solved
with the (preorder) "treesearch" model. If there are k nodes in the LST of the
root, then the root is the k+1st key in the sorted order.
char find_rth(bt b, int r) {
/* assume r > 0; returns rth smallest key in the BST */
/* returns null if r is greater than the number of nodes */
if(b != NULL) {
if(b->numLST == r-1) return b->key; /* root is the rth
if(b->numLST > r-1) return find_rth(b->L, r);
/* if at least r nodes in LST, then look for the rth */
return find_rth(b->R, r - (b->numLST + 1));
/* look in RST, subtracting 1 (for the root) + numLST */
}
return NULL;
}
insertBST contains an error (mine), though virtually nobody noticed it. you
can't build a tree by passing a copy of the root pointer. the code should read:
void insertBST(bt *p, char c) {
/* p is a pointer to a pointer */
if(*p != NULL) {
if((*p)->key > c) {
(*p)->numLST++;
insertBST(&((*p)->L), c);
}
else insertBST(&(*p)->R, c);
}
else *p = initNode(c);
}
and is called (say) with:
char c = 'x';
bt b = NULL;
insertBST(&b, c);
(3) First the pCount and sCount fields should be initialized to zero, and then
the adjacency list for each vertex is scanned, incrementing the counts as
appropriate.
void initCounts(graph g) {
int i;
edge *ep;
for(i = 1; i <= g.numVerts; i++)
g.vArray[i].pCount = g.vArray[i].sCount = 0;
for(i = 1; i <= g.numVerts; i++) {
ep = g.vArray[i].head;
while(ep != NULL) {
g.vArray[i].sCount++;
g.vArray[ep->neighbor].pCount++;
ep = ep->next;
}
}
}
(4) first the incremental method beginning with SYADILOH:
SY -> YS -> YSA -> YSAD -> YSADI -> YSLDIA -> YSODIAL -> YSOHIALD
for the "in-place" merging method:
SYADILOH -> SYAHILOD -> SYOHILAD -> YSOHILAD
since the height of an AVL tree is O(lgn), then the insert and remove costs
are O(lgn). insert "means" maintain an AVL tree under insertion, while remove
"means" remove the smallest (largest) and restore the AVL tree. the costs are
of the same order as the binary heap - but the overhead is much greater
(stack) and the coding much more complex for the AVL implementation of the
heap.
(5) The BST "generated" by this modified QS is:
6
/ \
2,5 16
/ \
14 17
/
7
\
10
/ \
8 13, 11
producing the array 2 5 6 7 8 10 13 11 14 16 17. As an example the root or
the tree is determined by the first pass over the array, which transforms the
array to 6 5 2 16 14 11 17 13 8 10 7, and then the pivot (6) is swapped with
2 to get this array: 2 5 6 16 14 11 17 13 8 10 7. The left subtree is not
processed by QS (too small), and 16 becomes the pivot for the QSing of the
right subtree.
To "clean-up" the partially sorted array above, insertion sort needs one
compare for each of 2, 5, 6, 7, 8, 13, two compares for 11, and then one each
for 14, 16, and 17, for a total of 6 + 2 + 3 = 11 compares.
For the modified mergesort:
6 13 10 16 14 11 17 5 8 2 7
/ \
6 13 10 16 14 11 17 5 8 2 7
/ \ / \
6 13 10 16 14 11 17 5 8 2 7
insertionsort -> | | | |
6 13 10 14 16 5 11 17 2 7 8
\ / \ /
6 10 13 14 16 2 5 7 8 11 17
\ /
2 5 6 7 8 10 11 13 14 16 17
the merge of 6, 13 with 10, 14, 16 requires three compares, that of 5, 11, 17
with 2, 7, 8 requires four compares, and the final merge requires ten compares
(a worst case), for a total of 17 comparisons. of course, since we can only
merge sorted lists, the insertion sort must appear as an "else" clause: we
can't "clean-up" at the end as in QS.
(6) Vertex #of preds ts # et lt
A 0 1 0 0
B 3 4 9 9
C 3 7 15 15
D 1 3 4 4
E 3 6 10 13
F 0 2 0 0
G 2 5 9 11
the completion time is 15. the critical paths are FBC and ADBC. since BC is
the only common edge, we can reduce the cost of both critical paths by reducing
the weight on BC. However, it can't be reduced by more than 2, since any
further reduction causes a new critical path (ADEG, completion time = 13) and
further reductions in BC accomplish nothing.
(7) For the binomial queue, the structure is determined by the number of nodes.
With 12 nodes, we must have a binomial tree of index two and one of index
three, and the postorder sequence is enough to label the nodes.
C G
/ \ / | \
Q I K O N
| | / \
U S R I
|
T
H -> H -> A H -> P H -> P -> S P -> S P
| | | | / \ / \ | / \
E E A E A H A H O A H
| | |
E E E
-> R S P -> T S P -> T P -> T
| / \ | | / \ / \ / \ / | \
O A H R O A H R S A H R S P
| | | | | / \
E E O E O A H
|
E
too simple: removing T simply leaves a binomial queue of its subtrees.
merging in a new node is like binary addition. if the low order bit is 0, there
are no carries, and the cost is 0. if the low order bit is 1, there is a carry,
but if the next bit is 0, the carry stops, and the cost is one. and so forth.
so, the average cost - over all possible values of n - is like coin-tossing.
E(xpected number of merges) = (1/2)0 + (1/2)(1 + E)
so E = 1.
at any rate, O(1) (constant cost, independent of n) receives full credit.