Файл: Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией.pdf

4.4. Деревья
4.4.1. Основные понятия и определения
Мы видели, что последовательности и списки удобно определять следующим об%
разом. Последовательность (список) с базовым типом
T
– это:
1) пустая последовательность (список);
2) конкатенация (сцепление) некоторого элемента типа
T и последовательно%
сти с базовым типом
T
Тем самым рекурсия используется как средство определения метода структу%
рирования, а именно последовательности или итерации. Последовательности и итерации встречаются настолько часто, что их обычно рассматривают в качестве фундаментальных схем структурирования и поведения. Но нужно помнить, что их определить с помощью рекурсии можно, однако обратное неверно, тогда как рекурсию можно элегантно и эффективно использовать для определения гораздо более изощренных структур. Хорошо известный пример – деревья. Определим понятие дерева следующим образом. Дерево с базовым типом
T
– это либо:
1) пустое дерево, либо
2) узел типа
T
с конечным числом поддеревьев, то есть не соединяющихся меж%
ду собой деревьев с базовым типом
T
Сходство рекурсивных определений последовательностей и деревьев показы%
вает, что последовательность (список) – это дерево, в котором у каждого узла не больше одного поддерева. Поэтому список можно считать вырожденным деревом.
Есть несколько способов представить дерево. Например, рис. 4.17 показывает несколько таких представлений для дерева с базовым типом
T = CHAR
. Все эти представления изображают одну и ту же структуру и потому эквивалентны. Но именно представление в виде графа объясняет, почему здесь используют термин
«дерево». Довольно странно, что деревья чаще изображают растущими вниз или –
если использовать другую метафору – показывают корни деревьев. Однако последнее описание вносит путаницу, так как корнем (
root
) обычно называют верхний узел (A).
Упорядоченное дерево – это такое дерево, в котором для ветвей каждого узла фиксирован определенный порядок. Поэтому два упорядоченных дерева на рис. 4.18 различны. Узел y
, который находится непосредственно под узлом x
, на%
зывается (непосредственным) потомком узла x
; если x
находится на уровне i
, то говорят, что y
находится на уровне i+1
. Обратно, узел x
называется (непосредст%
венным) предком узла y. Уровень корня по определению равен нулю. Максималь%
ный уровень элементов в дереве называется его глубиной, или высотой.
Деревья

Динамические структуры данных
192
Рис. 4.17. Представление дерева посредством (a) вложенных подмножеств,
(b) скобочного выражения, (c) текста с отступами, (d) графа
Рис. 4.18. Два разных упорядоченных дерева

193
Если узел не имеет потомков, то он называется концевым (терминальным), или
листом; узел, не являющийся концевым, называется внутренним. Количество
(непосредственных) потомков внутреннего узла – это его степень. Максимальная степень всех узлов называется степенью дерева. Число ветвей или ребер, по кото%
рым нужно пройти, чтобы попасть из корня в узел x
, называется его длиной пути.
Длина пути корня равна нулю, его непосредственных потомков – 1 и т. д. Вообще,
длина пути узла на уровне i
равна i
. Длина путей дерева определяется как сумма длин путей всех его компонент. Ее еще называют длиной внутренних путей. На%
пример, у дерева на рис. 4.17 длина внутренних путей равна 36. Очевидно, сред%
няя длина пути равна
P
int
= (S
S
S
S
Si: 1
≤ i ≤ n: n i
× i) / n где n
i
– число узлов на уровне i
. Чтобы определить длину внешних путей, расши%
рим дерево особыми дополнительными узлами всюду, где в исходном дереве от%
сутствовало поддерево. Здесь имеется в виду, что все узлы должны иметь одина%
ковую степень, а именно степень дерева. Такое расширение дерева равнозначно заполнению пустых ветвей, причем у добавляемых дополнительных узлов, конеч%
но, потомков нет. Дерево с рис. 4.17, расширенное дополнительными узлами, по%
казано на рис. 4.19, где дополнительные узлы показаны квадратиками. Длина вне%
шних путей теперь определяется как сумма длин путей всех дополнительных узлов. Если число дополнительных узлов на уровне i
равно m
i
, то средняя длина внешнего пути равна
P
ext
= (S
S
S
S
Si: 1
≤ i ≤ m i
× i) / m
Длина внешних путей дерева на рис. 4.19 равна 120.
Число m
дополнительных узлов, которые нужно добавить к дереву степени d
,
определяется числом n
исходных узлов. Заметим, что к каждому узлу ведет в точ%
ности одно ребро. Таким образом, в расширенном дереве m + n ребер. С другой
Рис. 4.19. Троичное дерево, расширенное дополнительными узлами
Деревья

Динамические структуры данных
194
стороны, из каждого исходного узла выходит d
ребер, из дополнительных узлов –
ни одного. Поэтому всего имеется d*n + 1
ребер, где
1
соответствует ребру, веду%
щему к корню. Две формулы дают следующее уравнение, связывающее число m
дополнительных узлов и число n
исходных узлов: d
×
n + 1 = m + n
, откуда m = (d–1)
× n + 1
Дерево заданной высоты h
будет иметь максимальное число узлов, если у всех узлов есть d
поддеревьев, кроме узлов на уровне h
, у которых поддеревьев нет.
Тогда у дерева степени d
на уровне 0 есть 1 узел (а именно корень), на уровне 1 –
d его потомков, на уровне 2 – d
2
потомков d
узлов уровня 1 и т. д. Отсюда получа%
ем выражение
N
d
(h) = S
S
S
S
Si: 0
≤ i < h: d i
для максимального числа узлов дерева высоты h
и степени d
. В частности, для d = 2
получаем
N
2
(h) = 2
h
– 1
Особенно важны упорядоченные деревья степени 2. Их называют двоичными
(бинарными) деревьями. Определим упорядоченное двоичное дерево как конеч%
ное множество элементов (узлов), которое либо пусто, либо состоит из корня
(корневого узла) с двумя отдельными двоичными деревьями, которые называют
левым и правым поддеревом корня. В дальнейшем мы будем в основном зани%
маться двоичными деревьями, поэтому под деревом всегда будем подразумевать
упорядоченное двоичное дерево. Деревья степени больше 2 называются сильно вет
вящимися деревьями, им посвящен раздел 4.7.1.
Знакомые примеры двоичных деревьев – семейная родословная, где отец и мать индивида представлены узлами%потомками (!); таблица результатов теннисного турнира, где каждому поединку соответствует узел, в котором запи%
сан победитель, а две предыдущие игры соперников являются потомками;
арифметическое выражение с двухместными операциями, где каждому оператору соответствует узел, а операндам – поддеревья (см. рис. 4.20).
Рис. 4.20. Представление в виде дерева для выражения
(a + b/c) * (d – e*f)

195
Обратимся теперь к проблеме представления деревьев. Изображение таких рекурсивных конструкций в виде ветвящихся структур подсказывает, что здесь можно использовать наш аппарат указателей. Очевидно, нет смысла объявлять переменные с фиксированной древесной структурой; вместо этого фиксирован%
ную структуру, то есть фиксированный тип, будут иметь узлы, для которых сте%
пень дерева определяет число указательных компонент, ссылающихся на подде%
ревья узла. Очевидно, ссылка на пустое дерево обозначается с помощью
NIL
Следовательно, дерево на рис. 4.20 состоит из компонент определенного ниже типа и может тогда быть построено, как показано на рис. 4.21.
TYPE Node =
POINTER TO NodeDesc;
TYPE NodeDesc = RECORD op: CHAR; left, right: Node END
Рис. 4.21. Дерево рис. 4.20, представленное как связная структура данных
Прежде чем исследовать, какую пользу можно извлечь, применяя деревья,
и как выполнять операции над ними, дадим пример программы, которая строит дерево. Предположим, что нужно построить дерево, значениями в узлах которого являются n
чисел, считываемых из входного файла. Чтобы сделать задачу инте%
ресней, будем строить дерево с n
узлами, имеющее минимальную высоту. Чтобы получить минимальную высоту при заданном числе узлов, нужно размещать мак%
симальное возможное число узлов на всех уровнях, кроме самого нижнего. Оче%
видно, этого можно достичь, распределяя новые узлы поровну слева и справа от каждого узла. Это означает, что мы строим дерево для заданного n
так, как показа%
но на рис. 4.22 для n = 1, ... , 7
Правило равномерного распределения при известном числе узлов n лучше всего сформулировать рекурсивно:
1. Использовать один узел в качестве корня.
2. Построить таким образом левое поддерево с числом узлов nl = n DIV 2 3. Построить таким образом правое поддерево с числом узлов nr = n – nl – 1
Деревья

Динамические структуры данных
196
Это правило реализуется рекурсивной процедурой, которая читает входной файл и строит идеально сбалансированное дерево. Вот определение: дерево явля%
ется идеально сбалансированным, если для каждого узла число узлов в левом и правом поддеревьях отличается не больше чем на 1.
TYPE Node = POINTER TO RECORD
(* ADruS441_BalancedTree *)
key: INTEGER; left, right: Node
END;
VAR R: Texts.Reader; W: Texts.Writer; root: Node;
PROCEDURE tree (n: INTEGER): Node;
(* n *)
VAR new: Node;
x, nl, nr: INTEGER;
BEGIN
IF n = 0 THEN new := NIL
ELSE nl := n DIV 2; nr := n–nl–1;
NEW(new); Texts.ReadInt(R, new.key);
new.key := x; new.left := tree(nl); new.right := tree(nr)
END;
RETURN new
END tree;
PROCEDURE PrintTree (t: Node; h: INTEGER);
(* t h *)
VAR i: INTEGER;
BEGIN
IF t # NIL THEN
Рис. 4.22. Идеально сбалансированные деревья

