ON THE RICHNESS OF THE COLLECTION OF SUBTREES IN RANDOM BINARY SEARCH-TREES

The purpose of this paper is to settle two conjectures by Flajolet, Go urdon and Martinet (1996). We confirm that in a random binary tree on n nodes, the expected number of different subtrees grows indeed as The ta (n/log n). Secondly, if K is the largest integer such that all poss ible shapes of subtrees of cardinality less than or equal to K occur i n a random binary search tree, then we show that K similar to log n/lo g log n in probability. (C) 1998 Published by Elsevier Science B.V.