|
|
Посетить узел p | |
| 2. Левое поддерево | If LEFT(p) then | |
| 3. Правое поддерево | If RIGHT(p) then |
Алгоритм на псевдокоде для общей схемы бинарного дерева имеет следующий вид:
пустой стек
(корень, 1)
while пусто do
begin
case i of
begin (p, 3); операция 2 end
begin (p, 2); операция 1 end
begin операция 3 end
end
end
Упрощенная конкретизация алгоритма для симметричного обхода будет выглядеть так:
пустой стек
(корень, 1)
while пусто do
begin
if then
begin
(p, 2);
If LEFT(p) then end
else
begin
Посетить узел p
If RIGHT(p) then end
end
В настоящем разделе вводится понятие дерева поиска и рассматриваются операции над множествами, которые можно эффективно выполнять, используя представление множеств с помощью деревьев поиска.
Рассмотрим следующую задачу на множестве S, которая часто возникает при работе с множествами. В множество вставляются и из него удаляются элементы. Нам может понадобиться узнать, принадлежит ли данный элемент множеству S или, например, каков в данный момент наименьший элемент в S. Мы считаем, что элементы добавляются в S из большого универсального множества, линейно упорядоченного отношением . Эту задачу можно сформулировать в общем виде как выполнение последовательности, состоящей из операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ и MIN. Структурой данных, пригодной для всех этих операций, является дерево двоичного поиска.
Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом так, что
1) для каждого узла u из левого поддерева узла v,
2) для каждого узла u из правого поддерева узла v,
3) для каждого элемента существует в точности один узел v, для которого .
Из условий 1 и 2 следует, что метки дерева поиска упорядочены в соответствии с симметричным порядком.
Чтобы выяснить, принадлежит ли a множеству S, представленному дереву поиска, надо сравнить a с меткой корня. Если метка корня равна a, то . Если a меньше метки корня, то надо перейти к левому поддереву корня (если оно есть). Если a больше метки корня, то надо перейти к правому поддереву корня (если оно есть). Если a присутствует в дереве, его местоположение будет обнаружено. В противном случае процесс окончится, когда надо будет найти несуществующее левое или правое поддерево.
Алгоритм поиска элемента a в множестве реализуется следующей рекурсивной процедурой ПОИСК:
ПОИСК(a, r) {вызов процедуры ПОИСК, r – корень дерева}
procedure ПОИСК(a, v)
begin
if then выдать ответ «да»
else
if a<l(v) then
if v имеет левого сына w then ПОИСК(a,w)
else выдать ответ «нет»
else
if v имеет правого сына w then ПОИСК(a, w)
else выдать ответ «нет»
end
Алгоритм выдает ответ «да», если элемент a найден, и ответ «нет» в противном случае.
Алгоритм легко модифицировать, чтобы он выполнял операцию ВСТАВИТЬ(a). Если дерево пусто, строится корень с меткой a. Если дерево непусто, а элемент, который нужно вставить, не найден в дереве, значит, не удается найти сына. Поэтому вместо ответа «нет» в алгоритме строится новый узел там, где должен был быть отсутствующий сын.
Деревья двоичного поиска удобны также для выполнения операций MIN и УДАЛИТЬ. Для нахождения наименьшего элемента в дереве двоичного поиска просматривается путь , где - корень дерева, - левый сын узла , , и у узла нет левого сына. Метка в узле является наименьшим элементом в дереве.
Реализовать операцию УДАЛИТЬ немного сложнее. Предположим, что элемент a, подлежащий удалению, расположен в узле . Возможны три случая:
1) 1) - лист; в этом случае удаляется из дерева;
2) у в точности один сын; в этом случае делаем отца узла отцом его сына, тем самым удаляя из дерева (если - корень, то его сына делаем новым корнем);
3) у два сына; в этом случае находим в левом поддереве узла наибольший элемент b, рекурсивно удаляем из этого поддерева узел, содержащий b, и метим узел элементом b (Заметим, что среди элементов, меньших a, b будет наибольшим элементом).
Одно выполнение любой из операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЬ и MIN можно осуществить за время O(n).
1. Шень А. Программирование: теоремы и задачи. – 3-е изд. – М.: МЦНМО, 2007. – 296 с.
2. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007. – 400 с.