12.3. Сбалансированные деревья

Дерево называется идеально сбалансированным, если для каждого его узла количества узлов в левом и в правом его поддеревьях различаются не более чем на 1. Разумеется, что идеально сбалансированное дерево имеет минимальную высоту по сравнению со всеми другими деревьями с тем же числом узлов.

Чтобы построить такое дерево, нужно располагать максимально возможное число узлов на всех уровнях, кроме самого нижнего. Это сделать просто, если распределять узлы поровну слева и справа от каждого узла. В результате получим дерево, показанное на рис. 12.6 и построенное из тех же значений, что и на рис. 12.2.

Рис. 12.6. Идеально сбалансированное дерево

Алгоритм равномерного распределения при известном числе узлов N лучше всего выбрать рекурсивным:

1. Взять один узел в качестве корня;

2. Построить левое поддерево с числом узлов nLeft = N div 2 тем же способом;

3. Построить правое поддерево с числом узлов nRight = N – nLeft-1 тем же способом.

Этот алгоритм реализован в виде функции BalanceTree, которая представлена в листинге 12.8. Значения узлов берутся из массива a, который формируется из чисел, введенных в компонент Edit.

Листинг 12.8. Функция построения идеально сбалансированного дерева

function BalanceTree(n: integer): TNode;

var NewNode: TNode;

nLeft, nRight: integer;

begin

if n=0 then BalanceTree:=Nil

else begin

nLeft:=n div 2; nRight:= n-nLeft-1;

new(NewNode);

with NewNode^ do begin

inc(i); key:=a[i];

left:=BalanceTree(nLeft); right:=BalanceTree(nRight);

end;

BalanceTree:= NewNode;

end;

end;

Мы рассмотрели два способа построения дерева — упорядоченного и идеально сбалансированного. Причем упорядоченное дерево, вообще говоря, не является идеально сбалансированным, а идеально сбалансированное — упорядоченным. Это иллюстрируют рис. 12.2, 12.5 и 12.6.

И даже если на каком-то этапе нам повезло, и мы имеем идеально сбалансированное и упорядоченное дерево, то при дальнейшей работе с деревом, то есть при выполнении операций вставки и удаления узлов, дерево может стать несбалансированным. Тогда алгоритмы работы с деревом — поиск, вставка и удаление узлов — становятся менее эффективными. Поэтому на каждом этапе желательно иметь сбалансированное и упорядоченное дерево. Это означает, что процедуры вставки и удаления узла должны оставлять дерево сбалансированным.

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

Одно такое определение сбалансированности было дано российскими математиками Г.М. Адельсоном-Вельским и Е.М. Ландисом. Критерий сбалансированности следующий:

Дерево является сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на единицу.

Деревья, удовлетворяющие этому условию, называют АВЛ-деревьями (по фамилиям их изобретателей). Ниже такие деревья будем называть просто сбалансированными.

Примечание

Все идеально сбалансированные деревья являются также АВЛ-сбалансированными.

Это определение приводит к легко выполнимой балансировке, а средняя длина поиска остается практически такой же, как у идеально сбалансированного дерева.