7.2 Представление деревьев в эвм

Рассмотрим проблему представления деревьев. Ясно, что представление таких структур с разветвлениями предполагает использование ссылок. Не имеет смысла описывать переменные с фиксированной древовидной структурой. Вместо этого узлы определяются как переменные с фиксированной структурой, а связи между ни­ми – с помощью динамических указателей. Степень дерева при этом определяет число компонент-указателей каждого узла. Ссылка на пустое поддерево обозначается, естественно, через Nil.

Таким образом наше дерево – арифметическое выражение – можно считать состоящим из компонент типа: TYPE NODE = RECORD

INF : CHAR; LEFT, RIGHT : ^NODE END; и наше дерево может быть представлено следующей структурой (рис. 19).

Nach 1				► *
				s I ч
	+ <						-
	/ 1 ^						A 1 *
У	г	\				У \
a		/				d		/
Nil Nil		Г 1 i				Nil Nil		г I •
		I		1				I	1
	b			с			/	1	e
	Nil Nil			Nil Nil			Nil Ni		Nil Nil

Рис. 19 Дерево, представленное как структура данных

Формирование дерева в программе может быть выполнено с помощью рекурсивной функции TREE. Предположим, что нужно построить дерево с n узлами и минимальной высотой (т.е. расположить максималь­ное число узлов на всех уровнях кроме последнего). При этом значениями узлов будут N чисел, прочитанных из входного файла. Пусть TYPE REF = ^NODE;

NODE = RECORD

KEY: integer; { содержание узла – число } LEFT, RIGHT: REF END; VAR N: INTEGER; { число узлов дерева }

ROOT: REF; Чтобы построить такое дерево, нужно постараться расположить все поступающие узлы поровну слева и справа от каждого узла. Такое дерево называется идеально сбалансированным.

Правила, по которым действует процедура TREE, можно сформулировать следующим образом:

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

2. построить левое поддерево с NL = N DIV 2 узлами;

3. построить правое поддерево с NR = N - NL - 1 узлами тем же способом. Тогда функция:

FUNCTION TREE(N: INTEGER): REF; VAR NEWNODE : REF;

X, NL, NR : INTEGER; BEGIN

IF N = 0 THEN TREE := Nil ELSE BEGIN

NL := N div 2; NR := N - NL - 1;

READ(x); NEW(NEWNODE);

WITH NEWNODE^ DO BEGIN KEY := X; LEFT := TREE(NL); RIGHT := TREE(NR);

END;

TREE := NEWNODE; END END { TREE }

7.3 Основные операции с бинарными деревьями

Над древовидными структурами выполняются три основные операции:

• обход (просмотр) дерева с целью нахождения нужного узла;

• добавление узла или поддерева в дерево;

• удаление узла из дерева.

Обход двоичного дерева

Если рассматривать задачу обхода дерева как единый последовательный процесс, то отдельные узлы по­сещаются в определенном порядке и могут считаться расположенными линейно. Для обхода бинарного дерева обычно используется один из трех способов:

1. обход сверху вниз – А, В, С (посетить корень до поддеревьев);

2. обход слева направо – В, А, С;

3. обход снизу вверх – В, С, А (посетить корень после поддеревьев). Каждая из этих трех процедур включает в себя в различном порядке следующие

шаги:

• просмотр корня поддерева,

• обход левого поддерева,

• обход правого поддерева. Обходя наше дерево и выписывая символы, находящиеся в узлах в том порядке, в котором они встречают­ ся, получим следующие последовательности:

1. сверху вниз: * + a / b c - d * e f ; (1)

2. слева направо: a + b / c * - e * f; (2)

3. снизу вверх: a b c / + d e f * - *; (3) Получили три формы записи выражений, известные как

1. – префиксная запись;

2. – инфиксная запись (привычная для нас форма, хотя и без скобок, необходимых для определения по­рядка выполнения операций);

3. – постфиксная запись.

Теперь можно описать эти три способа обхода как процедуры с явным параметром T, обозначающим де­рево и неявным P(T), означающим операцию, которую нужно выполнять с каждым узлом.

Введем определения: TYPE REF = ^NODE;

NODE = RECORD

