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

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

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

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

Деревом бинарного поиска над именами называется расширенное бинарное дерево, все внутренние узлы которого помечены различными именами из списка таким образом, что симметричный порядок узлов совпадает с естественным порядком. Каждый из внешних узлов соответствует промежутку в таблице. На рис.1 показаны четыре различных дерева бинарного поиска на множестве имен . Деревья (а) и (b) - вырожденные, поскольку они по существу являются линейными списками, которые должны просматриваться последовательно.

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

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

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

Эта процедура нахождения имени в таблице, организованная в виде дерева бинарного поиска , показана в алгоритме 5. Отметим его сходство с алгоритмом 4 (бинарный поиск).

Алгоритм 5. Поиск в дереве бинарного поиска

Логарифмический поиск в динамических таблицах

Здесь мы рассмотрим организацию в виде деревьев для таблиц, в которых часто встречаются включения и исключения. Что происходит с временем поиска в дереве, которое модифицировалось путем включения и исключения? Если включенные и исключенные имена выбраны случайно, то оказывается, что в среднем время поиска мало изменяется; но в худшем случае поведение плохое - деревья могут вырождаться в линейные списки, поиск в которых нужно осуществлять последовательно. Проблема вырождения дерева в линейный список, приводящая к времени поиска вместо в практических применениях выражена более резко, чем это указывается теоретическим анализом. Такой анализ обычно предполагает, что включения и исключения появляются случайным образом, но на практике часто это не так.

Случайные деревья бинарного поиска. Как ведут себя деревья бинарного поиска без ограничений в качестве динамических деревьев? Другими словами, предположим, что дерево бинарного поиска меняется при случайных включениях и исключениях.

Для включения мы используем незначительную модификацию алгоритма 5. Если не было найдено, мы получаем для новую ячейку и связываем ее с последним узлом, пройденным во время безуспешного поиска . Соответствующее предложение нельзя однако просто добавить в конце алгоритма 13.5, поскольку при нормальном окончании цикла указатель не указывает больше на последний пройденный узел, а вместо этого имеет значение . В связи с этим мы должны производить включение до того, как выполняется предположение или ; мы можем осуществить это, сделав процедуру включения рекурсивной. Процедура выдает в качестве значения указатель на дерево, в которое добавлено . Таким образом, используется для включения в .

Алгоритм 6 Включение в дерево бинарного поиска

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

Лекция № 5