Деревья оптимального поиска

Модуль "Деревья поиска" • урок 6 из 8 • ~6 минут

Суть урока. Если частоты обращений к разным ключам неравны, имеет смысл строить дерево оптимального поиска: частые ключи располагаются ближе к корню. Это минимизирует математическое ожидание числа сравнений при поиске (Σ Pi·Li). Дерево строится методами динамического программирования; оно может быть геометрически несбалансированным, но на практике будет работать быстрее АВЛ-дерева.

Деревья оптимального поиска: идея

АВЛ-деревья и красно-черные деревья гарантируют, что длина пути от корня до любого листа будет примерно одинаковой. Это удобно, если вероятность обращения ко всем элементам (ключам) одинакова. Но на практике это не так: к одним ключам обращаются очень часто, а к другим - крайне редко.

Если мы заранее знаем (или можем собрать статистику) о частоте обращений к каждому ключу, мы можем построить дерево оптимального поиска (Optimal Binary Search Tree). Главная идея заключается в том, чтобы разместить наиболее часто запрашиваемые ключи как можно ближе к корню (где путь поиска кратчайший), даже если это приведет к общему нарушению строгой геометрической сбалансированности дерева.

Цена поиска (Математическое ожидание)

Критерием оптимальности дерева является минимизация математического ожидания числа сравнений при поиске (среднего времени поиска). Если Pi - это вероятность обращения к узлу i, а Li - его уровень (расстояние от корня, где корень имеет уровень 1), то ожидаемая цена (стоимость) поиска по всему дереву вычисляется как сумма произведений Pi * Li для всех узлов.

Построение строго оптимального дерева для заданного набора частот - сложная вычислительная задача, которая решается методами динамического программирования (алгоритм Кнута) за время O(N3) или O(N2). Существуют также приближенные (жадные) алгоритмы, которые строят "почти оптимальные" деревья значительно быстрее.

Визуализация: сравнение сбалансированного и оптимального дерева

Рассмотрим ключи A, B, C с частотами запросов 70%, 20% и 10% соответственно. Идеально сбалансированное дерево здесь проигрывает: в корень выгоднее поднять не средний ключ, а самый частый.

Деревья оптимального поиска: у идеально сбалансированного дерева цена поиска 1,8, а у несбалансированной цепочки с частым ключом в корне 1,4
Геометрически несбалансированное дерево работает быстрее сбалансированного
А как в Python? В стандартной библиотеке C++ нет готового контейнера "дерево оптимального поиска", поскольку частоты запросов обычно неизвестны на этапе компиляции, а дерево со временем пришлось бы динамически перестраивать. Если оно необходимо, программист пишет его реализацию самостоятельно, используя двумерные массивы для таблицы алгоритма Кнута. В Python для задач, где одни ключи запрашиваются гораздо чаще других, хорошо подходят встроенные словари (dict). Их внутренняя организация (хеш-таблицы) в среднем дает сложность поиска O(1) вне зависимости от частоты запроса.

Коротко: главное

  • Деревья оптимального поиска строятся с учетом неравномерной частоты запросов к ключам.
  • Цель построения - минимизировать математическое ожидание числа шагов при поиске (поместить частые ключи ближе к корню).
  • Такое дерево может быть визуально (геометрически) несбалансированным, но при этом обеспечивать более высокую среднюю скорость поиска, чем строгое АВЛ-дерево.

Проверьте себя

Какой критерий используется для оценки "оптимальности" дерева поиска с неравными частотами запросов?

Как вам урок? Спасибо за отзыв!