LEFT, RIGHT: REF END; Легко выразить три перечисленных метода обхода как рекурсивные процедуры. Они также являются ил­люстрацией того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. Сверху вниз:

PROCEDURE PREFIX(T: REF); BEGIN IF T <> Nil THEN BEGIN

P(T); { обработка узла }

PREFIX(T^.LEFT);

PREFIX(T^.RIGHT);

END; END;

Слева направо: PROCEDURE INFIX(T: REF); BEGIN IF T <> Nil THEN BEGIN

INFIX(T^.LEFT);

P(T);

INFIX(T^.RIGHT);

END;

END;

Снизу вверх:

PROCEDURE POSTFIX(T: REF);

BEGIN

IF T <> Nil THEN BEGIN

POSTFIX(T^.LEFT);

POSTFIX(T^.RIGHT);

P(T);

END; END;

Заметим, что в этих процедурах ссылка Т передается как параметр-значение. Т.е. здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изменить значение, если бы Т передавался как параметр-переменная.

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

PROCEDURE PRINTTREE(T: REF, H: INTEGER); { T - указатель на вершину, H - сдвиг при печати } VAR I: INTEGER;

BEGIN { печать дерева Т со сдвигом Н } IF T <> Nil THEN

WHITH T^ DO BEGIN

PRINTTREE(LEFT, H+1); { обход левой ветви }

FOR I := 1 TO H DO WRITE(‘ ‘); { сдвиг }

WRITELN(KEY); { печать ключа }

PRINTTREE(RIGHT, H+1) { обход правой ветви }

END; END;

Вызывающая программа: BEGIN

ROOT := TREE(N); { УКАЗАТЕЛЬ КОРНЯ }

PRINTTREE(ROOT,0) END.

Задача поиска

Очень часто приходится решать следующую задачу: найти элемент с нужным значением ключа. Эту зада­чу приходится решать с использованием массивов, списков, деревьев. Эта задача решается по-разному в случае неупорядоченных или упорядоченных по возрастанию ключей элементов. В последнем случае можно не про­сматривать все элементы, а доходить только до элемента с ключом большим, чем требуемый.

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

Поставим задачу так: найти наименьший индекс (указатель) компоненты списка со значением ключа, рав­ным Х.

Последовательный поиск в массиве

Пусть массив:

VAR A: ARRAY[1..N] OF INTEGER;

X: INTEGER; FUNCTION LOC(X: INTEGER): INTEGER; VAR I: INTEGER; BEGIN

I := 0;

REPEAT

I := I+ 1

UNTIL (A[I] = X) OR (I = N);

IF A[I] <> X THEN LOC := 0

ELSE LOC := I END;

Процедура работает как для неупорядоченных, так и для упорядоченных массивов.

Неудобство функции в том, что проверка условия окончания сложная. Программу можно ускорить, если поставить "барьер", т.е. увеличить массив на один элемент и заслать туда значение искомого ключа.

I := 0; A[N+1] := X; REPEAT

I := I + 1; UNTIL A[ I ] = X;

IF I > N THEN LOC := 0 ELSE LOC := I; Среднее число просмотров m = N / 2.

Двоичный поиск в массиве (бинарный)

Применяется для упорядоченных массивов. При двоичном поиске используется метод деления пополам. Алгоритм: I := 1; J := N; REPEAT

K := (I + J) DIV 2;

IF X > A[K] THEN I := K + 1 ELSE J := K - 1 UNTIL (A[K] = X) OR (I > J) Число просмотров m = log₂N. При N = 100: последовательный поиск выполнится за 50 просмотров (m = 50), двоичный за 6,62 (m = 6,62).

Поиск в линейном списке

Как и в файле, поиск ведется строго последовательно. Он заканчивается либо когда элемент найден, либо когда достигнут конец списка. Самое простое решение: WHILE (P <> Nil) AND (P^.KEY <> X) DO

P := P^.NEXT Если элемента в списке нет, то при Р равном Nil нет следующего элемента P^.KEY. Поэтому надо ввести вторую часть проверки WHILE P<> Nil DO

IF P^.KEY = X THEN { выход из цикла } ELSE P := P^.NEXT; Лучше воспользоваться логической переменной (флажком): B := TRUE; WHILE (P <> Nil) AND B DO

