Search trees: Metric aspects and strong limit theorems

Research output: Contribution to journalArticleResearchpeer review

Authors

  • Rudolf Grübel
View graph of relations

Details

Original languageEnglish
Pages (from-to)1269-1297
Number of pages29
JournalAnnals of Applied Probability
Volume24
Issue number3
Publication statusPublished - Jun 2014

Abstract

We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree.

ASJC Scopus subject areas

Cite this

Search trees: Metric aspects and strong limit theorems. / Grübel, Rudolf.
In: Annals of Applied Probability, Vol. 24, No. 3, 06.2014, p. 1269-1297.

Research output: Contribution to journalArticleResearchpeer review

Grübel R. Search trees: Metric aspects and strong limit theorems. Annals of Applied Probability. 2014 Jun;24(3):1269-1297. doi: 10.48550/arXiv.1209.2546, 10.1214/13-AAP948
Grübel, Rudolf. / Search trees : Metric aspects and strong limit theorems. In: Annals of Applied Probability. 2014 ; Vol. 24, No. 3. pp. 1269-1297.
Download
@article{870c6b312bd74e4b967f83b00d323b68,
title = "Search trees: Metric aspects and strong limit theorems",
abstract = "We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree.",
author = "Rudolf Gr{\"u}bel",
note = "Copyright {\textcopyright} 2014 Institute of Mathematical Statistics",
year = "2014",
month = jun,
doi = "10.48550/arXiv.1209.2546",
language = "English",
volume = "24",
pages = "1269--1297",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "3",

}

Download

TY - JOUR

T1 - Search trees

T2 - Metric aspects and strong limit theorems

AU - Grübel, Rudolf

N1 - Copyright © 2014 Institute of Mathematical Statistics

PY - 2014/6

Y1 - 2014/6

N2 - We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree.

AB - We consider random binary trees that appear as the output of certain standard algorithms for sorting and searching if the input is random. We introduce the subtree size metric on search trees and show that the resulting metric spaces converge with probability 1. This is then used to obtain almost sure convergence for various tree functionals, together with representations of the respective limit random variables as functions of the limit tree.

UR - http://www.scopus.com/inward/record.url?scp=84899549401&partnerID=8YFLogxK

U2 - 10.48550/arXiv.1209.2546

DO - 10.48550/arXiv.1209.2546

M3 - Article

AN - SCOPUS:84899549401

VL - 24

SP - 1269

EP - 1297

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 3

ER -