ВУЗ:
Составители:
35
procedure Tree_1n(var T : Tree; n,k : integer);
var i : integer;
begin
if k > n then T:=nil
else
begin
new(T); T^.inf:=k;
Tree_1n (T^.L, n, k+1);
Tree_1n (T^.R, n, k+1);
end
end; { Tree_1n }
Обращение к процедуре Tree_1n для построения дерева Root заданным
способом будет иметь вид: Tree_1n(Root,n,1);
Процедуры включения и исключения, восстанавливающие идеально сба-
лансированное дерево, – довольно сложные операции и не всегда оправданы.
Менее строгое определение сбалансированного дерева было предложено
Г.М. Адельсоном-Вельским и Е.М. Ландисом :
Дерево называется сбалансированным тогда и только тогда
, когда
высоты двух поддеревьев каждой из его вершин отличаются не более чем на
единицу.
Деревья, удовлетворяющие такому условию, называют равновесными [7]
или АВЛ – деревьями. Идеально сбалансированные деревья являются частным
случаем АВЛ – деревьев.
Процедуры включения и исключения, сохраняющие сбалансированность
деревьев, подробно описаны в [ 2, 4 ].
Упражнение 5.1. Описать процедуру построения дерева, изображенного на
рисунке 8 а
), используя два параметра ( T, n ).
Упражнение 5.2. Описать процедуру построения дерева, изображенного на
рисунке 8 б).
