4.4.7. Включение в сбалансированное дерево

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

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

включается новый узел, вызывая увеличение его высоты на 1. Возможны три случая:

1. hi = Hr: L vl R становятся неравной высоты, но критерий сбалансированности не нарушается.

2. Hl < hR-. L к R приобретают равную высоту т. е. сбалансированность даже улучшается.

3. hL > h: критерий сбалансированности нарушается, и Д^ рево нужно перестраивать.

Рассмотрим дерево на рис. 4.31. Узлы с ключами 9 й 1* можно вставить без балансировки; дерево с корнем Ю становится односторонним (случай 1), а с корнем 8 улучш^е' вою сбалансированность (случай 2). Однако включение У^ лов 1, 3, 5 или 7 требует последующей балансировки.

При внимательном изучении этой ситуации можно обнарГ жить, что имеются лишь две существенно различные возмо^

2. Один узел есть дерево Фибоначчи с высотой 1.

3. Если Th-i и Гь-г - деревья Фибоначчи с высотой /i, и Л -2, то Th<Jh-u X, Th-i> есть дерево Фибона] с высотой h.

4. Никакие другие деревья не являются деревьями Фид^ наччи.

Число узлов в Тн определяется простым рекуррентныц соотношением:

Ni - это количества узлов, для которых можно получить нац. худший случай (верхнюю границу h) из (4.60).

стй, требующие индивидуального подхода. Оставщиеся мо-быть получены симметричными преобразованиями этих lyx. Случай 1 определяется включением ключа 1 или 3 дерево на рис. 4.31, случай 2 - включением узла 5 или 7.

т

Рис. 4.32. Несбалансированность, возникающая при включении.

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

Случай 1

Случай 2

Рис. 4.33. Восстановление баланса.

У^ную сбалансированность. Их результат приведен на PJC- 4.33; отметим, что допускаются перемещения лишь в вер- кальном направлении, в то время как относительное гори-*Итальное расположение показанных узлов и поддеревьев Лжно оставаться без изменений.

Алгоритм включения и балансировки полностью определится способом хранения информации о сбалансированносги ва. Крайнее решение состоит в хранении этой информа-

В дальнейшем мы будем интерпретировать показатель сбалансированности узла как высоту его правого поддерева минус высота его левого поддерева и будем строить алгоритм, исходя из узлов описанного в (4.62) типа.

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

1. Следовать по пути поиска, пока не окажется, что ключа нет в дереве.

2. Включить новый узел и определить новый показатель сбалансированности.

3. Пройти обратно по пути поиска и проверить показатель сбалансированности у каждого узла.

Хотя этот метод требует некоторой избыточной проверки (если сбалансированность установлена, то для предков соответствующего узла ее проверять уже не надо), мы будем вначале придерживаться этой, очевидно, корректной схемы, так как ее можно реализовать с помощью простого расширения уже разработанной процедуры поиска с включением из программы 4.4. Эта процедура описывает операцию поиска для каждого отдельного узла, и благодаря рекурсивной формулировке ее можно дополнить операцией, выполняемой О дороге назад вдоль пути поиска . На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому мы fifl бавим к списку параметров процедуры булевскую переменную Л, означающую высот поддерева увеличилась . Очевидно, что ft должна быть параметром-переменной, поскольку используется для передачи результата.

Теперь предположим, что алгоритм возвращается к узлУ с левой ветви (см. рис. 4.32) с указанием, что ее высота ув

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

type node = record Агед : integer;

count: integer;

left,rlght: ref; (4.62)

bah -1,. +1