присвоить Т Р, S R и и М. И, наконец, присвоить Р R и вернуться к шагу С2.

С4. [Перемещение вправо.] Установить М М - RANK(P) и R RLINK (Р). Если R = Л, присвоить RLINK (Р) Q и перейти к шагу С5. В противном случае, если B(R) ф О, присвоить Т Р, S 4- R и U М. И, наконец, присвоить Р R и вернуться к шагу С2.

С5. [Вставка.] Установить RANK(Q) 1, LLINK(Q) RLINK(Q) *r- Л, B(Q) *r- 0.

C6. [Корректировка факторов сбалансированности.] Установить М U. (Это действие позволяет восстановить предыдущее значение М, когда Р было равно S; все поля RANK установлены соответствующим образом.) Если М < RANK(S), присвоить R 4- Р LLINK(S) и а -1; в противном случае присвоить R Р RLINK(S), -hlnMf-M - RANK(S). Затем повторять следующие

действия, пока Р не станет равным Q: если М < RANK(P), установить В (Р) <--1

и Р LLINK (Р); если М > RANK(P), установить В(Р) +1, М М - RANK(P) и Р *г- RLINK (Р). (Если М = RANK(P), то Р = Q и можно переходить к следующему шагу.)

С7. [Балансировка.] Здесь возможны несколько случаев.

i) Если B(S) = О, установить B(S) а, LLINK(HEAD) LLINK(HEAD) + 1 и прекратить вьшолнение алгоритма.

ii) Если B(S) = -а, установить B(S) О и прекратить вьшолнение алгоритма.

iii) Если B(S) = а, то перейти к шагу С8 в случае, если B(R) = а, и к шагу С9, если B(R) = -а.

С8. [Однократный поворот.] УстановитьР = R, LINK(a,S) LINK(-a,R), LINK(-a, R) S, B(S) B(R) 0. Если a = +1, установить RANK(R) RANK(R) + RANK(S); если a = -1, установить RANK(S) RANK(S) - RANK(R). Перейти к шагу СЮ.

С9. [Двукратный поворот.] Выполнить шаг А9 (алгоритм А). Затем, если а = +1, установить RANK(R) <- RANK(R) -RANK(P), RANK(P) RANK(P) + RANK(S); если a = -1, присвоить RANK(P) RANK(P)+RANK(R), a затем RANK(S) RANK(S)-RANK(P).

CIO. [Последний штрих.] Если S = RLINK(Т), присвоить RLINK (Т) P, в противном случае - LLINK (Т)

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

Удаление при корректной постановке выполняется за 0{\ogN) шагов [С. С. Foster, "А Study of AVL Trees", Goodyear Aerospace Corp. report GER-12158 (April, 1965)]. Прежде всего, удаление произвольного узла сводится к простому удалению узла Р, поля LLINK (Р) или RLINK (Р) которого равны Л, как в алгоритме 6.2.2D.

Алгоритм к тому же должен быть изменен таким образом, чтобы он строил список указателей, определяюпдих путь к узлу Р:

(Ро,ао), (Pi,ai), (Р,,а,), (16)

где Ро = HEAD, oq = +1; LINKCa.P) = P+i, О < г < i; P, = P и LINK(a;,P;) = A. Этот список при поиске вниз по дереву может быть помещен во вспомогательный стек. В процессе удаления узла? устанавливается LINK (а; 1 ,P; i) +- LINK(-а;,Р;) и следует откорректировать фактор сбалансированности узла P;-i. Предположим, что мы должны откорректировать фактор сбалансированности узла Рк, потому что уменьшилась высота поддерева ак данного узла. Для этого используется следующая процедура: если А; = О, установить LLINK (HEAD) +- LLINK (HEAD) - 1 и прекратить выполнение алгоритма, поскольку уменьшилась высота всего дерева. В противном случае рассмотрим фактор сбалансированности В(Рл). Возможны три варианта, приведенных ниже.

