Geodesic
Average depth in a binary search tree with repeated keys
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006).

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

Random sequences from alphabet $\{1, \ldots,r\}$ are examined where repeated letters are allowed. Binary search trees are formed from these, and the average left-going depth of the first $1$ is found. Next, the right-going depth of the first $r$ is examined, and finally a merge (or 'shuffle') operator is used to obtain the average depth of an arbitrary node, which can be expressed in terms of the left-going and right-going depths. The variance of each of these parameters is also found. 
@article{DMTCS_2006_special_252_a20,
     author = {Archibald, Margaret and Cl\'ement, Julien},
     title = {Average depth in a binary search tree with repeated keys},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities},
     year = {2006},
     doi = {10.46298/dmtcs.3496},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3496/}
}
TY  - JOUR
AU  - Archibald, Margaret
AU  - Clément, Julien
TI  - Average depth in a binary search tree with repeated keys
JO  - Discrete mathematics & theoretical computer science
PY  - 2006
VL  - DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3496/
DO  - 10.46298/dmtcs.3496
LA  - en
ID  - DMTCS_2006_special_252_a20
ER  - 
%0 Journal Article
%A Archibald, Margaret
%A Clément, Julien
%T Average depth in a binary search tree with repeated keys
%J Discrete mathematics & theoretical computer science
%D 2006
%V DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3496/
%R 10.46298/dmtcs.3496
%G en
%F DMTCS_2006_special_252_a20
Archibald, Margaret; Clément, Julien. Average depth in a binary search tree with repeated keys. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006). doi : 10.46298/dmtcs.3496. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3496/

Cité par Sources :