Збалансовані та ідеально збалансовані дерева

Дерево ідеально збалансовано. якщо для кожного його вузла кількість вузлів в лівому і правому поддереве розрізняється не більше ніж на 1.

Дерево збалансовано. якщо для кожного його вузла висота двох відповідних піддерев розрізняється не більше ніж на 1.

Дерево пошуку - дерево, в якому для кожної вершини

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

AVL-дерево (Адельсон-Бєльський, Ландіс) - збалансоване дерево пошуку.

Мал. 6. Приклади довічних дерев.

а), b) - збалансовані дерева; b) - ідеально збалансоване дерево. дерево пошуку, AVL-дерево

СТВОРЕННЯ ИДЕАЛЬНО ЗБАЛАНСОВАНОГО ДЕРЕВА

Послідовність кроків при створенні ідеально збалансованого дерева для заздалегідь відомого числа вершин (n):

Створюється коренева вершина;

Тим же способом будується ліве піддерево, що містить nl = n div 2 вершин;

Тим же способом будується праве піддерево, що містить nr = n-nl-1 вершин;

Рекурсія завершується, якщо поддерево не містить жодної вершини (n = 0).

ПРИКЛАД 3. ПРОЦЕДУРА СТВОРЕННЯ ИДЕАЛЬНО ЗБАЛАНСОВАНОГО ДЕРЕВА

if (x

if (x> p ^ .Key) then Search (x, p ^ .Right)

else Writeln ( 'Вузол існує')

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

Використання дерев пошуку для сортування даних - будуємо дерево пошуку, після чого обходимо його за правилом ЛКП (по зростанню) або ПКЛ (по спадаючій)

ПРИКЛАД 8. ПРОЦЕДУРА ПОШУКУ З ВКЛЮЧЕННЯМ (без рекурсії) ...

ЗАВДАННЯ 2. Намалюйте дерева, які будуть створені функцією CreateTree (приклад 3) і процедурою Search (приклад 7) для введеної послідовності символів "Інформатика".

ПРИМІТКА. Див. Також програми: TreeSearch.exe (каталог \ Програми \ 02_ДеревоПоіска) - створення дерева пошуку та його обхід; Demt.exe (каталог \ Програми \ 03_ДеревоПоіска) - створення дерева пошуку та його балансування.

ВИДАЛЕННЯ УЗЛА З ДЕРЕВА ПОШУКУ

ПРИКЛАД 10. ПРОЦЕДУРА ВИДАЛЕННЯ УЗЛА З ДЕРЕВА ПОШУКУ

Зауваження: При видаленні елемента з двома нащадками відбувається його заміщення на самий правий елемент лівого піддерева (див. Процедуруdel)

PROCEDURE DELNODE (x: char; VAR p: tree);

procedure del (var r: tree);