- •Глава 6. Алгоритмы поиска
- •6.1. Последовательный поиск
- •6.2. Бинарный поиск в упорядоченной таблице
- •6.3. Поиск Фибоначчи в упорядоченной таблице
- •6.4. Поиск по бинарному дереву
- •6.4.1. Бинарное дерево поиска
- •6.4.2. Поиск и вставка в дереве поиска.
- •6.4.3.Удаление из дерева поиска
- •6.4.4. Оптимальное бинарное дерево поиска
- •6.5. Префиксный цифровой поиск
- •6.5.1. Префиксное дерево
- •6.5.2. Алгоритм префиксного поиска
- •6.6. Поиск по вторичным ключам
6.4.3.Удаление из дерева поиска
Пусть при поиске узла, подлежащего удалению, определено значение указателя на него с помощью приведённого выше алгоритма поиска и вставки. Следует различать три случая:
1) узел не имеет ни одного потомка;
2) узел имеет только одного потомка;
3) узел имеет обоих потомков.
В первом случае обнуляется ссылка на узел его родителя, и область памяти, занятая удаляемым узлом, возвращается в пул свободной памяти. Во втором случае ссылка нав родительском узле заменяется ссылкой на. При наличии уобоих потомков следует найти непосредственно следующий за ним по порядку ключей узел— самый левый в правом поддереве, заменить содержимое узла(ключевое поле и поля данных) на содержимое узла, после чего удалить узелпо схеме первого или второго случая, поскольку.
Алгоритм удаления узла из дерева поиска содержит следующие этапы.
╔
Ш1. Проверка пустоты ссылки удаляемого элемента:
;
если , то
;
перейти к Ш4.
Ш2. Поиск преемника удаляемого элемента:
;
если , то
;
;
перейти к Ш4.
Ш3. Поиск пустой ссылки :
1) ;
2) если , то
;
возврат к 1).
3) если , то
;
;
;
.
Ш4. Область, занятая удаляемым узлом , переходит в пул
свободной памяти.
╚
6.4.4. Оптимальное бинарное дерево поиска
Если накоплена статистика о частоте обращения к поиску для всех ключей, то возможна оптимизация структуры дерева, направленная на более быстрое нахождение более часто заказываемых ключей.
Пусть узлы дерева представляют имеющиеся в файле значения . Заданывероятностей, связанных с возможными положениями ключа поискаотносительно узлов:
,
где
—вероятность совпадения ключа поиска с ;
;
;
,
.
Таким образом, вероятности описывают ситуации удачного поиска, а— неудачного. В ряде задач целью поиска может служить как раз установление факта отсутствия ключа в списке, так что следует учитывать при оптимизации равноправно оба возможных исхода.
Если внутренний узел имеет уровень, то для его отыскания при удачном поиске потребуетсясравнений (начиная с корня дерева, имеющего нулевой уровень, и заканчивая сравнением с). Если— уровень- го внешнего узла, то при неудачном поиске потребуетсясравнений
Тогда математическое ожидание количества сравнений при поиске выражается числом
и называется ценой дерева. Требуется найти структуру дерева, при которой цена минимальна:
В этой задаче математического программирования управляемыми переменными, которые определяют структуру дерева, являются числа .
Дерево с минимальной ценой при заданных вероятностях называетсяоптимальным.
Оптимальные деревья обладают важным свойством: все поддеревья оптимального дерева также оптимальны. В [9] описан ряд основанных на динамическом программировании алгоритмов построения оптимальных деревьев.