Geodesic
The Height of List-tries and TST
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

We characterize the asymptotics of heights of the trees of de la Briandais and the ternary search trees (TST) of Bentley and Sedgewick. Our proof is based on a new analysis of the structure of tries that distinguishes the bulk of the tree, called the $\textit{core}$, and the long trees hanging down the core, called the $\textit{spaghettis}$. 
@article{DMTCS_2007_special_253_a18,
     author = {Broutin, N. and Devroye, L.},
     title = {The {Height} of {List-tries} and {TST}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3536},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3536/}
}
TY  - JOUR
AU  - Broutin, N.
AU  - Devroye, L.
TI  - The Height of List-tries and TST
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3536/
DO  - 10.46298/dmtcs.3536
LA  - en
ID  - DMTCS_2007_special_253_a18
ER  - 
%0 Journal Article
%A Broutin, N.
%A Devroye, L.
%T The Height of List-tries and TST
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3536/
%R 10.46298/dmtcs.3536
%G en
%F DMTCS_2007_special_253_a18
Broutin, N.; Devroye, L. The Height of List-tries and TST. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3536. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3536/

Cité par Sources :