197
PrintTree(t.left, h+1);
FOR i := 1 TO h DO Texts.Write(W, TAB) END;
Texts.WriteInt(W, t.key, 6); Texts.WriteLn(W);
PrintTree(t.right, h+1)
END
END PrintTree;
Например, предположим, что имеются входные данные для дерева с 21 узлами:
8 9 11 15 19 20 21 7 3 2 1 5 6 4 13 14 10 12 17 16 18
Вызов root := tree(21)
читает входные данные и строит идеально сбалансиро%
ванное дерево, показанное на рис. 4.23. Отметим простоту и прозрачность этой программы, построенной с использованием рекурсивных процедур. Очевидно,
что рекурсивные алгоритмы особенно удобны там, где нужно обрабатывать ин%
формацию, структура которой сама определена рекурсивно. Этот факт снова про%
является в процедуре, которая печатает получившееся дерево: если дерево пусто,
то ничего не печатается, для поддерева на уровне
L
сначала печатается его левое поддерево, затем узел с отступом в
L
символов табуляции и, наконец, его правое поддерево.
Рис. 4.23. Дерево, порожденное программой tree
4.4.2. Основные операции
с двоичными деревьями
Есть много операций, которые может понадобиться выполнить с древесной струк%
турой; например, часто нужно выполнить заданную процедуру
P
в каждом узле дерева. Тогда
P
следует считать параметром более общей задачи обхода всех уз%
лов, или, как обычно говорят, обхода дерева. Если мы рассмотрим такой обход как
Деревья

Динамические структуры данных
198
единый последовательный процесс, то получится, что от%
дельные узлы посещаются в некотором конкретном поряд%
ке и как бы расставляются в линию. Описание многих алгоритмов сильно упрощается, если обсуждать последо%
вательность обработки элементов в терминах какого%либо отношения порядка. Из структуры деревьев естественно определяются три основных отношения порядка. Их, как и саму древесную структуру, удобно выражать на языке ре%
курсии. Имея в виду двоичное дерево на рис. 4.24, где
R
обозначает корень, а
A
и
B
– левое и правое поддеревья, три упомянутых отношения порядка таковы:
1. Прямой порядок (preorder):
R, A, B
(корень до поддеревьев)
2. Центрированный порядок (inorder):
A, R, B
3. Обратный порядок (postorder):
A, B, R
(корень после поддеревьев)
Обходя дерево на рис. 4.20 и записывая соответствующие литеры по мере посещения узлов, получаем следующие упорядоченные последовательности:
1. Прямой порядок:
* + a / b c – d * e f
2. Центрированный порядок:
a + b / c * d – e * f
3. Обратный порядок:
a b c / + d e f * – *
Здесь можно узнать три формы записи выражений: прямой обход дерева выра%
жения дает префиксную нотацию, обратный – постфиксную, а центрированный –
обычную инфиксную, правда, без скобок, которые нужны для уточнения приори%
тетов операций.
Сформулируем теперь эти три метода обхода в виде трех конкретных про%
грамм с явным параметром t
, обозначающим дерево, которое нужно обработать,
и с неявным параметром
P
, обозначающим операцию, применяемую к каждому узлу. Подразумевается следующее определение:
TYPE Node = POINTER TO RECORD ... left, right: Node END
Теперь три метода легко формулируются в виде рекурсивных процедур; этим снова подчеркивается тот факт, что операции с рекурсивно определенными структурами данных удобней всего определять в виде рекурсивных алгоритмов.
PROCEDURE preorder (t: Node);
BEGIN
IF t # NIL THEN
P(t); preorder(t.left); preorder(t.right)
END
END preorder
PROCEDURE inorder (t: Node);
BEGIN
IF t # NIL THEN
inorder(t.left); P(t); inorder(t.right)
END
END inorder
Рис. 4.24. Двоичное дерево

