Discrete Mathematics & Theoretical Computer Science, Vol 5 (2002)

Font Size:  Small  Medium  Large

The height of q-Binary Search Trees

Michael Drmota, Helmut Prodinger

Abstract


q-binary search trees are obtained from words, equipped with a geometric distribution instead of permutations. The average and variance of the heighth computated, based on random words of length n, as well as a Gaussian limit law.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page