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

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

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

Это дерево - ИСД	Это – не ИСД (нарушение условия для корня!)	Это тоже не ИСД (совсем плохо, почти список!)

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

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

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

Nl=Ndiv2;

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