Динамічні структури даних: двійкові дерева h2>
Дерево
- Це сукупність елементів, які називаються вузлами (при цьому один з них визначено
як корінь), і відносин (батьківський-дочірній), які утворюють ієрархічну
структуру вузлів. Вузли можуть бути величинами будь-якого простого або
структурованого типу, за винятком файлового. Вузли, які не мають ні
одного подальшого вузла, називаються листям. p>
В
двійковому (бінарному) дереві кожен вузол може бути пов'язаний не більш як двома
іншими вузлами. Як розширення двійкове дерево визначається так: двійкове дерево
буває або порожнім (не містить жодного вузла), або містить вузол, званий
коренем, а також два незалежних піддереві - ліве піддерево і праве піддерево. p>
Двійкове
дерево пошуку може бути або порожнім, або воно має таку властивість, що
кореневий елемент має більше значення вузла, ніж будь-який елемент в лівому
піддереві, і менше або рівне, ніж елементи в правому піддереві. Зазначене
властивість називається характеристичним властивістю двійкового дерева пошуку та
виконується для будь-якого вузла такого дерева, включаючи коріння. Далі будемо
розглядати тільки двійкові дерева пошуку. Таку назву двійкові дерева
пошуку отримали з тієї причини, що швидкість пошуку в них приблизно така ж,
що і в впорядкованих масивах: O (n) = C • log2n (в гіршому випадку O (n) = n). p>
Приклад.
Для набору даних 9, 44, 0, -7, 10, 6, -12, 45 побудувати двійкове дерево
пошуку. p>
Згідно
визначення двійкового дерева пошуку число 9 поміщаємо в корінь, всі значення,
менші його - на ліве піддерево, більші або рівні - на праве. У кожному
піддереві черговий елемент можна розглядати як корінь і діяти за
того ж алгоритму. У підсумку отримуємо p>
p>
Виділимо
типові операції з двiйковими деревами пошуку: p>
додавання
елемента в дерево; p>
видалення
елемента з дерева; p>
обхід
дерева (для друку елементів і т.д.); p>
пошук
у лісі. p>
Оскільки
визначення двійкового дерева рекурсивно, то всі зазначені типові операції
можуть бути реалізовані у вигляді рекурсивних підпрограм (на практиці саме такий
варіант найчастіше і застосовується). Відзначимо лише, що використання рекурсії
уповільнює роботу програми і витрачає зайву пам'ять при її виконанні. p>
Нехай
двійкове дерево пошуку описується таким типом p>
Type BT = LongInt; U = ^ BinTree;
BinTree = Record Inf: BT; L, R: U End; p>
Покажемо
два варіанти додавання елемента в дерево: ітеративний і рекурсивний. p>
(Ітеративний
варіант додавання елемента в дерево, Turbo Pascal) p>
Procedure InsIteration (Var T: U; X
: BT); p>
Var vsp, A: U; p>
Begin p>
New (A); A ^. Inf: = X; A ^. L: = Nil; A ^. R: = Nil; p>
If T = Nil Then T: = A p>
Else Begin vsp: = T; p>
While vsp Nil
Do p>
If A ^. Inf <
vsp ^. Inf p>
Then p>
If vsp ^. L = Nil Then
Begin vsp ^. L: = A; vsp: = A ^. L End Else vsp: = vsp ^. L p>
Else p>
If vsp ^. R = Nil Then Begin vsp ^. R
: = A; vsp: = A ^. R End Else vsp: = vsp ^. R; p>
End p>
End; p>
(Рекурсивний
варіант додавання елемента в дерево, Turbo Pascal) p>
Procedure InsRec (Var Tree: U; x:
BT); p>
Begin p>
If Tree = Nil p>
Then Begin p>
New (Tree); p>
Tree ^. L: = Nil; p>
Tree ^. R: = Nil; p>
Tree ^. Inf: = x p>
End p>
Else If x
Then InsRec (Tree ^. L, x) p>
Else InsRec (Tree ^. R, x) p>
End; p>
Аналогічно на C ++. p>
typedef long BT; p>
struct BinTree ( p>
BT inf; p>
BinTree * L; BinTree * R; p>
); p>
/*
Ітеративний варіант додавання елемента в дерево, C + + */ p>
BinTree * InsIteration (BinTree * T, BT
x) p>
(BinTree * vsp, * A; p>
A = (BinTree *) malloc (sizeof (BinTree)); p>
A-> inf = x; A-> L = 0; A-> R = 0; p>
if (! T) T = A; p>
else (vsp = T; p>
while (vsp) p>
(if (A-> inf inf) p>
if (! vsp-> L) (vsp-> L = A; vsp = A-> L;) p>
else vsp = vsp-> L; p>
else p>
if (! vsp-> R) (vsp-> R = A; vsp = A-> R;) p>
else vsp = vsp-> R; p>
) p>
) p>
return T; p>
) p>
/*
Рекурсивний варіант додавання елемента в дерево, C + + */ p>
BinTree * InsRec (BinTree * Tree, BT x) p>
( p>
if (! Tree) (Tree = (BinTree *)
malloc (sizeof (BinTree)); p>
Tree-> inf = x; Tree-> L = 0; Tree-> R = 0; p>
) P>
else if (x inf)
Tree-> L = InsRec (Tree-> L, x); p>
else
Tree-> R = InsRec (Tree-> R, x); p>
return Tree; p>
) p>
Існує
декілька способів обходу (проходження) усіх вузлів дерева. Три найбільш часто
використовуваних з них називаються обхід в прямому (префіксном) порядку, в обхід
зворотному (постфіксном) порядку і обхід у внутрішньому порядку (або симетричний
обхід). Кожен з обходів реалізується з використанням рекурсії. P>
Нижче
наведені підпрограми друку елементів дерева з використанням обходу
двійкового дерева пошуку в зворотному порядку. p>
(Turbo Pascal) p>
Procedure PrintTree (T: U); p>
begin p>
if T Nil p>
then begin PrintTree (T ^. L); write (T ^. inf: 6); PrintTree (T ^. R) end; p>
end; p>
// C + + p>
void PrintTree (BinTree * T) p>
( p>
if (T) (PrintTree (T-> L); cout
infR );} p>
) p>
Реалізуємо
функція, що повертає true (1), якщо елемент присутній в дереві, і false (0)
- В іншому випадку. P>
(Turbo Pascal) p>
function find (Tree: U; x: BT):
boolean; p>
begin p>
if Tree = nil then find: = false p>
else if Tree ^. inf = x then Find: =
True p>
else if x
then
Find: = Find (Tree ^. L, x) p>
else
Find: = Find (Tree ^. R, x) p>
end; p>
/* C + + */ p>
int Find (BinTree * Tree, BT x) p>
(if (! Tree) return 0; p>
else if (Tree-> inf == x) return 1; p>
else if (x inf) return Find (Tree-> L, x); p>
else return Find (Tree-> R, x); p>
) p>
За
порівнянні з попередніми завдання видалення вузла з дерева реалізується кілька
складніше. Можна виділити два випадки видалення елемента x (випадок відсутності
елемента в дереві є виродженим): p>
1)
вузол, що містить елемент x, має ступінь не більше 1 (ступінь вузла - число
піддерев, що виходять з цього вузла); p>
2)
вузол, що містить елемент x, має ступінь 2. p>
Випадок
1 не представляє складності. Попередній вузол з'єднується або з єдиним
піддерево видаленого вузла (якщо ступінь видаленого вузла дорівнює 1), або не
буде мати піддереві зовсім (якщо ступінь вузла дорівнює 0). p>
Набагато
складніше, якщо видаляється вузол має два піддереві. У цьому випадку потрібно замінити
видаляється елемент самим правим елементом з його лівого піддереві. p>
(Turbo Pascal) p>
function Delete (Tree: U; x: BT): U; p>
var P, v: U; p>
begin p>
if (Tree = nil) p>
then writeln ( 'такого елемента в дереві немає!') p>
else if x
else p>
if x> Tree ^. inf p>
then Tree ^. R: =
Delete (Tree ^. R, x) (випадок 1) p>
else p>
begin (випадок 1) p>
P: = Tree; p>
if Tree ^. R = nil p>
then Tree: = Tree ^. L p>
else if Tree ^. L = nil p>
then
Tree: = Tree ^. R p>
else begin p>
v: =
Tree ^. L; p>
while
v ^. R ^. R nil do v: = v ^. R; p>
Tree ^. inf
: = V ^. R ^. Inf; p>
P: = v ^. R;
p>
v ^. R: = v ^. R ^. L; p>
end; p>
dispose (P); p>
end; p>
Delete: = Tree p>
end; p>
(C ++} p>
BinTree * Delete (BinTree * Tree, BT
x) p>
(
BinTree * P, * v; p>
if (! Tree) cout L =
Delete (Tree-> L, x); p>
else if (x> Tree-> inf) Tree-> R = Delete (Tree-> R, x); p>
else (P = Tree; p>
if (! Tree-> R) Tree = Tree-> L;// випадок 1 p>
else if (! Tree-> L) Tree = Tree-> R;// випадок 1 p>
else (v = Tree-> L; p>
while (v-> R-> R) v = v-> R;// випадок 2 p>
Tree-> inf = v-> R-> inf; p>
P = v-> R; v-> R = v-> R-> L; p>
) P>
free (P); p>
) P>
return Tree; p>
) p>
Примітка.
Якщо елемент повторюється у лісі кілька разів, то віддаляється тільки першу його
входження. p>
Список літератури h2>
Для
підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru
p>