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 Trees

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: height,binary search tree,q-analogue,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Share and export

Consultation statistics

This page has been seen 176 times.
This article's PDF has been downloaded 348 times.