Идеально сбалансированные деревья

В заключение данной темы рассмотрим один частный случай ДД — так называемое идеально сбалансированное дерево (ИСД). Как будет отмечено в дальнейшем, эффективное использование деревьев на практике часто требует управления ростом дерева для устранения крайних случаев, когда дерево вырождается в линейный список и тем самым теряет всю свою привлекательность (с вычислительной точки зрения, разумеется).

В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если для каждой вершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!

ИСД легко строится, если заранее известно количество вершин N в этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:

• · взять первую по порядку вершину в качестве корневой
• · найти количество вершин в левых и правых поддеревьях:

Nl = N div 2;

Nr = N — Nl — 1;

• · построить левое поддерево с Nl вершинами точно таким же образом (пока не получим Nl = 0)
• · построить правое поддерево с Nr вершинами точно таким же образом (пока не получим Nr = 0)

Естественно, что реализация рекурсивного алгоритма наиболее просто выполняется в виде рекурсивной подпрограммы. При этом между этой процедурой и процедурами обхода есть одно принципиальное различие: процедуры обхода лишь используют существующую структуру дерева, не изменяя ее, и поэтому их формальные параметры являются лишь входными, тогда как процедура построения ИСД должна СОЗДАВАТЬ вершины и каждый раз возвращать в вызвавшую ее подпрограмму адрес очередной созданной вершины. Поэтому формальный параметр ссылочного типа должен быть объявлен как параметр-переменная. Кроме того, второй формальный параметр-значение принимает число вершин в текущем строящемся поддереве.

procedure AddNodes (var pСurrent: Tp; aN: integer);

var pTemp: Tp;

Nl, Nr: integer;

begin.

if aN = 0 then { вершин для размещения нет }.

pCurrent:= nil { формируем пустую ссылку }.

else.

begin.

Nl:= aN div 2; {сколько вершин будет слева?}.

Nr:= aN — Nl — 1; {сколько вершин будет справа?}.

New (pTemp); {создаем корень поддерева}.

AddNodes (pTemp^.left, Nl); {уходим на создание левого поддерева}.

AddNodes (pTemp^.right, Nr);{уходим на создание правого поддерева}.

pCurrent:= pTemp; {возвращаем адрес созданного корня}.

end.

end;

Запуск процесса построения как обычно выполняется из главной программы с помощью вызова AddNodes (pRoot, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например — заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр pRoot, являясь выходным, получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.

Для понимания работы приведенной процедуры целесообразно вручную расписать шаги ее работы для простейшего дерева из трех вершин. Пусть элементами дерева являются символы A, B, C. В результате работы мы должны получить: pRoot -> A, A. left -> B, A. right -> C, B. left -> nil, B. right -> nil, C. left -> nil, C. right -> nil.

Тогда схема построения ИСД будет:

• · Главная программа: вызов AddNodes (pRoot, 3)
• · П/п 1: Nl = 1, Nr = 1, создание вершины A, вызов AddNodes (A.left, 1)
• · П/п 1−2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A
• · П/п 1−2: Nl = 0, Nr = 0, создание вершины B, вызов

AddNodes (B.left, 0).

• · П/п 1−2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B
• · П/п 1−2-3: aN = 0, pCurrent = nil, возврат к 1−2
• · П/п 1−2: восстановление Nl = 0, Nr = 0, вых. параметр B. left = nil
• · П/п 1−2: вызов AddNodes (B.right, 0)
• · П/п 1−2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса B
• · П/п 1−2-3: aN = 0, pCurrent = nil, возврат к 1−2
• · П/п 1−2: восстановление Nl = 0, Nr = 0, вых. параметр B. right = nil
• · П/п 1−2: pCurrent = адрес B, возврат к 1
• · П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A. left=адрес B
• · П/п 1: вызов AddNodes (A.right, 1)
• · П/п 1−2: сохранение в стеке значений Nl = 1, Nr = 1, адреса A
• · П/п 1−2: Nl = 0, Nr = 0, создание вершины C, вызов

AddNodes (C.left, 0).

• · П/п 1−2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
• · П/п 1−2-3: aN = 0, pCurrent = nil, возврат к 1−2
• · П/п 1−2: восстановление Nl = 0, Nr = 0, вых. параметр C. left = nil
• · П/п 1−2: вызов AddNodes (C.right, 0)
• · П/п 1−2-3: сохранение в стеке значений Nl = 0, Nr = 0, адреса C
• · П/п 1−2-3: aN = 0, pCurrent = nil, возврат к 1−2
• · П/п 1−2: восстановление Nl = 0, Nr = 0, вых. параметр C. right = nil
• · П/п 1−2: pCurrent = адрес C, возврат к 1
• · П/п 1: восстановление Nl = 1, Nr = 1, вых. параметр A. right=адрес C
• · П/п 1: pCurrent = адрес A, возврат в главную программу
• · Главная программа: установка выходного параметра pRoot = адрес A.