Некоторые оценки для распределения высоты дерева цифрового поиска

Пусть $\varkappa(T)$ — высота $q$-арного дерева цифрового поиска $T$, построенного по ключам $K_1,\ldots,K_n$, каждый из которых является вектором с компонентами, принадлежащими алфавиту $\mathfrak A=\{0,1,\ldots,q-1\}$. В предположении, что компоненты векторов независимы и равномерно распределены на $\mathfrak A$, найдены оценки сверху и снизу для вероятностей $\boldsymbol{\mathsf P}\{\varkappa(T)\le m\}$, $m=1,\ldots,n$, с явно выписанными константами. Для типичных значений $m$ полученные соотношения являются асимптотически более точными по сравнению с утверждением, доказанным в [2].
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проект 93–011–1443.