Файл: Бинарные деревья - дерево бинарного поиска.doc

Оглавление

Бинарные деревья

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

Основные понятия и определения.

Древовидная структура (дерево) определяется следующим образом: дерево (tree) с базовым типом Т – это:

• либо пустая структура;

• либо узел типа Т, с которым связано конечное число древовидных структур, называемых поддеревьями.

Если с узлом связаны только два поддерева, то дерево называется бинарным. В дальнейшем мы будем рассматривать только бинарные деревья. Бинарное дерево изображено на рис.1.

Рис.1. Представление бинарного дерева

Терминология, применяемая для описания деревьев:

• узел (node) – это точка, где может возникнуть ветвь. На рис.1 узлы – это, например, 70 и 200 и т.д;

• корень (root) – “верхний” узел дерева. Для дерева на рис.1 это узел 100;

• ветвь (brunch) –отрезок, описывающий связь между двумя узлами;

• лист (leaf) – узел, из которого не выходят ветви, т.е. не имеющий поддеревьев. На рис.1 это узлы 10, 90, 58, 65, 170, 210;

• родительским (parent) – называется узел, который находится непосредственно над другим узлом;

• дочерним (child) – называется узел, который находится непосредственно под другим узлом;

• предки данного узла – это все узлы на пути вверх от данного узла до корня. Например, предками узла 60 являются узлы 55, 50, 70, 100;

• потомки – все узлы, расположенные ниже данного. Для узла 55 потомками являются узлы 60, 58, 65;

• внутренний узел (internal node) – узел, не являющийся листом;

• порядок узла (node degree) – количество его дочерних узлов;

• глубина (depth) узла – количество его предков плюс единица;

• глубина (высота) дерева –максимальная глубина всех узлов;

• длина пути к узлу – количество ветвей, которые нужно пройти, чтобы дойди от корня к данному узлу;

• длина пути дерева(длина внутреннего пути) – сумма длин путей всех его узлов.

Основные операции с бинарными деревьями

Узел бинарного дерева

При определении узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами и фактические данные (информационная часть), которые должны храниться в узле. При работе программы дерево может модифицироваться: добавляются или удаляются узлы, изменяется информационная часть. То есть дерево является динамической структурой. Узел дерева можно описать как переменную с фиксированной структурой, содержащую информационную часть (например, целое число) и две ссылки, указывающие на левое и правое поддеревья данного узла. Для этого подойдет тип – запись (record). Ссылка на пустое дерево должна быть равна nil.

Описание узла дерева может выглядеть так:

type PTree = ^TTree; // указатель на узел дерева

TTree = record

Inf: integer; // информационная часть (тип может быть любой и зависит от задачи)

Left, Right:PTree; // указатели на левое и правое поддеревья

end;

Обход бинарного дерева.

Для двоичных деревьев (и деревьев вообще) вводиться важная категория алгоритмов – алгоритмы обхода дерева. Такой алгоритм – это метод, позволяющий получить доступ к каждому узлу дерева один и только один раз.

Для каждого узла выполняются некоторые виды обработки информационной части (проверка, суммирование и т.п.), однако способ обхода не зависит от конкретных действий, выполняемых над узлом, и является общим для всех алгоритмов обработки узлов. Назовем действия, выполняемые над узлом, “Обработать корень”. При разных способах обхода дерева отдельные узлы посещаются в некотором определенном порядке.

Существуют три порядка, использующие обход в глубину:

1. Сверху вниз (PreOrder):

   • обработать корень;

   • обход левого поддерева;

   • обход правого поддерева;

2. Слева направо (InOrder):

   • обход левого поддерева;

   • обработать корень;

• обход правого поддерева;

3. Снизу вверх (PosOrder):

   • обход левого поддерева;

   • обход правого поддерева;

   • обработать корень.

Для дерева на рис.1 три способа обхода дают следующий результат:

Эти три метода легко представить в виде рекурсивных процедур, листинг которых представлен ниже. Во всех процедурах в качестве обработки корня используется вывод значения информационного поля на экран. В качестве параметра Tree:PTree в процедуры передается адрес корня бинарного дерева.

Листинг процедур обхода бинарного дерева.

Procedure PrintTree(Tree: PTree); // PreOrder

begin

if Tree<>nil then begin // если дерево не пустое, то

Writeln(‘Value = ‘,Tree^.inf); // обработать узел

PrintTree(Tree^.Left); // обход левого поддерева

PrintTree(Tree^.Right); // обход правого поддерева

end;

end;

Procedure PrintTree(Tree: PTree); // InOrder

begin

if Tree<>nil then begin // если дерево не пустое, то

PrintTree(Tree^.Left); // обход левого поддерева

