…/p>

Посетить узел 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

5. Деревья поиска

В настоящем разделе вводится понятие дерева поиска и рассматриваются операции над множествами, которые можно эффективно выполнять, используя представление множеств с помощью деревьев поиска.

Рассмотрим следующую задачу на множестве 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).

6. Литература

6.1. Использованные источники информации

  1. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979. – 536 с.
  2. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980. – 480 с.
  3. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: Построение и анализ,. 2-е издание, - М.: Издательский дом "Вильямс", 2005. - 1296 с.

6.2. Дополнительная литература

1. Шень А. Программирование: теоремы и задачи. – 3-е изд. – М.: МЦНМО, 2007. – 296 с.

2. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.: Вильямс, 2007. – 400 с.

Бесплатный конструктор сайтов - uCoz