Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Відповіді до іспиту по СОД.doc
Скачиваний:
0
Добавлен:
01.03.2025
Размер:
191 Кб
Скачать
☆
  1. Бінарні ідеально сбалансовані дерева: приклади призначення, структура вузла, алгоритм формування.

Дерево является СБАЛАНСИРОВАННЫМ тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на 1.

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

Операции выполняемые над сбалансированным деревом: поиск, вставка, удаление элемента.

Алгоритм построения идеально сбалансированного дерева при известном числе вершин n лучше всего формулируется с помощью рекурсии .

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

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

взять одну вершину в качестве корня.

построить левое поддерево с nl = n DIV 2 вершинами тем же способом.

построить правое поддерево с nr = n-nl-1 вершинами тем же способом.

В сбалансированном дереве каждый узел должен находится в одном из этих трех состояний. Если в дереве существует узел, для которого это условие несправедливо, такое дерево называется несбалансированным.

function B_Tree(N:integer):Tree;

var

NewNode :Tree; Nl,Nr :integer; X :char;

begin

if N = 0 then B_Tree:=nil

else begin

Nl:=N div 2;

Nr:=N-Nl-1;

Inc(I);

X:= Mas[I];

New(NewNode);

with NewNode^ do begin

Key:=X;

Left:=B_Tree(Nl);

Right:=B_Tree(Nr);

end;

B_Tree:=NewNode;

end;end;