ДВОИЧНЫЕ ДЕРЕВЬЯ
В этом разделе рассматривается четвертая структура данных,
которая называется двоичным деревом. Имеется много типов деревь-
ев. Однако, двоичные деревья занимают особое положение. Если та-
кие деревья упорядочить, то операции поиска, вставки и удаления
будут выполняться очень быстро. Каждый элемент двоичного дерева
имеет информационные поля, связь с левым элементом и связь с пра-
вым элементом. На рис.14 показано небольшое дерево.
При описании деревьев используется специальная терминология.
Первый элемент дерева называется его корнем. Каждый элемент назы-
вают вершиной /или листом/ дерева, а часть дерева носит название
поддерева. Вершина, которая не имеет поддеревьев, называется тер-
минальной вершиной. Высота дерева равна числу уровней вершин в
дереве. В дальнейшем при рассмотрении деревьев можно считать, что
в памяти они располагаются так же, как на бумаге. Однако следует
помнить, что деревья представляют собой лишь способ представления
данных в памяти, а память в действительности имеет линейную фор-
му.
Root Node 1
+-------+
¦2 info ¦
+-------¦
¦ ¦ ¦
3 +-------+ 4
Left Subtree Righl Subtree
+-------+ +-------+
¦ 2 info¦ ¦2 info ¦
+-------¦ +-------¦
¦ ¦ ¦ 5¦nil¦ ¦
+-------+ +-------+
+-------+ +-------+ +-------+
¦2 info ¦ ¦2 info ¦ ¦2 info ¦
+-------¦ +-------¦ +-------¦
5¦nil¦nil¦5 5¦nil¦nil¦5 5¦nil¦nil¦5
+-------+ +-------+ +-------+
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 datanil 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 datanil 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
\
\
d
В этом случае левых поддеревьев не будет. Это дерево называ-
ется вырожденным, поскольку оно выродилось в линейный список. В
общем случае, если используемые для построения дерева данные яв-
ляются в достаточной мере случайными, дерево будет приближаться к
сбалансированному. Однако, если информация уже упорядочена, то в
результате будет получаться вырожденное дерево. /Имеется возмож-
ность переупорядочивать дерево, сохраняя при каждой вставке его
балансировку. Однако такой алгоритм достаточно сложен и если он
вас заинтересовал, то следует воспользоваться книгами по усовер-
шенствованным методам составления алгоритмов программ/.
Функции поиска для двоичных деревьев составляются легко. Ни-
же приводится функция, результатом которой является указатель на
вершину дерева, которая совпадает с ключем. В противном случае
возвращается нулевое значение.
{ поиск элемента в дереве }
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). Поэтому в этом случае поиск выполняется значительно
быстрее, чем поиск в связанном списке, который посуществу являет-
ся последовательным поиском.
