On the silhouette of binary search trees

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Autoren

  • Rudolf Grübel

Organisationseinheiten

Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Seiten (von - bis)1781-1802
Seitenumfang22
FachzeitschriftAnnals of Applied Probability
Jahrgang19
Ausgabenummer5
PublikationsstatusVeröffentlicht - Okt. 2009

Abstract

A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.

ASJC Scopus Sachgebiete

Zitieren

On the silhouette of binary search trees. / Grübel, Rudolf.
in: Annals of Applied Probability, Jahrgang 19, Nr. 5, 10.2009, S. 1781-1802.

Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review

Grübel R. On the silhouette of binary search trees. Annals of Applied Probability. 2009 Okt;19(5):1781-1802. doi: 10.1214/08-AAP593
Grübel, Rudolf. / On the silhouette of binary search trees. in: Annals of Applied Probability. 2009 ; Jahrgang 19, Nr. 5. S. 1781-1802.
Download
@article{6b4f5a3103f946a6af5f6a0e4c052a46,
title = "On the silhouette of binary search trees",
abstract = "A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.",
keywords = "Analysis of algorithms, Contraction method, Convergence in distribution, External path length, Functional limit theorems",
author = "Rudolf Gr{\"u}bel",
year = "2009",
month = oct,
doi = "10.1214/08-AAP593",
language = "English",
volume = "19",
pages = "1781--1802",
journal = "Annals of Applied Probability",
issn = "1050-5164",
publisher = "Institute of Mathematical Statistics",
number = "5",

}

Download

TY - JOUR

T1 - On the silhouette of binary search trees

AU - Grübel, Rudolf

PY - 2009/10

Y1 - 2009/10

N2 - A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.

AB - A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.

KW - Analysis of algorithms

KW - Contraction method

KW - Convergence in distribution

KW - External path length

KW - Functional limit theorems

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

U2 - 10.1214/08-AAP593

DO - 10.1214/08-AAP593

M3 - Article

AN - SCOPUS:73949119948

VL - 19

SP - 1781

EP - 1802

JO - Annals of Applied Probability

JF - Annals of Applied Probability

SN - 1050-5164

IS - 5

ER -