The height of q-Binary Search Trees

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.

Keywords

• height
• binary search tree
• q-analogue
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]