i) В{Рк) = йк- Установить Ъ{Рк) +- О, уменьшить fc на 1 и повторить процедуру корректировки для нового значения к.

И) B(Pt) = 0. Установить B(Pjfc) <--а* и прекратить выполнение алгоритма.

iii) B(Pt) = -йк. Требуется балансировка!

Ситуации, в которых требуется ребалансировка дерева, практически те же, что в алгоритме вставки; вернитесь к (1), где в роли А выступает узел Р*, а в роли В - узел LINKC-Ofc.Pt), принадлежащий ветви, противоположной той, в которой производится удаление. Отличие заключается в том, что узел В может быть сбалансированным. Это приводит к возникновению нового случая 3, который подобен случаю 1, но высота равна h + 1. В случаях 1 и 2 ребалансировка, как и в (2), означает, что мы уменьшаем высоту, устанавливая LINK(aife-i ,Pfc i) в качестве корня (2), уменьшаем fc на 1 и перезапускаем процедуру корректировки для нового значения fc. В случае 3 выполняется однократный поворот, который оставляет факторы сбалансированности А к В ненулевыми без изменения общей высоты. После занесения в LINK(at i ,Pjfc i) адреса узла В алгоритм завершается.

Важное отличие между удалением и вставкой заключается в том, что для удаления может потребоваться до log N поворотов, в то время как для вставки никогда не требуется больше одного. Причина этого становится ясна, если попытаться удалить крайний справа узел дерева Фибоначчи (см. рис. 8 в разделе 6.2.1). Однако эмпирические тесты показывают, что в среднем на одно удаление приходится около 0.21 вращений.

При использовании сбалансированных деревьев для представления линейных списков необходим алгоритм конкатенации (слияния); при этом некоторое дерево L2 целиком вставляется справа от дерева Li без нарушения сбалансированности. Элегантный алгоритм конкатенации впервые был разработан Кларком А. Крейном (Clark А. Crane). Предположим, что BbicoTa(Li) > высота(2) (другой случай обрабатьшается аналогично). Удалим из L2 первый узел, назвав его стыковочным узлом J. Через L2 обозначим получившееся дерево L2\{J}- После этого спустимся по правым деревьям Li, пока не достигнем узла Р, такого, что

высота(Р) - высота(Х2) = О или 1.

Это всегда возможно, поскольку при переходе вниз на один уровень высота изменяется на 1 или 2. Теперь заменим {Р) на

и продолжим корректировку Li, как если бы новый узел J был только что вставлен при помощи алгоритма А.

Рис. 25. Задача разделения списка.

Крейн также решил более сложную обратную задачу - разделить список на две части, которые дадут исходное дерево при конкатенации. Рассмотрим, например, задачу разделения списка, показанного на рис. 20, для получения двух списков, в одном из которых содержится {А,..., I}, а в другом - {J, • • •, О}- При этом требуется существенная перекомпоновка деревьев. В общем случае, когда необходимо разделить дерево в некотором заданном узле Р, путь к Р будет похож на путь, изображенный на рис. 25. Нужно построить левое дерево, содержащее узлы ai,Pi,ai,Pi,a6,P6,ar,p7,a,P в симметричном порядке, и правое дерево, которое содержит Р,Ра,08,Рь,Рь, Рз,Рз,Р2,2- Это можно сделать с помощью последовательности конкатенации: сначала вставить Р справа от а, затем соединить Р с Ps с использованием Pg в качестве стыковочного узла, соединить с аР (стыковочный узел - Рт), Об с a-jP-jaP (стыковочный узел - Ре), pPsPs с Рь (стыковочный узел - Рь) и т. д. Узлы P8,P7,...,Pi на пути к Р используются в качестве стыковочных. Крейн доказал, что для такого алгоритма разделения требуется O(logiV) единиц времени для исходного дерева с N узлами, так как конкатенация с использованием данного стыковочного узла вьшолняется за 0{к) шагов, где к -