Типи бінарних дерев

Очевидно, що дерева, що складаються з n вершин, можуть бути побудовані по-різному. У залежності від того, як будуються дерева, розрізняють: ідеально збалансовані дерева, збалансовані і не збалансовані дерева.

ІДЕАЛЬНО ЗБАЛАНСОВАНІ ДЕРЕВА.Дерево називається ідеально збалансованим, якщо число вершин у його лівих і правих піддеревах відрізняється не більше ніж на одну вершину. Таке дерево має мінімальну глибину (кількість рівнів). Мінімальна глибина досягається, якщо на всіх рівнях, крім останнього, міститься максимально можливе число вершин. Цього просто домогтися, якщо при побудові дерева розміщати вершини нарівно ліворуч і праворуч від кожної вершини. У результаті, у випадку, коли при побудові дерева подавати, наприклад, такі дані: A, B, C, D, E, F, G, то будуть виходити дерева структури, як на рис. 7.27.

 

 

Рис. 7.27. Порядок побудови збалансованого дерева

 

Правило рівномірного розподілу для заздалегідь відомого числа вершин n можна сформулювати так:

1). Взяти одну вершину як корінь.

2). Побудувати ліве піддерево з nl = (n DIV 2) вершинами.

3). Побудувати праве піддерево з nr = (n – nl – 1) вершинами.

Наприклад, якщо при побудові дерева з 21 вершиною на вхід надходять такі дані: 8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18, то збалансоване дерево, буде мати вигляд як показано на рис. 7.28.

 

 

Рис. 7.28. Ідеально збалансоване дерево

У програмному прикладі 7.3 подано функцію, що дозволяє по заданому nпобудувати ідеально збалансоване дерево.

{===== Програмний приклад 7.3 =======}

Function build_tree(n:integer):TreePtr

Var newnode: TreePtr;

x, nl, nr:integer;

Begin

if n=0 then newnode:=nil else

begin

nl:=n div 2; nr:=n-nl-1;

readln(x); new(newnode);

newnode^.data:=x; newnode^.lptr:= build_tree(nl);

newnode^.rptr:= build_tree(nr);

end; end;

У програмному прикладі 7.4 наведено процедуру виводу вмісту дерева на зразок змісту книг.

{===== Програмний приклад 7.4 =======}

Procedure Printtree(t:TreePtr; n:integer)

Var i:integer;

Begin {друк дерева t з отступом n}

if t<>nil then

Begin

Printtree(t^.lptr, n+1;

for i:=1 to n do write(‘ ‘);

writeln(t^.data:6);

Printtree(t^.rptr, n+1);

end; end;

 

ЗБАЛАНСОВАНІ ДЕРЕВА.Дерево називається збалансованим, якщо висоти лівих і правих піддерев кожної з її вершин відрізняються не більше ніж на одиницю. Дерева, що задовольняють такій умові, часто називають АВЛ-деревами (по імені їхніх відкривачів: Г.М.Адельсона-Вельського і Е.М.Ландіса). Помітимо, що всі ідеально збалансовані дерева є також і АВЛ-деревами. На рис. 7.29 наведені приклади збалансованих дерев.

 

Рис. 7.29. Збалансовані (АВЛ) дерева

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

У збалансованих деревах за час, що пропорційний О(log n) навіть у гіршому випадку, можна виконати такі операції: пошук вершини з заданим ключем, додавання нової вершини з заданим ключем, видалення вершини з зазначеним ключем. Такі твердження є наслідок доведеної Адельсоном-Вельским і Ландисом теореми, що гарантує, що збалансоване дерево ніколи не буде по висоті перевищувати ідеально збалансоване більше ніж на 45 % незалежно від кількості вершин.

НЕЗБАЛАНСОВАНІ ДЕРЕВА.Дерево, що не відповідає вимогам збалансованості є не збалансованим. На практиці частіше мають діло з деревами пошуку; воно росте під час виконання програми. Деревом пошуку називається дерево, для кожної вершини t_iякого справедливе твердження, що усі ключи лівого піддерева t_i менше ключа вузла t_i, а усі ключи правого піддерева t_i більше його. Наприклад, якщо при побудові дерева з 21 вершиною на вхід надходять такі дані: 8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18, то дерево пошуку буде мати вигляд як показано на рис. 7.30.

Рис. 7.30. Дерево пошуку

 

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