Динамічні структури даних: двійкові дерева

Дерево - Це сукупність елементів, які називаються вузлами (при цьому один з них визначено як корінь), і відносин (батьківський-дочірній), які утворюють ієрархічну структуру вузлів. Вузли можуть бути величинами будь-якого простого або структурованого типу, за винятком файлового. Вузли, які не мають ні одного подальшого вузла, називаються листям.

В двійковому (бінарному) дереві кожен вузол може бути пов'язаний не більш як двома іншими вузлами. Як розширення двійкове дерево визначається так: двійкове дерево буває або порожнім (не містить жодного вузла), або містить вузол, званий коренем, а також два незалежних піддереві - ліве піддерево і праве піддерево.

Двійкове дерево пошуку може бути або порожнім, або воно має таку властивість, що кореневий елемент має більше значення вузла, ніж будь-який елемент в лівому піддереві, і менше або рівне, ніж елементи в правому піддереві. Зазначене властивість називається характеристичним властивістю двійкового дерева пошуку та виконується для будь-якого вузла такого дерева, включаючи коріння. Далі будемо розглядати тільки двійкові дерева пошуку. Таку назву двійкові дерева пошуку отримали з тієї причини, що швидкість пошуку в них приблизно така ж, що і в впорядкованих масивах: O (n) = C • log2n (в гіршому випадку O (n) = n).

Приклад. Для набору даних 9, 44, 0, -7, 10, 6, -12, 45 побудувати двійкове дерево пошуку.

Згідно визначення двійкового дерева пошуку число 9 поміщаємо в корінь, всі значення, менші його - на ліве піддерево, більші або рівні - на праве. У кожному піддереві черговий елемент можна розглядати як корінь і діяти за того ж алгоритму. У підсумку отримуємо

Виділимо типові операції з двiйковими деревами пошуку:

додавання елемента в дерево;

видалення елемента з дерева;

обхід дерева (для друку елементів і т.д.);

пошук у лісі.

Оскільки визначення двійкового дерева рекурсивно, то всі зазначені типові операції можуть бути реалізовані у вигляді рекурсивних підпрограм (на практиці саме такий варіант найчастіше і застосовується). Відзначимо лише, що використання рекурсії уповільнює роботу програми і витрачає зайву пам'ять при її виконанні.

Нехай двійкове дерево пошуку описується таким типом

Type BT = LongInt; U = ^ BinTree; BinTree = Record Inf: BT; L, R: U End;

Покажемо два варіанти додавання елемента в дерево: ітеративний і рекурсивний.

(Ітеративний варіант додавання елемента в дерево, Turbo Pascal)

Procedure InsIteration (Var T: U; X : BT);

Var vsp, A: U;

Begin

New (A); A ^. Inf: = X; A ^. L: = Nil; A ^. R: = Nil;

If T = Nil Then T: = A

Else Begin vsp: = T;

While vsp Nil Do

If A ^. Inf < vsp ^. Inf

Then

If vsp ^. L = Nil Then Begin vsp ^. L: = A; vsp: = A ^. L End Else vsp: = vsp ^. L

Else

If vsp ^. R = Nil Then Begin vsp ^. R : = A; vsp: = A ^. R End Else vsp: = vsp ^. R;

End

End;

(Рекурсивний варіант додавання елемента в дерево, Turbo Pascal)

Procedure InsRec (Var Tree: U; x: BT);

Begin

If Tree = Nil

Then Begin

New (Tree);

Tree ^. L: = Nil;

Tree ^. R: = Nil;

Tree ^. Inf: = x

End

Else If x

Then InsRec (Tree ^. L, x)

Else InsRec (Tree ^. R, x)

End;

Аналогічно на C ++.

typedef long BT;

struct BinTree (

BT inf;

BinTree * L; BinTree * R;

);

/* Ітеративний варіант додавання елемента в дерево, C + + */

BinTree * InsIteration (BinTree * T, BT x)

(BinTree * vsp, * A;

A = (BinTree *) malloc (sizeof (BinTree));

A-> inf = x; A-> L = 0; A-> R = 0;

if (! T) T = A;

else (vsp = T;

while (vsp)

(if (A-> inf inf)

if (! vsp-> L) (vsp-> L = A; vsp = A-> L;)

else vsp = vsp-> L;

else

if (! vsp-> R) (vsp-> R = A; vsp = A-> R;)

else vsp = vsp-> R;

)

)

return T;

)

