Обход и прошивка бинарных деревьев. Понятие о прошивке бинарного дерева

Страницы работы

4 страницы (Word-файл)

Содержание работы

Лекция 11. Обход и прошивка бинарных деревьев.

Существует много приложений, в которых требуется выполнение некоторой определенной операции Р над каждой вершиной дерева. операцию Р в этом случае можно мыслить как параметр некоторой более общей задачи – «посещения» всех вершин или  «обхода дерева». Если удается найти  некоторое правило, обеспечивающее однозначную упорядоченность вершин при всяком обходе, то получаем аналог линейной упорядоченности для соответствующего класса нелинейных структур. В этом случае для многих алгоритмов работы с деревом справедливы утверждения: переход к следующей вершине, переход к предыдущей вершине. Возможность введения принципа упорядочения основана на двух положениях:

-  дерево является рекурсивно определяемой структурой,

-  поддеревья для каждой вершины упорядочены.

Отсюда вытекает три принципа упорядоченного обхода позиционного бинарного дерева (рис.11.1):

-  нисходящий обход (R, A, B);

-  восходящий обход (А, B, R);

-  смешанный (A, R, B).

R

 


A                             B

Левое                         Правое поддерево                     поддерево

Рисунок 11.1

Пусть t – указатель на корень бинарного дерева, а

Down (t:Ptr)

Процедура нисходящего обхода. Блок схема соответствующего рекурсивного алгоритма приведена на рис.11.2.

начало

 


                      да

         t=NULL                конец

 


P(t)

 


      down(t^.left)         down(t^.right)

Рисунок 11.2

Вместо рекурсивной процедуры может быть использован итерационный алгоритм со стеком для хранения ссылок на обнаруженные, но не обработанные ветви дерева. Пример соответствующего обхода с данными об изменении стека ссылок в процессе реализации итерационного алгоритма представлен на рис.11.3.

A                           Состояние стека

                                             при обходе дерева

B               H                 H

                                             E H

M E H

                                             E H

C          E      Y        X            F H

                                             H

X

D      M    G      F

Рисунок 11.3.

Смешанный подход реализуется рекурсивной процедурой:

-  смешанный обход левого поддерева,

-  обработка корня дерева,

-  смешанный обход правого поддерева.

Использование смешанного обхода, бинарного дерева поиска (рис.11.4), построенного для последовательности чисел:

13, 25, -7, 4, 15, 161, 151, 41, 22.

               13

-7                  25

 


4        15           161

 


22

151

41

Рисунок 11.4

Приводит к упорядочению исходной последовательности по возрастанию. Нетрудно показать, что это справедливо для любого дерева поиска, и на этом может основываться достаточно эффективный алгоритм сортировки массивов.

Понятие о прошивке бинарного дерева.

Рассматривая предложенное выше связанное представление бинарных деревьев, легко обнаружить, что в нем имеется много указателей типа NULL. Используя индукцию, можно показать, что в представлении бинарного дерева с N вершинами при использовании связанного представления дерева N+1 указателей имеют значение NULL.

Это не занятое пространство можно использовать для некоторой модификации ранее приведенного представления позиционных бинарных деревьев.. В предлагаемом представлении пустые указатели заменяются указателями нитями, которые адресуют вершины дерева, не связанные с данной  ребрами, но следующие за ней при установленном варианте обхода (рис.11.5)

A

lp

info

rp

B

E

lp

info

rp

lp

info

rp

C

D

F

G

PD

info

PE

info

lp

info

rp

info

H

I

info

PI

info

PG

Рисунок 11.5.

То есть не используемое значение указателя можно заменить адресом, указывающим на вершину, которая следует за данной в соответствии с тем порядком обхода, для которого прошивалось дерево. Различие связей и нитей можно показать через дополнительный флаг адреса.

Прошивка дерева кроме экономии памяти решает один принципиально важный вопрос. Она позволяет обходить дерево не с первой вершины, а с текущей. Тем самым некоторая операция может выполняться для некоторого подмножества упорядоченного множества вершин бинарного дерева.

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

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

Двоичные деревья часто употребляются для представления множества данных, среди которых идет поиск элементов по уникальному ключу.

Если дерево организовано так, что для каждой вершины Р справедливо утверждение, что все ключи левого поддерева Р меньше ключа key данной вершины, а все ключи правого поддерева больше key, то такое дерево принято называть деревом поиска.

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

Определим тир Ptr следующим образом:

Type Ptr=^retro;

Retro=record

Key:integer;

Qt:integer;

Lp:Ptr;

Rp:Ptr

End;

На рис.11.6 представлена блок-схема модификации бинарного дерева при анализе очередного слова в частотном словаре с идентифицирующим кодом x:

Search (x:integer, var p: Ptr).

Рисунок 11.6.

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

Рисунок 11.7.

Все детали приводятся в рекурсивном алгоритме соответствующей процедуры delete:

Delete (x:integer; var

Похожие материалы

Информация о работе