IF P^.KEY = X THEN B := FALSE

ELSE P := P^.NEXT; Элемент не найден, если P = Nil и B = TRUE.

Поиск в двоичном дереве

Бинарные деревья часто используются для представления данных, элементы которых ищутся по уникаль­ному, только им присущему ключу.

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

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

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

Поиск в упорядоченном двоичном дереве проводится по единственному пути от корня к искомому узлу (т.к. он проходит по единственному пути от корня к искомому узлу) и может быть описан с помощью итераци­онной функции LOC.

FUNCTION LOC(X: INTEGER; T: REF): REF;

VAR FOUND: BOOLEAN;

BEGIN

FOUND := FALSE;

WHILE (T <> Nil) AND NOT FOUND DO

IF T^.KEY = X THEN FOUND := TRUE ELSE IF T^.KEY > X THEN T := T^.LEFT ELSE T := T^.RIGHT LOC := T END;

Функция LOC(X, T) имеет значение Nil, если в дереве с корнем Т не найдено ключа со значением Х. Условие выхода из цикла можно упростить, если организовать еще один тупиковый узел, на который замкнуть все "листья" дерева (рис. 20).

s

Рис. 20 Дерево поиска с барьером Получили дерево, у которого все листья как бы привязаны к одному якорю или барьеру. Тогда упрощенная процедура поиска запишется так: FUNCTION LOC(X: INTEGER; T: REF): REF; BEGIN

S^.KEY := X;

WHILE T^.KEY <> X DO

IF X < T^.KEY THEN T := T^.LEFT

ELSE T := T^.RIGHT; LOC := T END;

Если в дереве с корнем Т не найдено ключа со значением Х, то в этом случае LOC(X, T) принимает значе­ние S, т.е. ссылки на барьер. Ссылка на S просто принимает на себя роль ссылки Nil.

Включение нового узла в дерево

Хорошим примером, иллюстрирующим операцию включения нового узла в дерево, является построение частотного словаря. В этой задаче дана последовательность слов и нужно установить число появлений каждого слова. Это означает, что начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличи­вается счетчик его появлений, если нет – в дерево вставляется это новое слово (с начальным значением счетчи­ка, равным 1). Можно назвать эту задачу поиском по дереву с включением.

Для простоты предполагаем, что слова уже выделены из исходного текста, закодированы целыми числами и находятся во входном файле.

Пусть типы описаны следующим образом: TYPE REF = ^WORD; WORD = RECORD

KEY: INTEGER; COUNT: INTEGER; LEFT, RIGHT: REF END; Считаем, что есть исходный файл ключей F, а переменная ROOT указывает на корень дерева поиска. То­гда программа поиска с включением: RESET (F);

WHILE NOT EOF(F) DO BEGIN READ (F, X); SEARCH (X, ROOT) END;

Здесь SEARCH (X, ROOT) – процедура поиска. Её описание: PROCEDURE SEARCH (X: INTEGER; VAR P: REF); BEGIN

IF P = Nil THEN BEGIN NEW(P); WITH P^ DO BEGIN

KEY := X; COUNT := 1; LEFT := Nil; RIGHT :=Nil END END ELSE

IF X < P^A.KEY THEN SEARCH(X, P^A.LEFT) ELSE IF X > P^A.KEY THEN SEARCH(X, P^A.RIGHT) ELSE P^A.COUNT := Р^л.COUNT +1 END {SEARCH }

Заметим, что параметр Р передается как параметр-переменная, а не как параметр-значение. Это сущест­венно, т.к. ей присваивается новое значение ссылки.

С учетом этого, а также считая, что ключи слов читаются из файла INPUT, основную программу можно записать: BEGIN

ROOT := Nil;

WHILE NOT EOF DO BEGIN READ (K); SEARCH (K, ROOT); END;

PRINTTREE (ROOT, 0) END.

Переменные ROOT и К должны быть описаны как VAR ROOT: REF; К: INTEGER;