199
PROCEDURE postorder (t: Node);
BEGIN
IF t # NIL THEN
postorder(t.left); postorder(t.right); P(t)
END
END postorder
Заметим, что указатель t
передается по значению. Этим выражается тот факт,
что передается ссылка на рассматриваемое поддерево, а не переменная, чьим зна%
чением является эта ссылка и чье значение могло бы быть изменено, если бы t
передавался как параметр%переменная.
Пример обхода дерева – печать с правильным числом отступов, соответству%
ющим уровню каждого узла.
Двоичные деревья часто используют для представления набора данных, к эле%
ментам которого нужно обращаться по уникальному ключу. Если дерево организовано таким образом, что для каждого узла t
i все ключи в его левом подде%
реве меньше, чем ключ узла t
i
, а ключи в правом поддереве больше, чем ключ t
i
, то такое дерево называют деревом поиска. В дереве поиска можно найти любой ключ,
стартуя с корня и спускаясь в левое или правое поддерево в зависимости только от значения ключа в текущем узле. Мы видели, что n
элементов можно организовать в двоичное дерево высоты всего лишь log(n)
. Поэтому поиск среди n
элементов можно выполнить всего лишь за log(n)
сравнений, если дерево идеально сбаланси%
ровано. Очевидно, дерево гораздо лучше подходит для организации такого набора данных, чем линейный список из предыдущего раздела. Так как поиск здесь про%
ходит по единственному пути от корня к искомому узлу, его легко запрограмми%
ровать с помощью цикла:
PROCEDURE locate (x: INTEGER; t: Node): Node;
BEGIN
WHILE (t # NIL) & (t.key # x) DO
IF t.key < x THEN t := t.right ELSE t := t.left END
END;
RETURN t
END locate
Функция locate(x, t)
возвращает значение
NIL
, если в дереве, начинающемся с корня t
, не найдено узла со значением ключа x
. Как и в случае поиска в списке,
сложность условия завершения подсказывает лучшее решение, а именно исполь%
зование барьера. Этот прием применим и при работе с деревом. Аппарат указателей позволяет использовать единственный, общий для всех ветвей узел%барьер. Полу%
чится дерево, у которого все листья привязаны к общему «якорю» (рис. 4.25). Барь%
ер можно считать общим представителем всех внешних узлов, которыми было расширено исходное дерево (см. рис. 4.19):
PROCEDURE locate (x: INTEGER; t: Node): Node;
BEGIN
s.key := x; (* *)
WHILE t.key # x DO
Деревья

Динамические структуры данных
200
IF t.key < x THEN t := t.right ELSE t := t.left END
END;
RETURN t
END locate
Заметим, что в этом случае locate(x, t)
возвращает значение s
вместо
NIL
, то есть указатель на барьер, если в дереве с корнем t
не найдено ключа со значением x
4.4.3. Поиск и вставка в деревьях
Вряд ли всю мощь метода динамического размещения с использованием указа%
телей можно вполне оценить по примерам, в которых набор данных сначала стро%
ится, а в дальнейшем не меняется. Интересней примеры, в которых дерево меня%
ется, то есть растет и/или сокращается, во время выполнения программы. Это как раз тот случай, когда оказываются непригодными другие представления данных,
например массив, и когда лучшее решение получается при использовании дерева с элементами, связанными посредством указателей.
Мы сначала рассмотрим случай только растущего, но никогда не сокращаю%
щегося дерева. Типичный пример – задача составления частотного словаря, кото%
рую мы уже рассматривали в связи со связными списками. Сейчас мы рассмотрим ее снова. В этой задаче дана последовательность слов, и нужно определить число вхождений каждого слова. Это означает, что каждое слово ищется в дереве (кото%
рое вначале пусто). Если слово найдено, то счетчик вхождений увеличивается;
в противном случае оно включается в дерево со счетчиком, выставленным в 1. Мы будем называть эту задачу поиск по дереву со вставкой. Предполагается, что опре%
делены следующие типы данных:
Рис. 4.25. Дерево поиска с барьером (узел s)

201
TYPE Node = POINTER TO RECORD
key, count: INTEGER;
left, right: Node
END
Как и раньше, не составляет труда найти путь поиска. Однако если он заверша%
ется тупиком (то есть приводит к пустому поддереву, обозначенному указателем со значением
NIL
), то данное слово нужно вставить в дерево в той точке, где было пустое поддерево. Например, рассмотрим двоичное дерево на рис. 4.26 и вставку имени
Paul
. Результат показан пунктирными линиями на том же рисунке.
Рис. 4.26. Вставка в упорядоченное двоичное дерево
Процесс поиска формулируется в виде рекурсивной процедуры. Заметим, что ее параметр p
передается по ссылке, а не по значению. Это важно, так как в случае вставки переменной, содержавшей значение
NIL
, нужно присвоить новое указа%
тельное значение. Для входной последовательности из 21 числа, которую мы уже использовали для построения дерева на рис. 4.23, процедура поиска и вставок дает двоичное дерево, показанное на рис. 4.27; для каждого ключа k выполняется вызов search(k, root)
, где root
– переменная типа
Node
PROCEDURE PrintTree (t: Node; h: INTEGER);
(* ADruS443_Tree *)
(* t h *)
VAR i: INTEGER;
BEGIN
IF t # NIL THEN
PrintTree(t.left, h+1);
FOR i := 1 TO h DO Texts.Write(W, TAB) END;
Texts.WriteInt(W, t.key, 6); Texts.WriteLn(W);
PrintTree(t.right, h+1)
END
END PrintTree;
Деревья

Динамические структуры данных
202
PROCEDURE search (x: INTEGER; VAR p: Node);
BEGIN
IF p = NIL THEN (*x ; *)
NEW(p); p.key := x; p.count := 1; p.left := NIL; p.right := NIL
ELSIF x < p.key THEN search(x, p.left)
ELSIF x > p.key THEN search(x, p.right)
ELSE INC(p.count)
END
END search
И снова использование барьера немного упрощает программу. Ясно, что в на%
чале программы переменная root должна быть инициализирована указателем на барьер s вместо значения
NIL
, а перед каждым поиском искомое значение x
долж%
но быть присвоено полю ключа барьера:
PROCEDURE search (x: INTEGER; VAR p: Node);
BEGIN
IF x < p.key THEN search(x, p.left)
ELSIF x > p.key THEN search(x, p.right)
ELSIF p # s THEN INC(p.count)
ELSE (* *)
NEW(p); p.key := x; p.left := s; p.right := s; p.count := 1
END
END search
Хотя целью этого алгоритма был поиск, его можно использовать и для сор%
тировки. На самом деле он очень похож на сортировку вставками, а благодаря использованию дерева вместо массива исчезает необходимость перемещать ком%
поненты, стоящие выше точки вставки. Древесную сортировку можно запрограм%
Рис. 4.27. Дерево поиска, порожденное процедурой поиска и вставки

203
мировать так, что она будет почти так же эффективна, как и лучшие известные методы сортировки массивов. Однако нужны некоторые предосторожности. Если обнаружено совпадение, новый элемент тоже нужно вставить. Если случай x = p.key обрабатывать так же, как и случай x > p.key
, то алгоритм сортировки будет устой%
чивым, то есть элементы с равными ключами будут прочитаны в том же относи%
тельном порядке при просмотре дерева в нормальном порядке, в каком они встав%
лялись.
Вообще говоря, есть и более эффективные методы сортировки, но для прило%
жений, где нужны как поиск, так и сортировка, можно уверенно рекомендовать алгоритм поиска и вставки. Он действительно очень часто применяется в компи%
ляторах и банках данных для организации объектов, которые нужно хранить и искать. Хорошим примером здесь является построение указателя перекрестных ссылок для заданного текста; мы уже обращались к этому примеру для иллю%
страции построения списков.
Итак, наша задача – написать программу, которая читает текст и печатает его,
последовательно нумеруя строки, и одновременно собирает все слова этого текста вместе с номерами строк, в которых встретилось каждое слово. По завершении просмотра должна быть построена таблица, содержащая все собранные слова в алфавитном порядке вместе с соответствующими списками номеров строк.
Очевидно, дерево поиска (иначе лексикографическое дерево) будет прекрасным кандидатом для представления информации о словах, встречающихся в тексте.
Теперь каждый узел будет не только содержать слово в качестве значения ключа,
но и являться началом списка номеров строк. Каждую запись о вхождении слова в текст будем называть «элементом» (item; нехватка синонимов для перевода ком%
пенсируется кавычками – прим. перев.).
Таким образом, в данном примере фигури%
руют как деревья, так и линейные списки. Программа состоит из двух главных час%
тей, а именно из фазы просмотра и фазы печати таблицы. Последняя – простая адаптация процедуры обхода дерева; здесь при посещении каждого узла выполня%
ется печать значения ключа (слова) вместе с соответствующим списком номеров строк. Ниже даются дополнительные пояснения о программе, приводимой далее.
Таблица 4.3 показывает результаты обработки текста процедуры search
1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы.
2. Так как длина слов может сильно меняться, их литеры хранятся в особом массиве%буфере, а узлы дерева содержат индекс первой буквы ключа.
3. Желательно, чтобы в указателе перекрестных ссылок номера строк печата%
лись в возрастающем порядке.
Поэтому список «элементов» должен сохранять порядок соответствующих вхождений слова в тексте. Из этого требования вытекает, что нужны два указа%
теля в каждом узле, причем один ссылается на первый, а другой – на последний
«элемент» списка. Мы предполагаем наличие глобального объекта печати
W
,
а также переменной, представляющей собой текущий номер строки в тексте.
Деревья

Динамические структуры данных
204
CONST WordLen = 32;
(* ADruS443_CrossRef *)
TYPE Word = ARRAY WordLen OF CHAR;
Item = POINTER TO RECORD (*" "*)
lno: INTEGER; next: Item
END;
Node = POINTER TO RECORD
key: Word;
first, last: Item; (**)
left, right: Node (* *)
END;
VAR line: INTEGER;
PROCEDURE search (VAR w: Node; VAR a: Word);
VAR q: Item;
BEGIN
IF w = NIL THEN (* ; *)
NEW(w); NEW(q); q.lno := line;
COPY(a, w.key); w.first := q; w.last := q; w.left := NIL; w.right := NIL
ELSIF w.key < a THEN search(w.right, a)
ELSIF w.key > a THEN search(w.left, a)
ELSE (* *)
NEW(q); q.lno := line; w.last.next := q; w.last := q
END
END search;
PROCEDURE Tabulate (w: Node);
VAR m: INTEGER; item: Item;
BEGIN
IF w # NIL THEN
Tabulate(w.left);
Texts.WriteString(W, w.key); Texts.Write(W, TAB); item := w.first; m := 0;
REPEAT
IF m = 10 THEN
Texts.WriteLn(W); Texts.Write(W, TAB); m := 0
END;
INC(m); Texts.WriteInt(W, item.lno, 6); item := item.next
UNTIL item = NIL;
Texts.WriteLn(W); Tabulate(w.right)
END
END Tabulate;
PROCEDURE CrossRef (VAR R: Texts.Reader);
VAR root: Node;
i: INTEGER; ch: CHAR; w: Word;
(* # ˆ W*)
BEGIN
root := NIL; line := 0;
Texts.WriteInt(W, 0, 6); Texts.Write(W, TAB);
Texts.Read(R, ch);
WHILE R.eot DO
IF ch = 0DX THEN (* *)
Texts.WriteLn(W);

205
INC(line);
Texts.WriteInt(W, line, 6); Texts.Write(W, 9X);
Texts.Read(R, ch)
ELSIF ("A" <= ch) & (ch <= "Z") OR ("a" <= ch) & (ch <= "z") THEN
i := 0;
REPEAT
IF i < WordLen–1 THEN w[i] := ch; INC(i) END;
Texts.Write(W, ch); Texts.Read(R, ch)
UNTIL (i = WordLen–1) OR (("A" <= ch) & (ch <= "Z")) &
(("a" <= ch) & (ch <= "z")) & (("0" <= ch) & (ch <= "9"));
w[i] := 0X; (* *)
search(root, w)
ELSE
Texts.Write(W, ch);
Texts.Read(R, ch)
END;
END;
Texts.WriteLn(W); Texts.WriteLn(W); Tabulate(root)
END CrossRef;
Таблица 4.3.
Таблица 4.3.
Таблица 4.3.
Таблица 4.3.
Таблица 4.3. Пример выдачи генератора перекрестных ссылок
0 PROCEDURE search (x: INTEGER; VAR p: Node);
1 BEGIN
2 IF x < p.key THEN search(x, p.left)
3 ELSIF x > p^key THEN search(x, p.right)
4 ELSIF p # s THEN INC(p.count)
5 ELSE (*insert*) NEW(p);
6 p.key := x; p.left := s; p.right := s; p.count := 1 7 END
8 END
BEGIN
1
ELSE
5
ELSIF
3 4
END
7 8
IF
2
INC
4
INTEGER
0
NEW
5
Node
0
PROCEDURE
0
THEN
2 3 4
VAR
0
count
4 6
insert
5
key
2 3 6
left
2 6
p
0 2 2 3 3 4 4 5 6 6 6 6
right
3 6
s
4 6 6
search
0 2 3
x
0 2 2 3 3 6
Деревья

Динамические структуры данных
206

1   ...   12   13   14   15   16   17   18   19   ...   22

4.4.4. Удаление из дерева
Обратимся теперь к операции, противоположной вставке, то есть удалению.
Наша цель – построить алгоритм для удаления узла с ключом x
из дерева с упоря%
доченными ключами. К сожалению, удаление элемента в общем случае сложнее,
чем вставка. Его несложно выполнить, если удаляемый узел является концевым или имеет единственного потомка. Трудность – в удалении элемента с двумя по%
томками, так как нельзя заставить один указатель указывать в двух направлениях.
В этой ситуации удаляемый элемент должен быть заменен либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева,
причем оба этих элемента не должны иметь более одного потомка. Детали показаны ниже в рекурсивной процедуре delete
. В ней различаются три случая:
1. Отсутствует компонента с ключом, равным x
2. У компоненты с ключом x
не более одного потомка.
3. У компоненты с ключом x
два потомка.
PROCEDURE delete (x: INTEGER; VAR p: Node);
(* ADruS444_Deletion *)
(* *)
PROCEDURE del (VAR r: Node);
BEGIN
IF r.right # NIL THEN
del(r.right)
ELSE
p.key := r.key; p.count := r.count;
r := r.left
END
END del;
BEGIN
IF p = NIL THEN (* *)
ELSIF x < p.key THEN delete(x, p.left)
ELSIF x > p.key THEN delete(x, p.right)
ELSE
(* p^:*)
IF p.right = NIL THEN p := p.left
ELSIF p.left = NIL THEN p := p.right
ELSE del(p.left)
END
END
END delete
Вспомогательная рекурсивная процедура del активируется только в случае 3.
Она спускается по крайней правой ветви левого поддерева элемента q^
, который должен быть удален, и затем заменяет содержимое (ключ и счетчик) записи q^
на соответствующие значения крайней правой компоненты r^
этого левого подде%
рева, после чего запись r^
более не нужна.
Заметим, что мы не упоминаем процедуру, которая была бы обратной для
NEW
и указывала бы, что память больше не нужна и ее можно использовать для других

207
целей. Вообще предполагается, что вычислительная система распознает ненуж%
ную более переменную по тому признаку, что никакие другие переменные больше на нее не указывают, и что поэтому к ней больше невозможно обратиться. Такой механизм называется сборкой мусора. Это средство не языка программирования,
а, скорее, его реализации.
Рисунок 4.28 иллюстрирует работу процедуры delete
. Рассмотрим дерево (a);
затем последовательно удалим узлы с ключами 13, 15, 5, 10. Получающиеся дере%
вья показаны на рис. 4.28 (b–e).
Рис. 4.28. Удаление из дерева
4.4.5. Анализ поиска по дереву со вставками
Вполне естественно испытывать подозрения в отношении алгоритма поиска по дереву со вставкой. По крайней мере, до получения дополнительных сведений о его поведении должна оставаться толика скептицизма. Многих программистов сначала беспокоит тот факт, что в общем случае мы не знаем, как будет расти дере%
во и какую форму оно примет. Можно только догадываться, что скорее всего оно не получится идеально сбалансированным. Поскольку среднее число сравнений,
нужное для отыскания ключа в идеально сбалансированном дереве с n
узлами,
примерно равно log(n)
, число сравнений в дереве, порожденном этим алгоритмом,
будет больше. Но насколько больше?
Прежде всего легко определить наихудший случай. Предположим, что все ключи поступают в уже строго возрастающем (или убывающем) порядке. Тогда
Деревья

Динамические структуры данных
208
каждый ключ присоединяется непосредственно справа (слева) к своему предку,
и получается полностью вырожденное дерево, то есть по сути линейный списк.
Средние затраты на поиск тогда составят n/2
сравнений. В этом наихудшем слу%
чае эффективность алгоритма поиска, очевидно, очень низка, что вроде бы под%
тверждает наш скептицизм. Разумеется, остается вопрос, насколько вероятен этот случай. Точнее, хотелось бы знать длину a
n пути поиска, усредненную по всем n
ключам и по всем n!
деревьям, которые порождаются из n!
перестановок n
различ%
ных исходных ключей. Эта задача оказывается довольно простой и обсуждается здесь как типичный пример анализа алгоритма, а также ввиду практической важности результата.
Пусть даны n
различных ключей со значениями
1, 2, ... ,
n
. Предположим, что они поступают в случайном порядке.
Вероятность для первого ключа – который становится корневым узлом – иметь значение i
равна
1/n
. В конечном счете его левое поддерево будет содержать i
%
1
узлов, а его правое поддерево – n
%
i узлов (см. рис. 4.29). Среднюю дли%
ну пути в левом поддереве обозначим как a
i–1
, а в правом как a
n–i
, снова предполагая, что все возможные перестанов%
ки остальных n
%
1
ключей равновероятны. Средняя длина пути в дереве с n
узлами равна сумме произведений уровня каждого узла, умноженного на вероятность обращения к нему. Если предположить, что все узлы ищутся с равной вероятностью, то a
n
= (S
S
S
S
Si: 1
≤ i ≤ n: p i
) / n где p
i
– длина пути узла i
В дереве на рис. 4.29 узлы разделены на три класса:
1)
i–1
узлов в левом поддереве имеют среднюю длину пути a
i–1
;
2) у корня длина пути равна 0;
3)
n–i узлов в правом поддереве имеют среднюю длину пути a
n–i
Получаем, что вышеприведенная формула выражается как сумма членов 1 и 3:
a n
(i)
= ((i–1) * a i–1
+ (n–i) * a n–i
) / n
Искомая величина a
n есть среднее величин a
n
(i)
по всем i = 1 ... n
, то есть по всем деревьям с ключами
1, 2, ... , n в корне:
a n
= (S
S
S
S
Si: 1
≤ i ≤ n: (i–1) a i–1
+ (n–i) a n–i
) / n
2
= 2 * (S
S
S
S
Si: 1
≤ i ≤ n: (i–1) a i–1
) / n
2
= 2 * (S
S
S
S
Si: 1
≤ i < n: i * a i
) / n
2
Это уравнение является рекуррентным соотношением вида a
n
= f
1
(a
1
, a
2
, ... , a n-1
)
. Из него получим более простое рекуррентное соотноше%
ние вида a
n
= f
2
(a n–1
)
. Следующее выражение (1) получаетcя выделением после%
днего члена, а (2) – подстановкой n–1
вместо n
:
Рис. 4.29. Распреде:
ление весов по ветвям

