Занятие 4. Идеально сбалансированное дерево

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

Использование деревьев поиска значительно сокращает время решения задачи.

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

Сформируем идеально сбалансированное дерево, элементами которого являются N чисел, вводимых с клавиатуры.

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

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

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

• Построить правое поддерево с числом узлов n2=N-n1-1 тем же способом.

Program BalansTree;

Uses

Crt;

Type

Pt = ^Node;

Node = record

Data: integer;

Left, Right: Pt;

end;

Var

n: integer;

kd: Pt;

f: text;

Function Tree(n: integer): Pt;

Var

NewNode: Pt;

x, n1, n2: integer;

Begin

if n=0

then

Tree:= Nil

else

begin

n1:= n Div 2;

n2:= n–n1–1;

read(f,x);

new(NewNode);

with NewNode^ do

begin

Data:= x;

Left:= Tree(n1);

Right:= Tree(n1);

end;

Tree:= NewNode;

end;

End;

Procedure PrintTree(t: Pt; h: integer);

Var

i: integer;

Begin

if t<>nil

then

with t^ do

begin

PrintTree(Left, h+1);

for i:= 1 to h do

write(' ');

writeln(Data:6);

PrintTree(Right, h+1);

end;

End;

Begin

ClrScr;

assign(f, 'c:\f.pas');

reset(f);

write('n=');

readln(n);

kd:= Tree(n);

PrintTree(kd, 0);

readln;

End.

Задание. Наберите программу, протестируйте ее, вставьте комментарий, приготовьтесь объяснить учителю принцип построения идеально сбалансированного дерева.