Комбинаторные алгоритмы для программистов



             

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


Бинарный поиск в последовательно распределенной таблице ( алгоритм 13.4.) обеспечивает очень быстрое нахождение имен, которые являются средними точками на раннем этапе процесса деления пополам, именно имен, близких к вершине дерева

T(1,n)
. Таким образом, любое имя в таблице можно выбрать примерно за
\lg n
сравнений.

Четыре дерева бинарного поиска над множеством имен {A,B,C,D}

Рис. 13.1.  Четыре дерева бинарного поиска над множеством имен {A,B,C,D}

На практике в большинстве таблиц встречаются имена, к которым обращаются гораздо чаще, чем к другим, и "привилегированные" места в таблице разумно постараться использовать для наиболее часто вызываемых имен, а не для имен, выбранных для этих мест в результате бинарного поиска. Это невозможно осуществить для последовательно распределенных таблиц, поскольку место имени определяется его положением относительно естественного порядка имен в таблице. Введем структуру данных, легко приспосабливаемую как к месту бинарного поиска, так и к возможности выделять точки, в которых таблица делится на две части.

Деревом бинарного поиска над именами

x_1,x_2,\ldots,x_n

называется расширенное бинарное дерево, все внутренние узлы которого помечены различными именами из списка

x_1,x_2,\ldots,x_n
таким образом, что симметричный порядок узлов совпадает с естественным порядком. Каждый из
n + 1
внешних узлов соответствует промежутку в таблице. На рис. 13.1 показаны четыре различных дерева бинарного поиска на множестве имен
\{ A,B,C,D\}
. Деревья (а) и (b) - вырожденные, поскольку они по существу являются линейными списками, которые должны просматриваться последовательно.

Поиск имени

z
в дереве бинарного поиска осуществляется путем сравнения
z
с именем, стоящим в корне. Тогда

  1. Если корня нет (дерево пусто), то
    z
    в таблице отсутствует и поиск завершается безуспешно.
  2. Если
    z
    совпадает с именем в корне, поиск завершается успешно.
  3. Если
    z
    предшествует имени в корне, поиск продолжается ниже в левом поддереве корня.
  4. Если
    z
    следует за именем в корне, поиск продолжается ниже в правом поддереве корня.

Пусть бинарное дерево имеет вид, в котором каждый узел представляет собой тройку (LEFT, NAME, RIGHT), где LEFT и RIGHTсодержат указатели левого и правого сыновей соответственно, и NAME содержит имя, хранящееся в узле.


Содержание  Назад  Вперед