209
(1) a n
= 2*(n–1) * a n–1
/n
2
+ 2 * (S
S
S
S
Si: 1
≤ i < n–1: i * a i
) / n
2
(2) a n–1
= 2 * (S
S
S
S
Si: 1
≤ i < n–1: i * a i
) / (n–1)
2
Умножая (2) на
(n–1)
2
/n
2
, получаем:
(3) 2 * (S
S
S
S
Si: 1
≤ i < n–1: i * a i
) / n
2
= a n–1
* (n–1)
2
/n
2
Подставляя правую часть уравнения (3) в (1), находим:
a n
= 2 * (n–1) * a n–1
/ n
2
+ a n–1
* (n–1)
2
/ n
2
= a n–1
* (n–1)
2
/ n
2
В итоге получается, что a
n допускает нерекурсивное замкнутое выражение через гармоническую сумму:
H
n
= 1 + 1/2 + 1/3 + … + 1/n a
n
= 2 * (H
n
* (n+1)/n – 1)
Из формулы Эйлера (используя константу Эйлера g =
0.577...)
H
n
= g + ln n + 1/12n
2
+ ...
выводим приближенное значение для больших n
:
a n
= 2 * (ln n + g – 1)
Так как средняя длина пути в идеально сбалансированном дереве примерно равна a
n
' = log n – 1
то, пренебрегая константами, не существенными при больших n
, получаем:
lim (a n
/a n
') = 2 * ln(n) / log(n) = 2 ln(2) = 1.386...
Чему учит нас этот результат? Он говорит нам, что усилия, направленные на то, чтобы всегда строить идеально сбалансированное дерево вместо случайного,
позволяют нам ожидать – всегда предполагая, что все ключи ищутся с равной ве%
роятностью, – среднее сокращение длины пути поиска самое большее на 39%.
Нужно подчеркнуть слово среднее, поскольку сокращение может, конечно, быть намного больше в том неудачном случае, когда создаваемое дерево полностью выродилось в список, вероятность чего, однако, очень низка. В этой связи стоит отметить, что средняя длина пути случайного дерева тоже растет строго логариф%
мически с ростом числа его узлов, несмотря на то что длина пути для наихудшего случая растет линейно.
Число 39% накладывает ограничение на объем дополнительных усилий, кото%
рые можно с пользой потратить на какую%либо реорганизацию дерева после вставки ключей. Естественно, полезная отдача от таких усилий сильно зависит от отношения числа обращений к узлам (извлечение информации) к числу вставок
(обновлений). Чем выше это отношение, тем больше выигрыш от процедуры реорганизации. Число 39% достаточно мало, чтобы в большинстве приложений улучшение простого алгоритма вставки в дерево не оправдывало себя, за исклю%
чением случаев, когда велики число узлов и отношение числа обращений к числу вставок.
Деревья

Динамические структуры данных
210
4.5. Сбалансированные деревья
Из предыдущего обсуждения ясно, что процедура вставки, всегда восстанавлива%
ющая идеальную сбалансированность дерева, вряд ли может быть полезной, так как восстановление идеального баланса после случайной вставки – операция довольно нетривиальная. Возможный путь повышения эффективности – попытаться найти менее жесткое определение баланса. Такой неидеальный критерий должен приво%
дить к более простым процедурам реорганизации дерева за счет незначительного ухудшения средней эффективности поиска. Одно такое определение сбалансиро%
ванности было дано Адельсоном%Вельским и Ландисом [4.1]. Вот оно:
Дерево называется сбалансированным в том и только в том случае, когда для каждого узла высота двух его поддеревьев отличается не более чем на 1.
Деревья, удовлетворяющие этому условию, часто называют по именам их изобретателей АВЛдеревьями. Мы будем называть их просто сбалансирован%
ными, так как этот критерий оказался в высшей степени удачным. (Заметим, что все идеально сбалансированные деревья также являются АВЛ%деревьями.)
Это определение не только само простое, но и приводит к не слишком сложной процедуре балансировки, а средняя длина поиска здесь практически не отличает%
ся от случая идеально сбалансированных деревьев. Следующие операции могут выполняться для сбалансированных деревьев за время порядка
O(log n)
даже в наихудшем случае:
1) поиск узла с заданным ключом;
2) вставка узла с заданным ключом;
3) удаление узла с заданным ключом.
Эти утверждения суть прямые следствия теоремы, доказанной Адельсоном%
Вельским и Ландисом, которая гарантирует, что сбалансированное дерево не бо%
лее чем на 45% превосходит по высоте его идеально сбалансированный вариант,
независимо от числа узлов. Если обозначить высоту сбалансированного дерева с n
узлами как h
b
(n)
, то log(n+1) < h b
(n) < 1.4404*log(n+2) – 0.328
Ясно, что оптимум достигается для идеально сбалансированного дерева с n = 2k–1
. Но какова структура наихудшего АВЛ%дерева? Чтобы найти макси%
мальную высоту h
всех сбалансированных деревьев с n
узлами, фиксируем высо%
ту h
и попытаемся построить сбалансированное дерево с минимальным числом узлов. Эта стратегия предпочтительна потому, что, как и в случае с минимальной высотой, это значение высоты может быть получено только для некоторых конк%
ретных значений n
. Обозначим такое дерево высоты h
как
T
h
. Очевидно, что
T
0
–
пустое дерево, а
T
1
– дерево с одним узлом. Чтобы построить дерево
T
h для h > 1
,
присоединим к корню два поддерева, у которых число узлов снова минимально.
Поэтому поддеревья принадлежат этому же классу
T
. Очевидно, одно поддерево должно иметь высоту h–1
, а другое тогда может иметь высоту на единицу меньше,
то есть h–2
Рисунок 4.30 показывает деревья с высотой 2, 3 и 4. Поскольку прин%

