Geodesic
Some estimates for the distribution of the height of a tree for digital searching
Diskretnaya Matematika, Tome 7 (1995) no. 3, pp. 8-18 
V. A. Vatutin; V. G. Mikhailov. Some estimates for the distribution of the height of a tree for digital searching. Diskretnaya Matematika, Tome 7 (1995) no. 3, pp. 8-18. http://geodesic.mathdoc.fr/item/DM_1995_7_3_a1/
@article{DM_1995_7_3_a1,
     author = {V. A. Vatutin and V. G. Mikhailov},
     title = {Some estimates for the distribution of the height of a tree for digital searching},
     journal = {Diskretnaya Matematika},
     pages = {8--18},
     year = {1995},
     volume = {7},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1995_7_3_a1/}
}
TY  - JOUR
AU  - V. A. Vatutin
AU  - V. G. Mikhailov
TI  - Some estimates for the distribution of the height of a tree for digital searching
JO  - Diskretnaya Matematika
PY  - 1995
SP  - 8
EP  - 18
VL  - 7
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DM_1995_7_3_a1/
LA  - ru
ID  - DM_1995_7_3_a1
ER  - 
%0 Journal Article
%A V. A. Vatutin
%A V. G. Mikhailov
%T Some estimates for the distribution of the height of a tree for digital searching
%J Diskretnaya Matematika
%D 1995
%P 8-18
%V 7
%N 3
%U http://geodesic.mathdoc.fr/item/DM_1995_7_3_a1/
%G ru
%F DM_1995_7_3_a1

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $\varkappa (T)$ be the height of a $q$-ary search tree $T$ constructed by the keys $K_1, K_2,\ldots,K_n$ each of which is a vector whose components belong to the alphabet $A=\{0,1,\ldots,q-1\}$. Assuming that the components of the vectors are independent and uniformly distributed on $A$, we find upper and lower estimates for the probabilities $\P\{\varkappa (t)\leq m\}$, $m=1,\ldots,n,$ with explicitly given constants. For typical values of $m $ the estimates obtained are better than those proved by Flajolet [2].