article · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 1996

Patterns in random binary search tree

Flajolet, Philippe, Gourdon, Xavier, Martínez Parra, Conrado

Cited by 0Open access

Abstract

In a randomly grown binary search tree (BST) of size n, any fixed\n\t\t\t\t pattern occurs with a frequency that is on average proportional to\n\t\t\t\t n. Deviations from the average case are highly unlikely and well\n\t\t\t\t quantified by a Gaussian law. Trees with forbidden patterns occur with\n\t\t\t\t an exponentially small probability that is characterized in terms of\n\t\t\t\t Bessel functions. The results obtained extend to BSTs a type of\n\t\t\t\t property otherwise known for strings and combinatorial tree\n\t\t\t\t models. They apply to paged trees or to quicksort with halting on\n\t\t\t\t short subfiles. As a consequence, various pointer saving strategies\n\t\t\t\t for maintaining trees obeying the random BST model can be precisely\n\t\t\t\t quantified. The methods used are based on analytic models, especially\n\t\t\t\t bivariate generating functions subjected to singularity perturbation\n\t\t\t\t asymptotics.

Cite this paper

APA 7

Flajolet, P., Gourdon, X., & Martínez Parra, C. (1996). Patterns in random binary search tree. LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

MLA 9

Flajolet, Philippe, et al. “Patterns in random binary search tree.” LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas), 1996.

Chicago

Flajolet, Philippe, Xavier Gourdon, and Conrado Martínez Parra. 1996. “Patterns in random binary search tree.” LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

Harvard

Flajolet, P., Gourdon, X. and Martínez Parra, C. (1996) ‘Patterns in random binary search tree’, LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas).

BibTeX

@article{flajolet1996patterns,
  title = {{Patterns in random binary search tree}},
  author = {Flajolet, Philippe and Gourdon, Xavier and Martínez Parra, Conrado},
  journal = {LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas)},
  year = {1996}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.