А. Несбалансированное б. сбалансированное

Дихотомические деревья (деревья поиска)

Таблица 5. Трасса состояний стека при работе процедуры построения сбалансированного дерева

Рис. 69. Сбалансированное дерево

Процедура построения сбалансированного дерева из N узлов:

Type
PTree = ^ Tree;	{ тип – указатель на узел сбалансированного дерева }
Tree = record	{ тип – элемент хранения узла сбалансированного дерева }
info: char;
left, right: PTree
end;

Procedure Balance(var root: PTree;	{ root – указатель на корень дерева, }
n: byte);	{ n – количество узлов в дереве }
begin
if n = 0 then root:=nil	{ если n = 0, построить пустое дерево }
else begin
new(root);	{ создать корень дерева }
write(‘Значение инф. поля‘, i, ‘-го узла дерева = ‘);
readln(root^.info);	{ заполнить информационное поле корня }
Balance(root^.left, n div 2);	{ построить левое поддерево}
(1) Balance(root^.right, n – n div 2 – 1)	{ построить правое поддерево }
(2) end
(3)end;

Номер уровня рекур- сии	Знач-я входного парам-ра n	Стек	Знач-я вых. пар-ра	Выход
Исходное состояние (n,root, (.) возврата)	Конечное состояние (n,root, (.) возврата)	root	root^.left	root^.right	из уровня
		(-, -, -)	(3,^A, 1)	^A	-	-	-
		(3,^A, 1)	(1, ^B, 1) (3, ^A, 1)	^B	-	-	-
		(1, ^B, 1) (3, ^A, 1)	(0,NIL,1) (1, ^B, 1) (3, ^A, 1)	NIL	-	-	-
		(0,NIL,1) (1, ^B, 1) (3, ^A, 1)	(1, ^B, 1) (3, ^A, 1)	NIL	-	-	(* 3 *)
		(1, ^B, 1) (3, ^A, 1)	(1, ^B, 2) (3, ^A, 1)	^B	NIL	-	-
		(1, ^B, 2) (3, ^A, 1)	(0,NIL,2) (1, ^B, 2) (3, ^A, 1)	NIL	-	-	-
		(0,NIL,2) (1, ^B, 2) (3, ^A, 1)	(1, ^B, 2) (3, ^A, 1)	NIL	-	-	(* 3 *)
		(1, ^B, 2) (3, ^A, 1)	(3, ^A, 1)	^B	NIL	NIL	(* 3 *)
		(3, ^A, 1)	(3, ^A, 2)	^A	^B	-	-
		(3,^A, 2)	(1, ^С, 1) (3, ^A, 2)	^C	-	-	-
		(1, ^С, 1) (3, ^A, 2)	(0,NIL,1) (1, ^С, 1) (3, ^A, 2)	NIL	-	-	-
		(0,NIL,1) (1, ^С, 1) (3, ^A, 2)	(1, ^С, 1) (3, ^A, 2)	NIL	-	-	(* 3 *)
		(1, ^С, 1) (3, ^A, 2)	(1, ^С, 2) (3, ^A, 2)	^C	NIL
		(1, ^С, 2) (3, ^A, 2)	(0,NIL,2) (1, ^С, 2) (3, ^A, 2)	NIL	-	-	-
		(0,NIL,2) (1, ^С, 2) (3, ^A, 2)	(1, ^С, 2) (3, ^A, 2)	NIL	-	-	(* 3 *)
2		(1, ^С, 2) (3, ^A, 2)	(3, ^A, 2)	^C	NIL	NIL	(* 3 *)
		(3, ^A, 2)	(-, -, -)	^A	^B	^C	(* 3 *)

Для иллюстрации работы этой процедуры и построения трассы состояний стека будем использовать следующие обозначения:

^A – адрес узла дерева, в информационном поле которого хранится символ “A”;

(* 1 *) и (* 2 *) – адреса возврата из уровня рекурсивной процедуры, номер которой на 1 больше текущего;

(* 3 *) – адрес возврата из рекурсивной процедуры текущего уровня.

Трасса построения сбалансированного дерева, содержащего 3 узла, приведена в таблице 5.

Сбалансированное дерево, как и дерево любого другого вида, можно построить в процессе нисходящего обхода. Особенность работы процедуры построения дерева заключается в том, что сначала создаются корневые узлы, адреса которых запоминаются в стеке. Установить ссылки из корневых узлов дерева на их поддеревья можно только после того, как эти поддеревья будут созданы и адреса их корневых узлов возвращены в точки вызова. Точками вызова являются поля ссылок на левое поддерево (root^.left) или правое поддерево (root^.right) корневого узла (в таблице установка этих ссылочных связей показана стрелками). Подобная возможность обеспечивается за счет того, что указатель на корень дерева является параметром-переменной процедуры.

Бинарные деревья часто используются для представления множества объектов, среди которых идет поиск по уникальному значению некоторого атрибута, называемого ключом. При этом на множестве объектов определенно особое отношение порядка - дихотомия, заключающееся в поэтапном разбиении множества информационных полей объектов на два непересекающихся подмножества. Дихотомическим деревом (деревом поиска) называется бинарное дерево, организованное так, что для каждого узла, имеющего ключ Т, справедливо утверждение о том, что в его левом поддереве содержатся узлы с ключами, меньшими T, а в его правом поддереве содержатся узлы с ключами, большими T.

Описание элемента хранения узла дихотомического дерева:

Type
PDtree = ^ Dtree;	{ тип – указатель на узел дихотомического дерева }
Dtree = record	{ тип – элемент хранения узла дихотомического дерева}
key: word;	{ поле ключа }
info: char;	{ информационное поле }
left, right: PDtree	{ ссылки на поддеревья }
end;
Var Root: PDtree;	{ указатель на корень дихотомического дерева }