|
Дискретная математика, 1995, том 7, выпуск 3, страницы 8–18
(Mi dm584)
|
|
|
|
Некоторые оценки для распределения высоты дерева цифрового поиска
В. А. Ватутин, В. Г. Михайлов
Аннотация:
Пусть $\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.
Статья поступила: 02.12.1993
Образец цитирования:
В. А. Ватутин, В. Г. Михайлов, “Некоторые оценки для распределения высоты дерева цифрового поиска”, Дискрет. матем., 7:3 (1995), 8–18; Discrete Math. Appl., 5:4 (1995), 289–300
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm584 https://www.mathnet.ru/rus/dm/v7/i3/p8
|
Статистика просмотров: |
Страница аннотации: | 541 | PDF полного текста: | 132 | Первая страница: | 3 |
|