/* Рекурсивний варіант додавання елемента в дерево, C + + */

BinTree * InsRec (BinTree * Tree, BT x)

(

if (! Tree) (Tree = (BinTree *) malloc (sizeof (BinTree));

Tree-> inf = x; Tree-> L = 0; Tree-> R = 0;

)

else if (x inf) Tree-> L = InsRec (Tree-> L, x);

else Tree-> R = InsRec (Tree-> R, x);

return Tree;

)

Існує декілька способів обходу (проходження) усіх вузлів дерева. Три найбільш часто використовуваних з них називаються обхід в прямому (префіксном) порядку, в обхід зворотному (постфіксном) порядку і обхід у внутрішньому порядку (або симетричний обхід). Кожен з обходів реалізується з використанням рекурсії.

Нижче наведені підпрограми друку елементів дерева з використанням обходу двійкового дерева пошуку в зворотному порядку.

(Turbo Pascal)

Procedure PrintTree (T: U);

begin

if T Nil

then begin PrintTree (T ^. L); write (T ^. inf: 6); PrintTree (T ^. R) end;

end;

// C + +

void PrintTree (BinTree * T)

(

if (T) (PrintTree (T-> L); cout infR );}

)

Реалізуємо функція, що повертає true (1), якщо елемент присутній в дереві, і false (0) - В іншому випадку.

(Turbo Pascal)

function find (Tree: U; x: BT): boolean;

begin

if Tree = nil then find: = false

else if Tree ^. inf = x then Find: = True

else if x

then Find: = Find (Tree ^. L, x)

else Find: = Find (Tree ^. R, x)

end;

/* C + + */

int Find (BinTree * Tree, BT x)

(if (! Tree) return 0;

else if (Tree-> inf == x) return 1;

else if (x inf) return Find (Tree-> L, x);

else return Find (Tree-> R, x);

)

За порівнянні з попередніми завдання видалення вузла з дерева реалізується кілька складніше. Можна виділити два випадки видалення елемента x (випадок відсутності елемента в дереві є виродженим):

1) вузол, що містить елемент x, має ступінь не більше 1 (ступінь вузла - число піддерев, що виходять з цього вузла);

2) вузол, що містить елемент x, має ступінь 2.

Випадок 1 не представляє складності. Попередній вузол з'єднується або з єдиним піддерево видаленого вузла (якщо ступінь видаленого вузла дорівнює 1), або не буде мати піддереві зовсім (якщо ступінь вузла дорівнює 0).

Набагато складніше, якщо видаляється вузол має два піддереві. У цьому випадку потрібно замінити видаляється елемент самим правим елементом з його лівого піддереві.

(Turbo Pascal)

function Delete (Tree: U; x: BT): U;

var P, v: U;

begin

if (Tree = nil)

then writeln ( 'такого елемента в дереві немає!')

else if x

else

if x> Tree ^. inf

then Tree ^. R: = Delete (Tree ^. R, x) (випадок 1)

else

begin (випадок 1)

P: = Tree;

if Tree ^. R = nil

then Tree: = Tree ^. L

else if Tree ^. L = nil

then Tree: = Tree ^. R

else begin

v: = Tree ^. L;

while v ^. R ^. R nil do v: = v ^. R;

Tree ^. inf : = V ^. R ^. Inf;

P: = v ^. R;

v ^. R: = v ^. R ^. L;

end;

dispose (P);

end;

Delete: = Tree

end;

(C ++}

BinTree * Delete (BinTree * Tree, BT x)

( BinTree * P, * v;

if (! Tree) cout L = Delete (Tree-> L, x);

else if (x> Tree-> inf) Tree-> R = Delete (Tree-> R, x);

else (P = Tree;

if (! Tree-> R) Tree = Tree-> L;// випадок 1

else if (! Tree-> L) Tree = Tree-> R;// випадок 1

else (v = Tree-> L;

while (v-> R-> R) v = v-> R;// випадок 2

Tree-> inf = v-> R-> inf;

P = v-> R; v-> R = v-> R-> L;

)

free (P);

)

return Tree;

)

Примітка. Якщо елемент повторюється у лісі кілька разів, то віддаляється тільки першу його входження.

Список літератури

Для підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru