試題詳解

3. Consider a weight-biased leftist tree (WBLT). Let w(x) be the number of internal nodes in the subtrec with root x. Which of the following statemnents are false?
(A) The length of the rightmost path from intemal node x to an extemal node must be no greater than log₂(w(x)+1).
(B) The height of the subtree with root x must be no greater than 1og₂(w(x)+1).
(C) Combining two weight-based lettist trees with a total of n elements is done in time O(log n).
(D)A max WBLT is a max tree that for every interal node y, w(LefiChild(y) is greater than or equal to w(RightChild(y)).