Для сравнения построим версии процедуры SEARCH без использования рекурсии. При этом для того, чтобы производить включение, надо помнить пройденный путь хотя бы на один шаг назад. Чтобы правильно включить (привязать) очередную включаемую компоненту, мы должны иметь ссылку на её предка и знать, в качестве какого поддерева она включается: правого или левого. Для этого вводятся две переменные: Р2 и D: PROCEDURE SEARCH (X: INTEGER; ROOT: REF); VAR PI, P2: REF; D: INTEGER; BEGIN

P2 := ROOT; PI := P2^A.RIGHT; D := 1; WHILE (PI <> Nil) AND (D <> 0) DO BEGIN P2 := P1; IF X < P1^A.KEY THEN

BEGIN PI := P1^A.LEFT; D:= -1 END ELSE IF X > P1^A.KEY THEN

BEGIN PI := P1^A.RIGHT; D := 1 END ELSE D := 0 END;

IF D = 0 THEN Pl^A.COUNT := P1^A.COUNT + 1 ELSE BEGIN NEW(Pl); WITH P1^A DO BEGIN

KEY := X; LEFT := Nil; RUGHT :=Nil; COUNT := 1 END;

IF D < 0 THEN P2^A.LEFT := PI ELSE IF D > 0 THEN P2^A.RIGHT := PI END END;

Здесь используются две ссылки: PI и Р2, причем в процессе поиска Р2 всегда указывает на предикат Р1^Л. Чтобы удовлетворить этому условию в начале поиска, вводится вспомогательный фиктивный элемент, на кото­рый указывает root. Начало действительного дерева поиска обозначается ссылкой ROOT^A.RIGHT. Поэтому программа должна начинаться операторами

NEW(ROOT); ROOT^A.RIGHT := Nil;

(вместо начального присваивания ROOT := Nil)

Удаление из дерева

Удаление - задача, обратная включению. Нужно построить алгоритм для удаления узла с ключом Х из де­рева с упорядоченными ключами. Удаление элемента обычно не так просто, как включение.

Оно просто в случае, когда удаляемый элемент является терминальным узлом или имеет одного потомка (рис. 21)

а) б)

В порождающий элемент У порождающего элемента

вносится ссылка Nil ссылка переносится на

порожденный удаляемым

узлом

Рис. 21 Удаление из дерева в простых случаях

Трудность возникает при удалении элементов с двумя потомками, т.к. мы не можем указывать одной ссылкой на два направления. В этом случае удаляемый элемент надо заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Ясно, что такие элементы не могут иметь более одного потомка (рис. 22).

б) г)

^д) ^е) Рис. 22 Удаление из дерева

Процесс удаления можно представить рекурсивной процедурой DELETE. Она различает три случая:

1. компоненты с ключом, равным Х, нет;

2. компонента с ключом Х имеет не более одного потомка;

3. компонента с ключом Х имеет двух потомков. PROCEDURE DELETE (X: INTEGER; VAR P: REF); VAR Q: REF;

PROCEDURE DEL(VAR R: REF);

BEGIN

IF R^A.RIGHT <> NIL THEN DEL(R^A.RIGHT)

ELSE BEGIN QMCEY := RMCEY; Q^A.COUNT := R^A.COUNT;

Q := R; R := R^A.LEFT END END { DEL } BEGIN { DELETE }

IF P = NIL THEN WRITELNC нет слова с заданным ключом ') ELSE

IF X < PMCEY THEN DELETE(X, P^A.LEFT)

ELSE

IF X > PMCEY THEN DELETE (X, P^A.RIGHT)

ELSE BEGIN { удаление по указателю Р } Q := P;

IF Q^A.RIGHT = NIL THEN P := Q^A.LEFT ELSE

IF Q^A.LEFT = NIL THEN P := Q^A.RIGHT ELSE DEL(Q^A.LEFT);

DISPOSE(Q) END END { DELETE }

Вспомогательная рекурсивная процедура DEL вызывается только в третьем случае. Она "спускается" вдоль самой правой ветви левого поддерева удаляемого узла Q^A и затем заменяет существующую информацию (ключ и счетчик) в Q^A соответствующими значениями самой правой компоненты R^A этого левого поддерева, после чего от R^A можно освободиться. Это делается с помощью стандартной процедуры DISPOSE(Q). Работу процедуры можно проверить по рис. 22.