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 был тщательно подобран,
чтобы показать наибольшее число ротаций при минимуме вставок.
Сложность действий по балансировке говорит о том, что использовать сбалан%
сированные деревья следует только тогда, когда поиск
информации производится значительно чаще, чем вставки. Тем более что с целью экономии памяти узлы таких деревьев поиска обычно реализуются как плотно упакованные записи. По%
этому скорость изменения показателей баланса, требующих только двух битов каждый, часто решающим образом влияет на эффективность балансировки. Эм%
пирические оценки показывают, что привлекательность сбалансированных дере%
вьев сильно падает, если записи должны быть плотно упакованы. Так что пре%
взойти простейший алгоритм вставки в дерево оказывается нелегко.
Скачать 2.67 Mb.