TAOCP 6.2.4 Exercise 8
Working
Exercise 8. [**] [HM87| Consider the generalization of tree insertion suggested by Muntz and Uzgalis, where each page can hold M keys. After N random items have been inserted into such a tree, so that there are N +1 external nodes, let b@ ) be the probability that an unsuccessful search requires k page accesses and that it “ends at an external node whose parent node belongs to a page containing j keys. d BO (z j= bY) zk is the corresponding generating function, prove that we have Bt Dz ) = 6j12 and
; N-j j+1 . BO (2) = we PO rere Piz), forl<j <M; N- 2 BO (z) = LZ BO, ~* BM) (z M N-1 Wm M+1 ,c-1 BQ i2)= Nal BY D(z) + Wo By (2).
Find the asymptotic behavior of Cy = ean BO'(1), the average number of page accesses per unsuccessful search. [Hint: Express the recurrence in terms of the matrix, 3 0. ... 0 22 3-4... 0 0 0 4... 0 0 0 QO..., M-1 0 0 O ... M41, -2
and relate Cy to an Nth degree polynomial in W(1).]
6.2.4 MULTIWAY TREES AQ1
Verified: no
Solve time: 4m26s
Working