Оценка средней эффективности поисковых деревьев, построенных для произвольных наборов двоичных слов

Рассматривается задача построения двоичного поискового дерева для произвольного множества двоичных слов, которая находит широкое применение в информатике, в биологии и минералогии при построении определительных таблиц, а также в других областях. Известно, что задача построения дерева минимальной стоимости NP-полна, поэтому возникает задача поиска простых алгоритмов построения деревьев, близких к оптимальным. В статье показано, что даже простейший алгоритм строит поисковые деревья, в среднем близкие к оптимальным, и доказано, что среднее количество проверяемых узлов в оптимальном дереве отличается от естественной нижней границы — двоичного логарифма числа слов — не более, чем на 1{,}04.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 98–01–00772.