211
цип их построения сильно напоминает определение чисел Фибоначчи, их называ%
ют деревьями Фибоначчи (см. рис. 4.30). Определяются они так:
1. Пустое дерево есть дерево Фибоначчи высоты 0.
2. Дерево с одним узлом есть дерево Фибоначчи высоты 1.
3. Если
T
h–1
и
T
h–2
– деревья Фибоначчи высоты h–1
и h–2
соответственно, то
T
h
= h–1
, x, T
h–2
> – дерево Фибоначчи.
4. Других деревьев Фибоначчи нет.
Рис. 4.30. Деревья Фибоначчи высоты 2, 3 и 4
Число узлов в
T
h определяется следующим простым рекуррентным соотноше%
нием:
N
0
= 0, N
1
= 1
N
h
= N
h–1
+ 1 + N
h–2
N
h
– это число узлов, для которого может реализоваться наихудший случай
(верхний предел для h
); такие числа называются числами Леонардо.
4.5.1. Вставка в сбалансированное дерево
Теперь посмотрим, что происходит, когда в сбалансированное дерево вставляется новый узел. Если r
– корень с левым и правым поддеревьями
L
и
R
, то могут иметь место три случая. Пусть новый узел вставляется в
L
, увеличивая его высоту на 1:
1.
h
L
= h
R
: высота
L
и
R
становится неравной, но критерий сбалансирован%
ности не нарушается.
2.
h
L
< h
R
: высота
L
и
R
становится равной, то есть баланс только улучшается.
3.
h
L
> h
R
: критерий сбалансированности нарушается, и дерево нужно пере%
страивать.
Рассмотрим дерево на рис. 4.31. Узлы с ключами 9 или 11 можно вставить без перестройки: поддерево с корнем 10 станет асимметричным (случай 1), а у дерева с корнем 8 баланс улучшится (случай 2). Однако вставка узлов 1, 3, 5 или 7 потре%
бует перестройки для восстановления баланса.
Сбалансированные деревья

Динамические структуры данных
212
Пристально рассматривая ситуацию, обнаружи%
ваем, что есть только две существенно разные кон%
фигурации, требующие раздельного анализа. Ос%
тальные сводятся к этим двум по соображениям симметрии. Случай 1 соответствует вставке ключей
1 или 3 в дерево на рис. 4.31, случай 2 – вставке клю%
чей 5 или 7.
Эти два случая изображены в более общем виде на рис. 4.32, где прямоугольники обозначают подде%
ревья, а увеличение высоты за счет вставки указано крестиками. Желаемый баланс восстанавливается простыми преобразованиями. Их результат показан на рис. 4.33; заметим, что разрешены только перемещения по вертикали, а относи%
тельное горизонтальное положение показанных узлов и поддеревьев не должно меняться.
Рис. 4.31. Сбалансированное дерево
Рис. 4.32. Нарушение баланса в результате вставки
Рис. 4.33. Восстановление баланса

213
Алгоритм вставки и балансировки критически зависит от способа хранения информации о сбалансированности дерева. Одна крайность – вообще не хранить эту информацию в явном виде. Но тогда баланс узла должен быть заново вычислен каждый раз, когда он может измениться при вставке, что приводит к чрезмерным накладным расходам. Другая крайность – в явном виде хранить соответствующий баланс в каждом узле. Тогда определение типа
Node дополняется следующим об%
разом:
TYPE Node = POINTER TO RECORD
key, count, bal: INTEGER; (*bal = –1, 0, +1*)
left, right: Node
END
В дальнейшем балансом узла будем называть разность высоты его правого и левого поддеревьев и положим приведенное определение типа узла в основу по%
строения алгоритма. Процесс вставки узла состоит из трех последовательных шагов:
1) пройти по пути поиска, пока не выяснится, что данного ключа в дереве еще нет;
2) вставить новый узел и определить получающийся баланс;
3) вернуться по пути поиска и проверить баланс в каждом узле. Если нужно,
выполнять балансировку.
Хотя этот способ требует избыточных проверок (когда баланс установлен, его не нужно проверять для предков данного узла), мы будем сначала придерживаться этой очевидно корректной схемы, так как ее можно реализовать простым расшире%
нием уже построенной процедуры поиска и вставки. Эта процедура описывает нуж%
ную операцию поиска для каждого отдельного узла, и благодаря ее рекурсивной формулировке в нее легко добавить дополнительные действия, выполняемые при возвращении по пути поиска. На каждом шаге должна передаваться информация о том, увеличилась или нет высота поддерева, в котором сделана вставка. Поэтому мы расширим список параметров процедуры булевским параметром h
со значени%
ем

. Ясно, что это должен быть параметр%перемен%
ная, так как через него передается некий результат.
Теперь предположим, что процесс возвращается в некий узел p^
(А на рис. 4.32 –
прим. перев.) из левой ветви с указанием, что ее высота увеличилась. Тогда нужно различать три случая соотношения высот поддеревьев до вставки:
1)
h
L
< h
R
, p.bal = +1
; дисбаланс в p
исправляется вставкой;
2)
h
L
= h
R
, p.bal = 0
;
после вставки левое поддерево перевешивает;
3)
h
L
> h
R
, p.bal = –1
; нужна балансировка.
В третьем случае изучение баланса корня (B на рис. 4.32 – прим. перев.) левого поддерева (скажем, p1.bal
) покажет, какой из случаев 1 или 2 на рис. 4.32 имеет место. Если у того узла тоже левое поддерево выше, чем правое, то мы имеем дело со случаем 1, иначе со случаем 2. (Убедитесь, что в этом случае не может встре%
титься левое поддерево с нулевым балансом в корне.) Необходимые операции ба%
Сбалансированные деревья

Динамические структуры данных
214
лансировки полностью выражаются в виде нескольких присваиваний указателей.
На самом деле имеет место циклическая перестановка указателей, приводящая к одиночной или двойной «ротации» двух или трех участвующих узлов. Кроме ротации указателей, нужно обновить и показатели баланса соответствующих уз%
лов. Детали показаны в процедурах поиска, вставки и балансировки.
Рис. 4.34. Вставки в сбалансированное дерево
Работа алгоритма показана на рис. 4.34. Рассмотрим двоичное дерево (a), со%
стоящее только из двух узлов. Вставка ключа 7 дает сначала несбалансированное дерево (то есть линейный список). Его балансировка требует одиночной RR%рота%
ции, приводящей к идеально сбалансированному дереву (b). Дальнейшая вставка узлов 2 и 1 приводит к разбалансировке поддерева с корнем 4. Это поддерево ба%
лансируется одиночной LL%ротацией (d). Cледующая вставка ключа 3 тут же на%
рушает баланс в корневом узле 5. После чего баланс восстанавливается более сложной двойной LR%ротацией; результат – дерево (e). После следующей вставки баланс может нарушиться только в узле 5. В самом деле, вставка узла 6 должна приводить к четвертому случаю балансировки из описанных ниже, то есть двой%
ной RL%ротации. Окончательный вид дерева показан на рис. 4.34 (f).
PROCEDURE search (x: INTEGER; VAR p: Node; VAR h: BOOLEAN);
VAR p1, p2: Node;
(* ADruS45_AVL *)
BEGIN
(*h*)
IF p = NIL THEN (* *)
NEW(p); p.key := x; p.count := 1; p.left := NIL; p.right := NIL; p.bal := 0;
h := TRUE;
ELSIF p.key > x THEN
search(x, p.left, h);

