AOP_Tom3 (1021738), страница 130
Текст из файла (страница 130)
Сб. (Корректировка факторов сбалансированности.] Установить И <- О. (Это действие позволяет восстановить предыдущее значение И, когда Р было равно Я: все поля НАМК установлены соответствующим образом.) Если И < НАМК(Я), присвоить Н е- Р < — ЕЫМК(Б) и а < — — 1; в противном случае присвоить Н +- Р +- 81.1МК(Б), а < — +1 и И < — М вЂ” НАМК(Б). Затем повторять следующие действия, пока Р не станет равным Ц: если И ( НАМК(Р), установить В(Р) +- — 1 и Р с — (.ЫМК(Р); если И > НАМК(Р), установить В(Р) ь- +1, И ,'— И вЂ” НАМК(Р) и Р < — НЫМК(Р).
(Если И = НАМК(Р), то Р = Ц и можно переходить к следующему шагу ) СТ. ]Балансировка.] Здесь возможны несколько случаев. !) Если В(Я) = О, установить В(Я) с — а, (.ЫМК(НЕАО) + — (,ЫМК(НЕАО) + 1 и прекратить выполнение алгоритма. Н) Если В(Я) = -а, установить В(Я) +- О и прекратить выполнение алгоритма. ш) Если В(Б) = а, то перейти к шагу С8 в случае, если В(К) = а, и к шагу С9, если В(Н) = — а.
С8. ]Однократный поворот] Установить Р = Н, 51МК(а,Б) +- 51МК(-а,й), ЫМК(-а, К) +- Б, В(Я) е- В(Н) < — О. Если а = +1, установить НАМК(Н) < — НАМИ(Н) + НАМК(Я); если а = — 1, установить НАМК(Б) < — НАМК(Я) — НАМК(Н). Перейти к шагу С10. С9. (Двукратный поворот.] Выполнить шаг А9 (алгоритм А). Затем, если а = +1, установить НАМК(Н) с — НАМК(Н) — НАМК(Р), НАМК(Р) ь- НАМК(Р) + НАМК(Б); если а = — 1, присвоить НАМК(Р) < — НАМК(Р)+МАКК(Н), а затем НАМК(Б) е- НАМК(Я)— НАМК (Р) . С10. ]Последний штрих.] Если Я = КЕ1МК(Т), присвоить НЕ1МК(Т) е- Р, в противном случае — 1.1.1МК (Т) < — Р.
1 Удаление, конкатенации и другие операции. Существует множество других операций над сбаланси!к~ванными деревьями, которые поддерживают их сбалансированность, однако их алгоритмы слишком длинны для детального рассмотрения в этой книге. Здесь обсуждаются только общие идеи, и заинтересованному читателю предоставляется возможность самостоятельно восстановить опущенные детали (что ие так трудно, как кажется на первый взгляд).
Удаление при корректной постановке выполняется за 0(!оК Ж) шагов (С. С. Гоэсег, "Л 8(пс)у о( АУЧЕ Тгеев", Соог(уеаг Аегозрасе Согр. серег( СЕР;12158 (Арп(, 1955)]. Прежде всего, удаление произвольного узла сводится к простому удалению узла Р, поля ВЫМК(Р) или НЕ1МК(Р) которого равны Л, как в алгоритме 6.2.2П. Алгоритм к тому же должен быть изменен таким образом, чтобы он строил список указателей, определяющих путь к узлу Р: (16) где Ро — — НЕАО, ао = +1; 1.1МК(а„Р;) = Рч м О < ! < 1; Р~ = Р и 1.1МК(аыР~) = Л.
Этот список при поиске вниз по дереву может быть помещен во вспомогательный стек. В процессе удаления узла Р устанавливается (.1МК(а~,, Р~, ) е- 01МК( — аыР~) и следует откорректировать фактор сбалансированности узла Р~ ~. Предположим, что мы должны откорректировать фактор сбалансированности узла Ры потому что уменьшилась высота поддерева аь данного узла. Для этого используетгя следующая процедура: если А = О, установить Е(.1МК(НЕА0) +- 1.1.1МК(НЕА0) — 1 и прекратить выполнение алгоритма, поскольку уменьшилась высота всего дерева. В противном случае рассмотрим фактор сбалансированности В(РА). Возможны три варианта, приведенных ниже.
!) В(РА) = аь. Установить В(РА) +- О, уменьшить А на 1 и повторить процедуру корректировки для нового значения lс. Н) В(Рь) = О. Установить В(Рь) е- — аь н прекратить выполнение алгоритма. 'ш) В(РА) = †Требуется балансировка! Ситуации, в которых требуется ребалансировка дерева, практически те же, что в алгоритме вставки; вернитесь к (1), где в роли А выступает узел Ргм а в роли  — узел 1.1МК(-аь,РА), принадлежащий ветви, противоположной той, в которой производится удаление. Отличие заключается в том, что узел В может быть сбалансированным. Это приводит к возникновению нового случая 3, который подобен случаю 1, но высота Д равна А + 1. В случаях 1 и 2 ребалансировка, как и в (2), означает, что мы уменыпаем высогу, устанавливая 1.1МК(аь юРь-~) в качестве корня (2), уменьшаем А на 1 и перезапускаем процедуру корректировки для нового значения )с.
В случае 3 выполняется однократный поворот, который оставляет факторы сбалансированности А и В ненулевыми без изменения общей высоты. После занесения в Е1МК(аь,, Рь,) адреса узла В алгоритм завершается. Важное отличие между удалением и вставкой заключается в том, что для удаления может потребоваться до !оКЮ поворотов, в то время как для вставки никогда не требуется больше одного. Причина этого становится ясна, если попытаться удалить крайний справа узел дерева Фибоначчи (см.
рис. 8 в разделе 6.2.1). Однако эмпирические тесты показывают, что в среднем на одно удаление приходится около 0.21 вращений. При использовании сбалансированных деревьев для представления линейных списков необходим алгоритм конкатенации (глияния); при этом некоторое дерево Тз целиком вставляется справа от дерева 1ч без нарушения сбалансированности. Элегантный алгоритм конкатенации впервые был разработан Кларком А. Крейном (С!аг!с А. Сгапе).
Предположим, что высота(1~) > высота(1з) (другой случай обрабатывается аналогично). Узалим из бт первый узел, назвав его сшмкоеочнмм узлом 1. Через Е~ обозначим получившееся дерево Х,з '! (,У). После этого спустимся по правым деревьям Ь|, пока не достигнем узла Р, такого, что высота(Р) — высота(Ц) = 0 нли 1. Это всегда возможно, поскольку при переходе вниз на один уровень высота изменяется на 1 или 2.
Теперь заменим (Р~ на ф а и продолжим корректировку Е~, как если бы новый узел 1 был только что вставлен при помощи алгоритма А. Рис. 25. Задача разделения списка. Крейн также решил более сложную обратную задачу — разделить список на две части, которые дадут исходное дерево при конкатенации. Рассмотрим, например, задачу разделения списка, показанного на рнс.
20, для получения двух списков, в одном из которых содержится (А,..., 1), а в другом — (Л,..., Ц). При етом требуется существенная перекомпоновка деревьев. В общем случае, когда необходимо разделить дерево в некотором заданном узле Р, путь к Р будет похож на путь, изображенный на рис. 25. Нужно построить левое дерево, содержащее узлы ам Р„о4, Р4, ав, Рг, о7, Рт, а, Р в симметричном порядке, и правое дерево, которое содержит д,Ре,де,Рюдв, Рз,дз,Рз,дз. Это можно сделать с помощью последовательности конкатенаций: сначала вставить Р справа от а, затем соединить Д с Дв с использованием Ре в качестве стыковочного узла, соединить ат с аР (стыковочный узел — Рт), ав с атРтоР (стыковочный узел — Ра), дРврв с Д (стыковочный узел — Рз) и т.
д. Узлы Рв,Р7, °,Р~ на пути к Р используются в качестве стыковочных, Крейн доказал, что для такого алгоритма разделения требуется О(!оп Ж) единиц времени для исходного дерева с Х узлами, так как конкатенация с использованием данного стыковочного узла выполняется за 0(й) шагов, где )с— разность высот конкатенируемых деревьев, а значения Ь образукэт геометрическую прогрессию. Все эти алгоритмы могут использоваться как с полями КЕУ, так и с полями ЕАИК (или с обоими), хотя в случае конкатенации с помощью ключей все ключи дерева Ьз должны быть больше ключей дерева Ь,.
Для общих целей часто предпочтительнее использовать деревья с шремл связями, в которых наряду с полями ЬЬ1МК и ЕЬ1МК применяется поле ОР, которое указывает на родительский узел, и однобитавое поле, указывающее, каким потомком является данный узел: левым или правым. Такие деревья упрощают используемые алгоритмы и позволяют определить узел без явного указания пути к мему.
Можно написать подпрограмму для удаления узла ИОРЕ(Р) по заданному Р, удаления узла, следующего за МОРЕ(Р) в симметричном порядке, для нахождения списка, содержащего ИООЕ(Р), и т. д. В алгоритме удаления для деревьев с тремя связями не нужно строить список (16), так как ссылки ОР предоставляют всю необходимую информацию. Конечно, при вставке, удалении или повороте в таких деревьях требуется немного больше усилий для изменения ссылок. Использование "трехсвязных" деревьев вместо двухсвязных аналогично использовамию двойных связей вместо одинарных: можно начать работу с любого места и двигаться как вперед, так и назад.
Полное описание алгоритмов, основанных на трехсвязных деревьях, приводится в диссертации Крейна (51апГогс$ Пп!гегз!Гуз 1972). левый вес у/2 — 1 с правый вес (17) где левый н правый веса означают количество внешних узлов в левом и правом поддеревьях соответственно. Можно показать, что при вставке взвешенную сбалансированность можно поддерживать с помощью однократных и двукратных поворотов, как в алгоритме А (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
