9. Оптимальные деревья поиска
 

Существуют достаточно редкие случаи, когда имеется информация о вероятности обращений к отдельным ключам в дереве поиска. Такие вероятности могут быть получены только на основе статистических измерений, когда ключи поиска в дереве остаются неизменными.

Пусть известны вероятности p_i обращения к i-м узлам с ключами k_i. Мы хотим организовать бинарное дерево поиска таким образом, чтобы минимизировать математическое ожидание числа сравнений при поиске. Для этого припишем каждому узлу в определении длины пути вес, равный вероятности обращения к этому узлу. Тогда взвешенная длина пути дерева есть сумма всех путей от корня к каждому узлу, умноженных на вероятности обращения к этому узлу:

Остается минимизировать эту взвешенную длину пути при данном распределении вероятностей. Очевидно, что узлы с большими вероятностями должны располагаться ближе к корню дерева, но тогда оптимальным может оказаться не сбалансированное, а вырожденное дерево.

Однако такой подход учитывает только удачный поиск, т.е. поиск только существующих в дереве ключей. Если же множество ключей дерева является подмножеством ключей поиска (аргументов поиска), то наличие ключей поиска, приво-дящих к неудачному поиску, повлияет на структуру оптимального дерева поиска. Такая ситуация присуща, например, трансляторам, когда среди слов исходной программы отыскиваются зарезервированные слова, вероятность появления которых в программе можно установить. В таких случаях нахождение оптимальных деревьев поиска усложняется. (Существует метод динамического программирования для построения оптимального дерева).