Michael Drmota ; Helmut Prodinger - The height of q-Binary Search Trees

dmtcs:304 - Discrete Mathematics & Theoretical Computer Science, January 1, 2002, Vol. 5 - https://doi.org/10.46298/dmtcs.304
The height of q-Binary Search TreesArticle

Authors: Michael Drmota 1,2; Helmut Prodinger 3

  • 1 Department of Geometry [Vienna]
  • 2 Department of Geometry [TU Wien]
  • 3 The John Knopfmacher Centre for Applicable Analysis and Number Theory [Johannesburg]


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.

https://doi.org/10.46298/dmtcs.304
Source: HAL:hal-00958975v1
Volume: Vol. 5
Published on: January 1, 2002
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [en] binary search tree, q-analogue, height

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 445 times.
This article's PDF has been downloaded 614 times.