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; Helmut Prodinger 2

  • 1 Department of Geometry [Vienna]
  • 2 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 400 times.
This article's PDF has been downloaded 588 times.