Writeln(‘Value = ‘,Tree^.inf); // обработать узел

PrintTree(Tree^.Right); // обход правого поддерева

end;

end;

Procedure PrintTree(Tree: PTree); // PosOrder

begin

if Tree<>nil then begin // если дерево не пустое, то

PrintTree(Tree^.Left); // обход левого поддерева

PrintTree(Tree^.Right); // обход правого поддерева

Writeln(‘Value = ‘,Tree^.inf); // обработать узел

end;

end;

Ссылка Tree передается как параметр-значение, следовательно, является локальной переменной процедуры, получающей копию фактического параметра. При ее изменении фактический параметр не измениться (т.к. процедура работает с его локальной копией). Это означает, что при передаче в качестве фактического параметра адреса корня дерева, хранящая его переменная останется неизменной.

Упорядоченные деревья. Включение нового узла, поиск по дереву с включением

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

Построение упорядоченного дерева начинается с корня. Первое входящее значение помещается в корень дерева. Для последующих значений производиться сравнение со значением в очередном узле, начиная с корня. Если оно меньше (или равно) значению в узле, то переходим в левое поддерево, иначе – в правое. Эти переходы и сравнения продолжаются до тех пор, пока мы не придем к ссылке, которая равна nil. Тогда создается новый узел, заполняются его поля: информационное - новым значением, ссылки на левое и правое поддеревья пустым значение nil. Адрес нового узла передается в одно из ссылочных полей родительского узла. Для этого необходимо воспользоваться параметром-переменной. Этот алгоритм реализован в виде рекурсивной процедуры Insert.

Рис.2 Добавление нового узла в упорядоченное дерево.

Листинг процедуры добавления нового узла в упорядоченное дерево.

{Параметры процедуры: Tree – указатель на корень дерева, NewValue – значение для добавляемого узла.}

Procedure Insert(var Tree:PTree; NewValue:integer);

var Temp:PTree;

begin

if Tree = nil then begin

new(Tree); // создание нового узла, в том числе и корневого

Tree^.inf:=NewValue; Tree^.Left:=nil; Tree^.Right:=nil; // заполнение полей

end

else

if NewValue <=Tree^.inf then

Insert(Tree^.left,NewValue)

{переход к левому поддереву}

else

Insert(Tree^.Right,NewValue)

{переход к правому поддереву}

end;

Следует отметить, что в процедуре Insetr параметр Tree передается как параметр-переменная, а не как параметр-значение в процедуре PrintTree. Это очень важно, так как в случае включения нового узла параметру-переменной Tree присваивается адрес нового узла и через нее передает в родительский узел ссылкы (адрес) на включенный узел, изменяя старое значение равное nil. Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево. В программе необходимо описать указатель на корень дерева (например, var Root:PTree;). В начале программы необходимо провести инициализацию бинарного дерева – указателю на корень присвоить пустое значение (Root:=nil;). Бинарного дерева не существует, поэтому это пустое значение служит начальным значением бинарного дерева. Добавление новых элементов в дерево будем осуществлять процедурой Insert. Например, добавление числа Х в бинарное дерево будет выглядеть так: Insert(Root,X). Вывод на экран содержимого дерева можно записать процедурой PrintTree(Root).

Если построено упорядоченное дерево, то его можно применять для сортировки данных. Осуществляя обход дерева InOrder можно получить значения узлов в порядке возрастания, т.е. отсортированную последовательность. Для вывода значений узлов в порядке убывания необходимо внести небольшие изменения в процедуру обхода – поменять местами обходы левого и правого поддеревьев:

Procedure PrintTree1(Tree: PTree); // InOrder

begin

if Tree<>nil then begin // если дерево не пустое, то

PrintTree1(Tree^.Right); // обход правого поддерева

Writeln(‘Value = ‘,Tree^.inf); // обработать узел

PrintTree1(Tree^.Left); // обход левого поддерева

end;

end;

Упорядоченные деревья. Поиск заданного значения.

Упорядоченное дерево можно эффективно применять для поиска. Действительно, поиск значения х осуществляется перемещением по дереву линейно, выбирая на каждом этапе (в каждом узле) направление дальнейшего движения – налево или направо, в зависимости от результата сравнения значения Х со значением в узле. Окончание поиска – или найденное значение или пустой указатель (искать уже негде) При таком алгоритме нет надобности перебирать все значения подряд, поэтому число сравнений здесь минимально. Поиск в бинарном дереве сравним по эффективности с бинарным поиском в упорядоченном массиве.

Функция Find осуществляет поиск узла со значением равным параметру Х. Параметр R –указатель на корень дерева, в котором осуществляется поиск. Возвращаемый результат: True – узел со значением Х найден, False – не найден.