215
IF h THEN (* *)
IF p.bal = 1 THEN p.bal := 0; h := FALSE
ELSIF p.bal = 0 THEN p.bal := –1
ELSE (*bal = –1, *) p1 := p.left;
IF p1.bal = –1 THEN (* LL– *)
p.left := p1.right; p1.right := p;
p.bal := 0; p := p1
ELSE (* LR– *) p2 := p1.right;
p1.right := p2.left; p2.left := p1;
p.left := p2.right; p2.right := p;
IF p2.bal = –1 THEN p.bal := 1 ELSE p.bal := 0 END;
IF p2.bal = +1 THEN p1.bal := –1 ELSE p1.bal := 0 END;
p := p2
END;
p.bal := 0; h := FALSE
END
END
ELSIF p.key < x THEN
search(x, p.right, h);
IF h THEN (* *)
IF p.bal = –1 THEN p.bal := 0; h := FALSE
ELSIF p.bal = 0 THEN p.bal := 1
ELSE (*bal = +1, *) p1 := p.right;
IF p1.bal = 1 THEN (* RR– *)
p.right := p1.left; p1.left := p;
p.bal := 0; p := p1
ELSE (* RL– *) p2 := p1.left;
p1.left := p2.right; p2.right := p1;
p.right := p2.left; p2.left := p;
IF p2.bal = +1 THEN p.bal := –1 ELSE p.bal := 0 END;
IF p2.bal = –1 THEN p1.bal := 1 ELSE p1.bal := 0 END;
p := p2
END;
p.bal := 0; h := FALSE
END
END
ELSE INC(p.count)
END
END search
Возникает два особенно интересных вопроса касательно производительности алгоритма вставки в сбалансированные деревья:
1. Если все n!
перестановок n
ключей встречаются с одинаковой вероятностью,
какова будет средняя высота получающегося сбалансированного дерева?
2. С какой вероятностью вставка приводит к необходимости балансировки?
Задача математического исследования этого сложного алгоритма остается нере%
шенной. Эмпирические тесты подтверждают предположение, что средняя высота сбалансированного дерева, построенного таким способом, равна h = log(n)+c
, где c
–
Сбалансированные деревья

Динамические структуры данных
216
небольшая константа (
c
≈
0.25
). Это означает, что на практике АВЛ%деревья так же хороши, как и идеально сбалансированные деревья, хотя работать с ними го%
раздо проще. Эмпирические данные также показывают, что в среднем одна балан%
сировка нужна примерно на каждые две вставки. Здесь одиночные и двойные ро%
тации равновероятны. Разумеется, пример на рис. 4.34 был тщательно подобран,
чтобы показать наибольшее число ротаций при минимуме вставок.
Сложность действий по балансировке говорит о том, что использовать сбалан%
сированные деревья следует только тогда, когда поиск информации производится значительно чаще, чем вставки. Тем более что с целью экономии памяти узлы таких деревьев поиска обычно реализуются как плотно упакованные записи. По%
этому скорость изменения показателей баланса, требующих только двух битов каждый, часто решающим образом влияет на эффективность балансировки. Эм%
пирические оценки показывают, что привлекательность сбалансированных дере%
вьев сильно падает, если записи должны быть плотно упакованы. Так что пре%
взойти простейший алгоритм вставки в дерево оказывается нелегко.

1   ...   14   15   16   17   18   19   20   21   22

4.5.2. Удаление из сбалансированного дерева
Наш опыт с удалением из деревьев подсказывает, что и в случае сбалансиро%
ванных деревьев удаление будет более сложной операцией, чем вставка. Это на самом деле так, хотя операция балансировки остается в сущности такой же, как и для вставки. В частности, здесь балансировка тоже состоит из одиночных или двойных ротаций узлов.
Процедура удаления из сбалансированного дерева строится на основе алго%
ритма удаления из обычного дерева. Простые случаи – концевые узлы и узлы с единственным потомком. Если удаляемый узел имеет два поддерева, мы снова будет заменять его самым правым узлом его левого поддерева. Как и в случае вставки, добавляется булевский параметр%переменная h
со значением

v
. Необходимость в балансировке может возникнуть,
только если h
истинно. Это случается при обнаружении и удалении узла, или если сама балансировка уменьшает высоту поддерева. Здесь мы введем две процедуры для (симметричных) операций балансировки, так как их нужно вызывать из более чем одной точки алгоритма удаления. Заметим, что процедуры balanceL
или balanceR вызываются после того, как уменьшилась высота левой или правой вет%
ви соответственно.
Работа процедуры проиллюстрирована на рис. 4.35. Если дано сбалансирован%
ное дерево (a), то последовательное удаление узлов с ключами 4, 8, 6, 5, 2, 1, и 7
приводит к деревьям (b)...(h). Удаление ключа 4 само по себе просто, так как соот%
ветствующий узел концевой. Но это приводит к несбалансированному узлу 3. Его балансировка требует одиночной LL%ротации. Балансировка опять нужна после удаления узла 6. На этот раз правое поддерево для корня (7) балансируется оди%
ночной RR%ротацией. Удаление узла 2, само по себе бесхитростное, так как узел имеет лишь одного потомка, требует применения сложной двойной RL%ротации.
Наконец, четвертый случай, двойная LR%ротация, вызывается после удаления

217
узла 7, который сначала замещается крайним правым элементом своего левого поддерева, то есть узлом 3.
PROCEDURE balanceL (VAR p: Node; VAR h: BOOLEAN);
(*ADruS45_AVL*)
VAR p1, p2: Node;
BEGIN
(*h; v *)
IF p.bal = –1 THEN p.bal := 0
Рис. 4.35. Удаления из сбалансированного дерева
Сбалансированные деревья

Динамические структуры данных
218
ELSIF p.bal = 0 THEN p.bal := 1; h := FALSE
ELSE (*bal = 1, *) p1 := p.right;
IF p1.bal >= 0 THEN (* RR– *)
p.right := p1.left; p1.left := p;
IF p1.bal = 0 THEN p.bal := 1; p1.bal := –1; h := FALSE
ELSE p.bal := 0; p1.bal := 0
END;
p := p1
ELSE (* RL– *)
p2 := p1.left;
p1.left := p2.right; p2.right := p1;
p.right := p2.left; p2.left := p;
IF p2.bal = +1 THEN p.bal := –1 ELSE p.bal := 0 END;
IF p2.bal = –1 THEN p1.bal := 1 ELSE p1.bal := 0 END;
p := p2; p2.bal := 0
END
END
END balanceL;
PROCEDURE balanceR (VAR p: Node; VAR h: BOOLEAN);
VAR p1, p2: Node;
BEGIN
(*h; v *)
IF p.bal = 1 THEN p.bal := 0
ELSIF p.bal = 0 THEN p.bal := –1; h := FALSE
ELSE (*bal = –1, rebalance*) p1 := p.left;
IF p1.bal <= 0 THEN (* LL– *)
p.left := p1.right; p1.right := p;
IF p1.bal = 0 THEN p.bal := –1; p1.bal := 1; h := FALSE
ELSE p.bal := 0; p1.bal := 0
END;
p := p1
ELSE (* LR– *)
p2 := p1.right;
p1.right := p2.left; p2.left := p1;
p.left := p2.right; p2.right := p;
IF p2.bal = –1 THEN p.bal := 1 ELSE p.bal := 0 END;
IF p2.bal = +1 THEN p1.bal := –1 ELSE p1.bal := 0 END;
p := p2; p2.bal := 0
END
END
END balanceR;
PROCEDURE delete (x: INTEGER; VAR p: Node; VAR h: BOOLEAN);
VAR q: Node;
PROCEDURE del (VAR r: Node; VAR h: BOOLEAN);
BEGIN

219
(*h*)
IF r.right # NIL THEN
del(r.right, h);
IF h THEN balanceR(r, h) END
ELSE
q.key := r.key; q.count := r.count;
q := r; r := r.left; h := TRUE
END
END del;
BEGIN
(*h*)
IF p = NIL THEN (* *)
ELSIF p.key > x THEN
delete(x, p.left, h);
IF h THEN balanceL(p, h) END
ELSIF p.key < x THEN
delete(x, p.right, h);
IF h THEN balanceR(p, h) END
ELSE (* p^*)
q := p;
IF q.right = NIL THEN p := q.left; h := TRUE
ELSIF q.left = NIL THEN p := q.right; h := TRUE
ELSE
del(q.left, h);
IF h THEN balanceL(p, h) END
END
END
END delete
К счастью, удаление элемента из сбалансированного дерева тоже может быть выполнено – в худшем случае – за
O(log n)
операций. Однако нельзя игнориро%
вать существенную разницу в поведении процедур вставки и удаления. В то время как вставка единственного ключа может потребовать самое большее одной рота%
ции (двух или трех узлов), удаление может потребовать ротации в каждом узле пути поиска. Например, рассмотрим удаление крайнего правого узла дерева Фи%
боначчи. В этом случае удаление любого одного узла приводит к уменьшению высоты дерева; кроме того, удаление крайнего правого узла требует максималь%
ного числа ротаций. Здесь имеет место весьма неудачная комбинация – наихуд%
ший выбор узла в наихудшей конфигурации сбалансированного дерева. А на%
сколько вероятны ротации в общем случае?
Удивительный результат эмпирических тестов состоит в том, что хотя одна ротация требуется примерно на каждые две вставки, лишь одна ротация потре%
буется на пять удалений. Поэтому в сбалансированных деревьях удаление элемента является столь же легкой (или столь же трудоемкой) операцией, как и вставка.
Сбалансированные деревья

