Энциклопедия Turbo Pascal. Главы 1-4 - Двоичные деревья
ОГЛАВЛЕНИЕ
Двоичные деревья
В этом разделе рассматривается четвертая структура данных, которая называется двоичным деревом. Имеется много типов деревьев. Однако, двоичные деревья занимают особое положение. Если такие деревья упорядочить, то операции поиска, вставки и удаления будут выполняться очень быстро. Каждый элемент двоичного дерева имеет информационные поля, связь с левым элементом и связь с правым элементом. На рис.14 показано небольшое дерево.
При описании деревьев используется специальная терминология. Первый элемент дерева называется его корнем. Каждый элемент называют вершиной /или листом/ дерева, а часть дерева носит название поддерева. Вершина, которая не имеет поддеревьев, называется терминальной вершиной. Высота дерева равна числу уровней вершин в дереве. В дальнейшем при рассмотрении деревьев можно считать, что в памяти они располагаются так же, как на бумаге. Однако следует помнить, что деревья представляют собой лишь способ представления данных в памяти, а память в действительности имеет линейную форму.
Root Node 1
--------¬
¦2 info ¦
+---T---+
¦ ¦ ¦
3 L---+---- 4
Left Subtree Righl Subtree
--------¬ --------¬
¦ 2 info¦ ¦2 info ¦
+---T---+ +---T---+
¦ ¦ ¦ 5¦nil¦ ¦
L---+---- L---+---
--------¬ --------¬ --------¬
¦2 info ¦ ¦2 info ¦ ¦2 info ¦
+---T---+ +---T---+ +---T---+
5¦nil¦nil¦5 5¦nil¦nil¦5 5¦nil¦nil¦5
L---+---- L---+---- L---+---
6
Terminal Nodes
Рис.14. Пример двоичного дерева:
1 - корневая вершина;
2 - информационные поля;
3 - левое поддерево;
5 - указатель связи с нулевым значением;
6 - терминальные вершины.
Двоичное дерево представляет собой особую форму связанного списка. Доступ к элементам, их вставка и удаление могут выполняться в любом порядке. Кроме того, операция поиска не носит разрушительный характер. Хотя деревья легко представляются образно, для программирования они представляют достаточно непростую задачу. Поэтому они стали рассматриваться лишь в этом разделе.
Большинство функций над деревьями носят рекурсивный характер, поскольку дерево само по себе является рекурсивной структурой данных. /Т.е. каждое поддерево само является деревом/. Поэтому представленные в этом разделе программы являются, как правило, рекурсивными. Имеются нерекурсивные версии этих функций, однако разобраться в них значительно труднее.
Упорядоченность дерева зависит от порядка доступа к дереву.
Процесс доступа к каждой вершине дерева называется обходом дерева.
Имеется три способа обхода дерева: во внутреннем порядке, в прямом порядке и в обратном порядке. При прохождении дерева во внутреннем порядке сначала посещается левое поддерево, затем корень и затем посещается правое дерево. При прохождении дерева в прямом порядке сначала посещается корень, затем левое поддерево и затем правое поддерево. При прохождении дерева в обратном порядке сначала посещается левое поддерево, затем правое поддерево и затем корень.
Порядок прохождения ds, выбранного в качестве примера дерева будет следующим:
- при прохождении во внутреннем порядке: a b c d e f g;
- при прохождении в прямом порядке: d b a c f e g;
- при прохождении в обратном порядке: a c b e g f d.
Хотя дерево не обязательно должно быть упорядочено, в большинстве случаев оно должно быть таким. Упорядоченность дерева зависит от того, как вы будете проходить дерево. В приводимых ниже примерах используется внутренний порядок прохода по дереву. В отсортированном двоичном дереве левое поддерево содержит вершины, которые меньше или равны корню, а вершины правого поддерева больше или равны корню. Ниже приводится функция, которая выполняет построение отсортированного двоичного дерева:
type
TreePointer = ^tree;
tree = record
data: char;
left: TreePointer;
right:TreePointer;
end;
{ добавить элемент в двоичное дерево }
function Stree(root,r:TreePointer;data:char);TreePointer;
begin
if r=nil then
begin
new(r); { получить новую вершину }
r^.left:=nil;
r^right:=nil;
r^.data:=data;
if data<root^.data then root^.left:=r
else root^.right:=r;
STree:=r;
end else
begin
if data<r^.data then STree:=STree(r, r^.left, data)
else STree:=STree(r, r^.right, data);
end;
end; { конец функции добавления элемента в двоичное
дерево }
В этом алгоритме выполняется просто прохождение по связям дерева, двигаясь вправо или влево в зависимости от поля данных.
При применении этой функции необходимо предусмотреть глобальную переменную для корня дерева. Вначале эта глобальная переменная должна быть установлена в нулевое значение. Указатель на корень будет установлен при первом обращении к указанной функции. Поскольку при последующих обращениях к этой функции нет необходимости делать новую установку корня, то используется фиктивная переменная. Если глобальной переменной будет "rt", то обращение к указанной функции может иметь следующий вид:
{call STree}
if rt=nil rt:=STree(rt, rt, info)
else dummy := STree(rt, rt, info);При таком обращении к функции вставка и первого и последующих элементов будет выполняться корректно.
Указанная функция является рекурсивной, как и большинство других процедур с деревьями. Если этот алгоритм преобразовать, используя прямой метод перехода рекурсивных алгоритмов в циклическую форму, то программа будет в несколько раз длинее. При обращении к функции задается указатель на корень и указатель на поддерево, а также помещаемые в дерево данные. Здесь в качкестве вставляемых в дерево данных используется символьное данное. Однако, в качестве такого данного можно использовать данное любого типа.
Для обхода дерева с использованием указанной функции и выдачи на печать поля данных каждой вершины можно использовать следующую функцию:
procedure InOrder(root:TreePointer);
begin
if root<>nil then
begin
InOrder(root^.left);
Write(root^.data);
InOrder(root^.right);
end;
end.
Эта функция делает обход дерева во внутреннем порядке и завершается при обнаружении терминального листа /указателя о нулевом завершении/. Ниже показаны функции для прохождения дерева в прямом и обратном порядке:
procedure PreOrder(root:TreePointer);
begin
if root<>nil then
begin
write(root^.data);
preorder(root^.left);
preorder(root^.right);
end;
end.
procedure PostOrder(root:TreePointer);
begin
if root<>nil then
begin
postorder(root^.left);
postorder(root^.right);
Write(root^.data);
end;
end.
Вы можете составить короткую программу, которая строит упорядоченное двоичное дерево и, кроме того, печатает его на экране вашего компьютера. Для этого требуется выполнить лишь незначительные изменения в процедуре прохода дерева во внутреннем порядке. Ниже приводится программа, которая выдает вершины дерева во внутреннем порядке:
{ вывод на экран вершин дерева /слева направо/ }
programm DisplayTree;
uses Crt;
type
TreePointer = ^tree
tree = record
data: char;
left: TreePointer;
right: TreePointer;
end;
var
root, dummy: TreePointer;
ch:char;
function STree(root, r:TreePointer; data: char):
TreePointer;
begin
if r = nil then
begin
new(r); { получить новую вершину }
r^.left := nil;
r^.right := nil;
r^.data := data;
if data < root^.data then root^.left := r
else root^.right := r;
STree := r;
end else
begin
if data<r^.data then STree := STree(r, r^.left, data)
else STree := STree(r, r^.right, data)
end;
end; { конец процедуры STree }
procedure PrintTree(r: TreePointer; n: integer);
var
i:integer;
begin
if r<>nil then begin
PrintTree(r.^left, n+1);
for i := 1 to n do Write(' ');
Writeln(r^.data);
PrintTree(r^.right, n+1);
end;
end; { конец процедуры PrintTree }
begin
root := nil;
repeat
Write('enter a letter (Q to quit): ');
ch := ReadKey; Writeln(ch);
if root= nil then root := STree(root, root, ch)
else dummy := STree(root, root, ch);
ch := UpCase(ch);
until ch ='Q';
PrintTree(root, 0);
end;В этой программе фактически делается сортировка полученной информации. В данном случае используется вариант сортировки вставкой, которая описывается в предыдущей главе. Для среднего случая сортировка вставкой имеет достаточно хорошие характеристики, однако быстрая сортировка все же является лучшим методом сортировки, так как она требует меньше оперативной памяти и выполняется быстрее. Однако, если дерево строится на основе использования других деревьев или если вам приходится поддерживать упорядоченное дерево, то новые элементы всегда будут вставляться с использованием функции STree.
Если вы воспользуетесь программой вывода на экран двоичного дерева, то возможно вы заметите, что некоторые деревья сбалансированы /т.е. все поддеревья имеют одинаковую или почти одинаковую высоту/, а другие сильно несбалансированы. Если вы введете дерево
"abcd", то оно примет следующий вид:
a
\
\
b
\
\
c
\
\
.
В этом случае левых поддеревьев не будет. Это дерево называется вырожденным, поскольку оно выродилось в линейный список. В общем случае, если используемые для построения дерева данные являются в достаточной мере случайными, дерево будет приближаться к сбалансированному. Однако, если информация уже упорядочена, то в результате будет получаться вырожденное дерево. /Имеется возможность переупорядочивать дерево, сохраняя при каждой вставке его балансировку. Однако такой алгоритм достаточно сложен и если он вас заинтересовал, то следует воспользоваться книгами по усовершенствованным методам составления алгоритмов программ/.
Функции поиска для двоичных деревьев составляются легко. Ниже приводится функция, результатом которой является указатель на вершину дерева, которая совпадает с ключем. В противном случае возвращается нулевое значение.
{ поиск элемента в дереве }
function Search(root:TreePointer;
key:DataItem):TreePointer;
begin
if root <> nil
begin
while (root^.data <> key) and (root <> nil) do
begin
if key < root^.data then root := root^.left
else root := root^.right;
end;
end;
Search := root;
end; { конец процедуры поиска элемента }
К сожалению, удаление вершины дерева выполняется не так просто, как поиск вершины. Удаленной вершиной может быть корень, левая вершина или правая вершина. Вершина может также иметь от нуля до двух поддеревьев. Необходимость изменения указателей приводит, например, к следующему рекурсивному алгоритму
{ удаление элемента из дерева }
function DTree(root:TreePointer;key:char):TreePointer;
var
temp,temp2:TreePointer;
begin
if root^.data = key then
begin
if root^.left=root^.right tnen
begin
dispose(root)
DTree := nil;
end
else if root^.left=nil tnen
begin
temp := root^.right
dispose(root)
DTree := temp;
end
else if root^.right=nil tnen
begin
temp := root^.left
dispose(root)
DTree := temp;
end
else
begin { имеются два листа }
temp2 := root^.right
temp := root^.right
while temp^.left <> nil do temp := temp^.left;
temp^.left := root^.left
dispose(root);
DTree := temp2
end;
else
begin
if root^.data < key
then root^.right := DTree(root^.right, key)
else root^.left := DTree(root^.left, key)
DTree := root;
end;
end; { конец функции DTree }Следует помнить, что в основной программе необходимо обновлять указатель на корень дерева, так как удаленная вершина может оказаться корнем дерева. Использование двоичных деревьев позволяет создавать мощные, гибкие и эффективные программы по управлению баз данных. Информация в этом случае может находиться на диске и поэтому важное значение может иметь время доступа. Число сравнений при использовании сбалансированных двоичных деревьев для худшего случая равно log2(n). Поэтому в этом случае поиск выполняется значительно быстрее, чем поиск в связанном списке, который посуществу является последовательным поиском.