Exact and asymptotic distributions in digital and binary search trees
RAIRO-Theor. Inf. Appl., 21 4 (1987) 479-495
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Asymptotic expectation of protected node profile in random digital search trees
M. Javanian, R. Imany Nabiyyi, J. Toofanpour and M. Q. Vahidi-AslJournal of Applied Mathematics, Statistics and Informatics 18 (1) 43 (2022)
https://doi.org/10.2478/jamsi-2022-0004
Node profiles of symmetric digital search trees: Concentration properties
Michael Drmota, Michael Fuchs, Hsien‐Kuei Hwang and Ralph NeiningerRandom Structures & Algorithms 58 (3) 430 (2021)
https://doi.org/10.1002/rsa.20979
The expected profile of digital search trees
Michael Drmota and Wojciech SzpankowskiJournal of Combinatorial Theory, Series A 118 (7) 1939 (2011)
https://doi.org/10.1016/j.jcta.2011.04.001
Branching random walks on binary search trees: convergence of the occupation measure
Eric FeketeESAIM: Probability and Statistics 14 286 (2010)
https://doi.org/10.1051/ps:2008035
Estimation of search tree size and approximate counting: A likelihood approach
Florian Dennert and Rudolf GrübelStatistics & Decisions 26 (4) 263 (2009)
https://doi.org/10.1524/stnd.2008.1016
The left–right-imbalance of binary search trees
Markus Kuba and Alois PanholzerTheoretical Computer Science 370 (1-3) 265 (2007)
https://doi.org/10.1016/j.tcs.2006.10.033
Renewals for exponentially increasing lifetimes, with an application to digital search trees
Florian Dennert and Rudolf GrübelThe Annals of Applied Probability 17 (2) (2007)
https://doi.org/10.1214/105051606000000862
Rounding of continuous random variables and oscillatory asymptotics
Svante JansonThe Annals of Probability 34 (5) (2006)
https://doi.org/10.1214/009117906000000232
The Guessing Secrets problem: a probabilistic approach
Alberto Del Lungo, Guy Louchard, Claudio Marini and Franco MontagnaJournal of Algorithms 55 (2) 142 (2005)
https://doi.org/10.1016/j.jalgor.2004.03.001
Mixed Poisson approximation of node depth distributions in random binary search trees
Rudolf Grübel and Nikolče StefanoskiThe Annals of Applied Probability 15 (1A) (2005)
https://doi.org/10.1214/105051604000000611
Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees
Michael Drmota and Hsien-Kuei HwangSIAM Journal on Discrete Mathematics 19 (1) 19 (2005)
https://doi.org/10.1137/S0895480104440134
Distances and Finger Search in Random Binary Search Trees
Luc Devroye and Ralph NeiningerSIAM Journal on Computing 33 (3) 647 (2004)
https://doi.org/10.1137/S0097539703424521
The height of a binary search tree: the limiting distribution perspective
Charles Knessl and Wojciech SzpankowskiTheoretical Computer Science 289 (1) 649 (2002)
https://doi.org/10.1016/S0304-3975(01)00387-5
https://doi.org/10.1002/9781118032770.biblio
Distinctness of compositions of an integer: A probabilistic analysis
Paweł Hitczenko and Guy LouchardRandom Structures & Algorithms 19 (3-4) 407 (2001)
https://doi.org/10.1002/rsa.10008
Martingales and large deviations for binary search trees
Jean Jabbour‐HattabRandom Structures & Algorithms 19 (2) 112 (2001)
https://doi.org/10.1002/rsa.1023
Probabilistic analysis of adaptative sampling
Guy LouchardRandom Structures & Algorithms 10 (1-2) 157 (2000)
https://doi.org/10.1002/(SICI)1098-2418(199701/03)10:1/2<157::AID-RSA8>3.0.CO;2-U
Asymptotic Behavior of the Height in a Digital Search Tree and the Longest Phrase of the Lempel--Ziv Scheme
Charles Knessl and Wojciech SzpankowskiSIAM Journal on Computing 30 (3) 923 (2000)
https://doi.org/10.1137/S0097539799356812
Probabilistic Methods for Algorithmic Discrete Mathematics
Luc DevroyeAlgorithms and Combinatorics, Probabilistic Methods for Algorithmic Discrete Mathematics 16 249 (1998)
https://doi.org/10.1007/978-3-662-12788-9_7
Average Profile of the Generalized Digital Search Tree and the Generalized Lempel--Ziv Algorithm
Guy Louchard, Wojciech Szpankowski and Jing TangSIAM Journal on Computing 28 (3) 904 (1998)
https://doi.org/10.1137/S0097539796301811
Universal Limit Laws for Depths in Random Trees
Luc DevroyeSIAM Journal on Computing 28 (2) 409 (1998)
https://doi.org/10.1137/S0097539795283954
Data Structures' Maxima
G. Louchard, Claire Kenyon and R. SchottSIAM Journal on Computing 26 (4) 1006 (1997)
https://doi.org/10.1137/S0097539791196603
1063 (1995)
https://doi.org/10.1016/B978-044488002-4/50024-5
262 (1995)
https://doi.org/10.1109/DCC.1995.515516
Asymptotic behavior of the Lempel-Ziv parsing scheme and digital search trees
Philippe Jacquet and Wojciech SzpankowskiTheoretical Computer Science 144 (1-2) 161 (1995)
https://doi.org/10.1016/0304-3975(94)00298-W
On the variance of a class of inductive valuations of data structures for digital search
Werner SchachingerTheoretical Computer Science 144 (1-2) 251 (1995)
https://doi.org/10.1016/0304-3975(94)00306-4
Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm
G. Louchard and W. SzpankowskiIEEE Transactions on Information Theory 41 (2) 478 (1995)
https://doi.org/10.1109/18.370149
Digital Search Trees Again Revisited: The Internal Path Length Perspective
Peter Kirschenhofer, Helmut Prodinger and Wojciech SzpankowskiSIAM Journal on Computing 23 (3) 598 (1994)
https://doi.org/10.1137/S0097539790189368
Search costs in quadtrees and singularity perturbation asymptotics
P. Flajolet and T. LafforgueDiscrete & Computational Geometry 12 (2) 151 (1994)
https://doi.org/10.1007/BF02574372
On random cartesian trees
Luc DevroyeRandom Structures & Algorithms 5 (2) 305 (1994)
https://doi.org/10.1002/rsa.3240050205
Analytic variations on quadtrees
Philippe Flajolet, Gaston Gonnet, Claude Puech and J. M. RobsonAlgorithmica 10 (6) 473 (1993)
https://doi.org/10.1007/BF01891833
Dynamic algorithms in D.E. Knuth's model: a probabilistic analysis
G. Louchard, B. Randrianarimanana and R. SchottTheoretical Computer Science 93 (2) 201 (1992)
https://doi.org/10.1016/0304-3975(92)90330-I
CAAP '92
François Bergeron, Philippe Flajolet and Bruno SalvyLecture Notes in Computer Science, CAAP '92 581 24 (1992)
https://doi.org/10.1007/3-540-55251-0_2
Generalized Digital Trees and Their Difference—Differential Equations
Philippe Flajolet and Bruce RichmondRandom Structures & Algorithms 3 (3) 305 (1992)
https://doi.org/10.1002/rsa.3240030309
Fundamentals of Computation Theory
Bogdan S. Chlebus and Imrich VrťoLecture Notes in Computer Science, Fundamentals of Computation Theory 529 190 (1991)
https://doi.org/10.1007/3-540-54458-5_63
Fundamentals of Computation Theory
Guy Louchard, Claire Kenyon and René SchottLecture Notes in Computer Science, Fundamentals of Computation Theory 529 339 (1991)
https://doi.org/10.1007/3-540-54458-5_78
On the height of random m‐ary search trees
Luc DevroyeRandom Structures & Algorithms 1 (2) 191 (1990)
https://doi.org/10.1002/rsa.3240010206
An Analysis of Randomd-Dimensional Quad Trees
Luc Devroye and Louise LaforestSIAM Journal on Computing 19 (5) 821 (1990)
https://doi.org/10.1137/0219057
Automata, Languages and Programming
G. Louchard, B. Randrianarimanana and R. SchottLecture Notes in Computer Science, Automata, Languages and Programming 372 521 (1989)
https://doi.org/10.1007/BFb0035781