Динамические структуры данных
220
4.6. Оптимальные деревья поиска
До сих пор наш анализ организации деревьев поиска опирался на предположение,
что частота обращений ко всем узлам одинакова, то есть что все ключи с равной вероятностью могут встретиться в качестве аргумента поиска. Вероятно, это луч%
шая гипотеза, если о распределении вероятностей обращений к ключам ничего не известно. Однако бывают случаи (хотя они, скорее, исключения, чем правило),
когда такая информация есть. Для подобных случаев характерно, что ключи все%
гда одни и те же, то есть структура дерева поиска не меняется, то есть не выпол%
няются ни вставки, ни удаления. Типичный пример – лексический анализатор
(сканер) компилятора, который для каждого слова (идентификатора) определя%
ет, является ли оно ключевым (зарезервированным) словом. В этом случае стати%
стическое исследование сотен компилируемых программ может дать точную ин%
формацию об относительных частотах появления таких слов и, следовательно,
обращений к ним в дереве поиска.
Предположим, что в дереве поиска вероятность обращения к ключу i
равна
Pr {x = k i
} = p i
, (S
S
S
S
Si: 1
≤ i ≤ n : p i
) = 1
Мы сейчас хотим организовать дерево поиска так, чтобы полное число шагов по%
иска – для достаточно большого числа попыток – было минимальным. Для этого изменим определение длины пути, (1) приписывая каждому узлу некоторый вес и
(2) считая, что корень находится на уровне 1 (а не 0), поскольку с ним связано первое сравнение на пути поиска. Узлы, к которым обращений много, становятся тяжелыми, а те, которые посещаются редко, – легкими. Тогда взвешенная длина
путей (внутренних) равна сумме всех путей из корня до каждого узла, взвешен%
ных с вероятностью обращения к этому узлу:
P = S
S
S
S
Si: 1
≤ i ≤ n : p i
* h i
h i
– уровень узла i
. Теперь наша цель – минимизировать взвешенную длину путей для заданного распределения вероятностей. Например, рассмотрим набор клю%
чей 1, 2, 3 с вероятностями обращения p1 = 1/7
, p2 = 2/7
и p3 = 4/7
. Из этих трех ключей дерево поиска можно составить пятью разными способами (см. рис. 4.36).
Из определения можно вычислить взвешенные длины путей деревьев (a)–(e):
P(a) = 11/7, P(b) = 12/7, P(c) = 12/7, P(d) = 15/7, P(e) = 17/7
Рис. 4.36. Деревья поиска с 3 узлами

221
Таким образом, в этом примере оптимальным оказывается не идеально сбалан%
сированное дерево (c), а вырожденное дерево (a).
Пример сканера компилятора сразу наводит на мысль, что задачу нужно не%
много обобщить: слова, встречающиеся в исходном тексте, не всегда являются ключевыми; на самом деле ключевые слова – скорее исключения. Обнаружение того факта, что некое слово k
не является ключом в дереве поиска, можно рассма%
тривать как обращение к так называемому дополнительному узлу, вставленному между ближайшими меньшим и большим ключами (см. рис. 4.19), для которого определена длина внешнего пути. Если вероятность q
i того, что аргумент поиска x
лежит между этими двумя ключами k
i и k
i+1
, тоже известна, то эта информация может существенно изменить структуру оптимального дерева поиска. Поэтому,
обобщая задачу, будем учитывать также и безуспешные попытки поиска. Теперь общая взвешенная длина путей равна
P = (S
S
S
S
Si: 1
≤ i ≤ n : p i
*h i
) + (S
S
S
S
Si: 1
≤ i ≤ m : q i
*h'
i
)
где
(S
S
S
S
Si: 1
≤ i ≤ n : p i
) + (S
S
S
S
Si: 1
≤ i ≤ m : q i
) = 1
и где h
i
– уровень (внутреннего) узла i
, а h'
j
– уровень внешнего узла j
. Тогда сред%
нюю взвешенную длину пути можно назвать ценой дерева поиска, поскольку она является мерой ожидаемых затрат на поиск. Дерево поиска с минимальной ценой среди всех деревьев с заданным набором ключей k
i и вероятностей p
i и q
i называ%
ется оптимальным деревом.
Чтобы найти оптимальное дерево, не нужно требовать, чтобы сумма всех чисел p
или q
равнялась 1. На самом деле эти вероятности обычно определяются из экс%
периментов, где подсчитывается число обращений к каждому узлу. В дальнейшем
Рис. 4.37. Дерево поиска с частотами обращений
Оптимальные деревья поиска

Динамические структуры данных
222
вместо вероятностей p
i и q
j мы будем использовать такие счетчики и обозначать их следующим образом:
a i
= сколько раз агрумент поиска x
был равен k
i b
j
= сколько раз агрумент поиска x
оказался между k
j и k
j+1
По определению, b
0
– число случаев, когда x
оказался меньше k
1
, а b
n
– когда x
был больше k
n
(см. рис. 4.37). В дальнейшем мы будем использовать
P
для обозна%
чения полной взвешенной длины путей вместо средней длины пути:
P = (S
S
S
S
Si: 1
≤ i ≤ n : a i
*h i
) + (S
S
S
S
Si: 1
≤ i ≤ m : b i
*h'
i
)
Таким образом, в дополнение к тому, что уже не нужно вычислять вероятности по измеренным частотам, получаем дополнительный бонус: при поиске оптималь%
ного дерева можно работать с целыми числами вместо дробных.
Учитывая, что число возможных конфигураций n
узлов растет экспоненци%
ально с n
, задача нахождения оптимума для больших n
кажется безнадежной. Од%
нако оптимальные деревья обладают одним важным свойством, которое помогает в их отыскании: все их поддеревья также оптимальны. Например, если дерево на рис. 4.37 оптимально, то поддерево с ключами k
3
и k
4
также оптимально. Это свойство подсказывает алгоритм, который систематически строит все большие деревья, начиная с отдельных узлов в качестве наименьших возможных подде%
ревьев. При этом дерево растет от листьев к корню, то есть, учитывая, что мы ри%
суем деревья вверх ногами, в направлении снизу вверх [4.6].
Уравнение, представляющее собой ключ к этому алгоритму, выводится так.
Пусть
P
будет взвешенной длиной путей некоторого дерева, и пусть
P
L
и
P
R
– соот%
ветствующие длины для левого и правого поддеревьев его корня. Ясно, что
P
рав%
на сумме
P
L
,
P
R
, а также количества проходов поиска по ребру, ведущему к корню,
что просто равно полному числу попыток поиска
W
. Будем называть
W
весом дере%
ва. Тогда его средняя длина путей равна
P/W
:
P = P
L
+ W + P
R
W = (S
S
S
S
Si: 1
≤ i ≤ n : a i
) + (S
S
S
S
Si: 1
≤ i ≤ m : b i
)
Эти соображения показывают, что нужно как%то обозначить веса и длины пу%
тей поддеревьев, состоящих из некоторого числа смежных ключей. Пусть
T
ij
–
оптимальное поддерево, состоящее из узлов с ключами k
i+1
, k
i+2
, ... , k
j
. Тогда пусть w
ij обозначает вес, а p
ij
– длину путей поддерева
T
ij
. Ясно, что
P = p
0,n и
W = w
0,n
Все эти величины определяются следующими рекуррентными соотношениями:
w ii
= b i
(0
≤ i ≤ n)
w ij
= w i,j–1
+ a j
+ b j
(0
≤ i < j ≤ n)
p ii
= w ii
(0
≤ i ≤ n)
p ij
= w ij
+ MIN k: i < k
≤ j : (p i,k–1
+ p kj
) (0
≤ i < j ≤ n)
Последнее уравнение прямо следует из определений величины
P
и оптималь%
ности. Так как имеется примерно n
2
/2
значений p
ij
, а операция минимизации в правой части требует выбора из
0 < j–i
≤
n значений, то полная минимизация потребует примерно n
3
/6
операций. Кнут указал способ сэкономить один фактор

223
n
(см. ниже), и только благодаря этой экономии данный алгоритм становится ин%
тересным для практических целей.
Пусть r
ij
– то значение величины k
, в котором достигается минимум p
ij
. Оказы%
вается, поиск r
ij можно ограничить гораздо меньшим интервалом, то есть умень%
шить число j–i шагов вычисления. Ключевым здесь является наблюдение, что если мы нашли корень r
ij оптимального поддерева
T
ij
, то ни расширение дерева добавлением какого%нибудь узла справа, ни уменьшение дерева удалением край%
него левого узла не могут сдвинуть оптимальный корень влево. Это выражается соотношением r
i,j–1
≤ r ij
≤ r i+1,j
,
которое ограничивает поиск решения для r
ij интервалом r
i,j–1
... r i+1,j
. Это приво%
дит к полному числу элементарных шагов порядка n
2
Мы готовы теперь построить алгоритм оптимизации в деталях. Вспомним следующие определения для оптимальных деревьев
T
ij
, состоящих из узлов с клю%
чами k
i+1
... k j
:
1.
a i
: частота поиска ключа k
i
2.
b j
: частота случаев, когда аргумент поиска x
оказывается между k
j и k
j+1 3.
w ij
: вес
T
ij
4.
p ij
: взвешенная длина путей поддерева
T
ij
5.
r ij
:
индекс корня поддерева
T
ij
Объявим следующие массивы:
a:
ARRAY n+1 OF INTEGER; (*a[0] *)
b:
ARRAY n+1 OF INTEGER;
p,w,r:
ARRAY n+1, n+1 OF INTEGER;
Предположим, что веса w
ij вычислены из a
и b
простейшим способом. Будем счи%
тать w
аргументом процедуры
OptTree
, которую нужно разработать, а r
– ее резуль%
татом, так как r
полностью описывает структуру де%
рева. Массив p
можно считать промежуточным результатом. Начиная с наименьших возможных деревьев, то есть вообще не имеющих узлов, мы пере%
ходим ко все большим деревьям. Обозначим ширину j–i поддерева
T
ij как h
. Тогда можно легко определить значения p
ii для всех деревьев с h = 0
в соответствии с определением величин p
ij
:
FOR i := 0 TO n DO p[i,i] := b[i] END
В случае h = 1
речь идет о деревьях с одним узлом,
который, очевидно, и является корнем (см.
рис. 4.38):
FOR i := 0 TO n–1 DO
j := i+1; p[i,j] := w[i,j] + p[i,i] + p[j,j]; r[i,j] := j
END
Рис. 4.38. Оптимальное дерево поиска с единственным узлом
Оптимальные деревья поиска

