Some estimates for the distribution of the height of a tree for digital searching

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].