Динамические структуры данных
224
Заметим, что i
и j
обозначают левый и правый пределы значений индекса в рас%
сматриваемом дереве
T
ij
. Для случаев h > 1
используем цикл с h
от 2 до n
, причем случай h = n соответствует всему дереву
T
0,n
. В каждом случае минимальная дли%
на путей p
ij и соответствующий индекс корня r
ij определяются простым циклом,
в котором индекс k
пробегает интервал для r
ij
:
FOR h := 2 TO n DO
FOR i := 0 TO n–h DO
j := i+h;
k min = MIN k: i < k < j : (p i,k–1
+ p kj
), r i,j–1
< k < r i+1,j
;
p[i,j] := min + w[i,j]; r[i,j] := k
END
END
Детали того, как уточняется предложение, набранное курсивом, можно найти в программе, приводимой ниже. Теперь средняя длина пути дерева
T
0,n дается от%
ношением p
0,n
/w
0,n
, а его корнем является узел с индексом r
0,n
Опишем теперь структуру проектируемой программы. Ее двумя главными компонентами являются процедура для нахождения оптимального дерева поиска при заданном распределении весов w
, а также прцедура для печати дерева при заданных индексах r
. Сначала вводятся частоты a
и b
, а также ключи. Ключи на самом деле не нужны для вычисления структуры дерева; они просто используют%
ся при распечатке дерева. После печати статистики частот программа вычисляет длину путей идеально сбалансированного дерева, заодно определяя и корни его поддеревьев. Затем печатается средняя взвешенная длина пути и распечатывает%
ся само дерево.
В третьей части вызывается процедура
OptTree
, чтобы вычислить оптималь%
ное дерево поиска; затем это дерево распечатывается. Наконец, те же процедуры используются для вычисления и печати оптимального дерева с учетом частот только ключей, игнорируя частоты значений, не являющихся ключами. Все это можно суммировать так, как показано ниже, начиная с объявлений глобальных констант и переменных:
CONST N = 100; (* . *)
(* ADruS46_OptTree *)
WordLen = 16; (* . *)
VAR key: ARRAY N+1, WordLen OF CHAR;
a, b: ARRAY N+1 OF INTEGER;
p, w, r: ARRAY N+1, N+1 OF INTEGER;
PROCEDURE BalTree (i, j: INTEGER): INTEGER;
VAR k, res: INTEGER;
BEGIN
k := (i+j+1) DIV 2; r[i, j] := k;
IF i >= j THEN res := 0
ELSE res := BalTree(i, k–1) + BalTree(k, j) + w[i, j]
END;
RETURN res
END BalTree;

225
PROCEDURE ComputeOptTree (n: INTEGER);
VAR x, min, tmp: INTEGER;
i, j, k, h, m: INTEGER;
BEGIN
(* # : w, : p, r*)
FOR i := 0 TO n DO p[i, i] := 0 END;
FOR i := 0 TO n–1 DO
j := i+1; p[i, j] := w[i, j]; r[i, j] := j
END;
FOR h := 2 TO n DO
FOR i := 0 TO n–h DO
j := i+h; m := r[i, j–1]; min := p[i, m–1] + p[m, j];
FOR k := m+1 TO r[i+1, j] DO
tmp := p[i, k–1]; x := p[k, j] + tmp;
IF x < min THEN m := k; min := x END
END;
p[i, j] := min + w[i, j]; r[i, j] := m
END
END
END ComputeOptTree;
PROCEDURE WriteTree (i, j, level: INTEGER);
VAR k: INTEGER;
(* # ˆ W*)
BEGIN
IF i < j THEN
WriteTree(i, r[i, j]–1, level+1);
FOR k := 1 TO level DO Texts.Write(W, TAB) END;
Texts.WriteString(W, key[r[i, j]]); Texts.WriteLn(W);
WriteTree(r[i, j], j, level+1)
END
END WriteTree;
PROCEDURE Find (VAR S: Texts.Scanner);
VAR i, j, n: INTEGER;
(* # ˆ W*)
BEGIN
Texts.Scan(S); b[0] := SHORT(S.i);
n := 0; Texts.Scan(S); (*: a, , b*)
WHILE S.class = Texts.Int DO
INC(n); a[n] := SHORT(S.i); Texts.Scan(S); COPY(S.s, key[n]);
Texts.Scan(S); b[n] := SHORT(S.i); Texts.Scan(S)
END;
(* w a b*)
FOR i := 0 TO n DO
w[i, i] := b[i];
FOR j := i+1 TO n DO
w[i, j] := w[i, j–1] + a[j] + b[j]
END
END;
Оптимальные деревья поиска

Динамические структуры данных
226
Texts.WriteString(W, " = ");
Texts.WriteInt(W, w[0, n], 6); Texts.WriteLn(W);
Texts.WriteString(W, "‘ # = ");
Texts.WriteInt(W, BalTree(0, n), 6); Texts.WriteLn(W);
WriteTree(0, n, 0); Texts.WriteLn(W);
ComputeOptTree(n);
Texts.WriteString(W, "‘ # = ");
Texts.WriteInt(W, p[0, n], 6); Texts.WriteLn(W);
WriteTree(0, n, 0); Texts.WriteLn(W);
FOR i := 0 TO n DO
w[i, i] := 0;
FOR j := i+1 TO n DO w[i, j] := w[i, j–1] + a[j] END
END;
ComputeOptTree(n);
Texts.WriteString(W, " b"); Texts.WriteLn(W);
WriteTree(0, n, 0); Texts.WriteLn(W)
END Find;
В качестве примера рассмотрим следующие входные данные для дерева с тре%
мя ключами:
20 1 Albert 10 2 Ernst 1 5 Peter 1
b
0
= 20
a
1
= 1
key
1
= Albert b
1
= 10
a
2
= 2
key
2
= Ernst b
2
= 1
a
3
= 4
key
3
= Peter b
3
= 1
Результаты работы процедуры
Find показаны на рис. 4.39; видно, что структу%
ры, полученные в трех случаях, могут сильно отличаться. Полный вес равен 40,
длина путей сбалансированного дерева равна 78, а для оптимального дерева – 66.
Рис. 4.39. Три дерева, построенные процедурой
ComputeOptTree
Из этого алгоритма очевидно, что затраты на определение оптимальной струк%
туры имеют порядок n
2
; к тому же и объем требуемой памяти имеет порядок n
2
Это неприемлемо для очень больших n
. Поэтому весьма желательно найти более эффективные алгоритмы. Один из них был разработан Ху и Такером [4.5]; их алго%
ритм требует памяти порядка
O(n)
и вычислительных затрат порядка
O(n*log(n))
Однако в нем рассматривается только случай, когда частоты ключей равны нулю,
то есть учитываются только безуспешные попытки поиска ключей. Другой алго%

227
ритм, также требующий
O(n)
элементов памяти и
O(n*log(n))
вычислительных операций, описан Уокером и Готлибом [4.7]. Вместо поиска оптимума этот алго%
ритм пытается найти почти оптимальное дерево. Поэтому его можно построить на использовании эвристик. Основная идея такова.
Представим себе, что узлы (реальные и дополнительные) распределены на ли%
нейной шкале и что каждому узлу приписан вес, равный соответствующей часто%
те (или вероятности) обращений. Затем найдем узел, ближайший к их центру тя%
жести. Этот узел называется центроидом, а его индекс равен величине
(S
S
S
S
Si: 1
≤ i ≤ n : i*a i
) + (S
S
S
S
Si: 1
≤ i ≤ m : i*b i
) / W
,
округленной до ближайшего целого. Если вес всех узлов одинаков, то корень ис%
комого оптимального дерева, очевидно, совпадает с центроидом. В противном случае – рассуждают авторы алгоритма – он будет в большинстве случаев на%
ходиться вблизи центроида. Тогда выполняется ограниченный поиск для на%
хождения локального оптимума, после чего та же процедура применяется к двум получающимся поддеревьям. Вероятность того, что корень лежит очень близко к центроиду, растет вместе с объемом дерева n
. Как только поддеревья становятся достаточно малыми, оптимум для них может быть найден посредством точного алгоритма, приведенного выше.

1   ...   14   15   16   17   18   19   20   21   22