Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 29
Текст из файла (страница 29)
После занесения в 1.1МК(аь ю Рэ г ) адреса узла В алгоритм завершается. Важное отличие между удалением и вставкой заключается в том, что для удаления может потребоваться до 1оЕХ поворотов, в то время как для вставки никогда не требуется больше одного. Причина этого становится ясна, если попытаться удалить крайний справа узел дерева Фибоначчи (см. рис. В в разделе 6.2.1). Однако эмпирические тесты показывают, что в среднем на одно удаление приходится около 0.21 вращений.
При использовании сбалансированных деревьев для представления линейных списков необходим алгоритм коикатеиацип (слияния); при этом некоторое дерево Хз целиком вставляется справа от дерева Х,| без нарушения сбалансированности. Элегантный алгоритм конкатенации впервые был разработан Кларком А. Крейном (С1вг)с А. Сгапе). Предположим, что высота(Х~) > высота(Х,з) (другой случай обрабатывается аналогично). Удалим из Х,э первый узел, назвав его сгпмкоеочнэсм узлом Х.
Через Х ~ обозначим получившееся дерево Хэ ~ (,Х). После этого спустимся по правым деревьям Еы пока не достигнем узла Р, такою, что вьюота(Р) — высота(Ц) = 0 или 1. Это всегда возможно, поскольку при переходе вниз на один уровень высота изменяется на 1 или 2. Теперь заменим (Р~ на и продолжим корректировку Ам как если бы новый узел У был только что вставлен при помощи алгоритма А. Рис.
26. Задача разделения списка. Крейн также решил более сложную обратную задачу — разделить список на две части, которые дадут исходное дерево при конкатенации. Рассмотрим, нв пример, задачу разделения списка, показанного на рис. 20, для получения двух списков, в одном из которых содержится (л,...,1), а в другом — (Л,..., Я), При этом требуется существенная перекомпоновка деревьев.
В общем случае, когда необходимо разделить дерево в некотором заданном узле Р, путь к Р будет похож на путь, изображенный на рис. 25. Нужно построить левое дерево, содержащее узлы Оы Р„ах, Р„аш Рюсс, Рт, а, Р в симметричном порядке, н правое дерево, которое сОдержит ф~ Ре, Фе~ Рв, А, Р3,~93, РЯ, дз. Это мОжнО сделать с пОмОщью последовательности конкатенаций: сначала вставить Р справа от а, затем соединить Д с дэ с использованием Ре в качестве стыковочного узла„соединить ат с ОР (стыковочный узел — Рт), ае с отРгоР (стыковочный узел — Ре),;9РеД~ с Д (стыковочный узел — Рэ) и т.
д. Узлы Ре,гт,...,Р1 на пути к Р используются в качестве стыковочных. Крейн доказал, что для такого алгоритма разделения требуется О(1оя Х) единиц времени для исходного дерева с Ф узлами, так как конкатенация с использованием данного стыковочного узла выполняется за 0(й) шагов, где ив разность высот коикатепируемых деревьев, а значения й образуют геометрическую прогрессию. Все зти алгоритмы могут использоваться как с полями КЕУ, так и с полями МАЕК (или с обоими), хотя в случае конкатенации с помощью ключей все ключи дерева Ев должны быть больше ключей дерева Ем Для общих целей часто предпочтительнее использовать деревья с гарема свлзямп, в которых наряду с полями Ы.|МК н 1Ч.ХМК применяется поле ОР, которое указывает на родительский узел, и однобитовое поле, указывающее, каким потомком является данный узел: левым или правым. Такие деревья упрощают используемые алгоритмы и позволяют определить узел без явного указания пути к нему.
Можно написать подпрограмму для удаления узла МООЕ(Р) по заданному Р, удаления узла, следующего за МООЕ(Р) в симметричном порядке. для нахождения списка, содерлсащего МОВЕ(Р), н т. д. В алгоритме удаления для деревьев с тремя связями не нужно строить список (16), так как ссылки ОР предоставляют всю необходимую информацию. Конечно, при вставке, удалении или повороте в таких деревьях требуется немного больше усилий для изменения ссылок. Использование ьтрехсвязиых" деревьев вместо двухсвязных аналогично использованию двойных связей вместо одинарных: можно начать работу с любого места и двигаться как вперед, так и назад. Полное описание алгоритмов, основанных на трехсвязных деревьях, приводится в диссертации Крейна (Ягап(ого Пп!тегв)су, 1972).
левый вес правый вес (17) где левый и правый веса означают количество внешния узлов в левом и правом поддеревьях соответственно. Можно показать, что при вставке взвешенную сбалансированность можно поддерживать с помощью однократных и двукратных поворотов, как в алгоритме А (см. упр. 25). Однако при вставке могут оказаться необходимыми несколько ребалансировок дерева. При ослаблении условия (17) количество нужных ребалансировок уменьшается (правда, за счет увеличения времени поиска). На первый взгляд может показаться, что для взвешенно-сбалансированных деревьев необходимо больше памяти, однако иногда ее нужно даже меньше, чем для обычных сбалансированных деревьев! Если в каждом узле уже имеется поле ЕАМК для представления линейного списка, то зто и есть вес левого поддерева, а соответствующие правые веса могут быть определены при движении вниз по дереву.
Альтернативы Ат'1-деревьям. Помимо использования А1'1;деревьев, было предложено несколько других подходов к организации деревьев, гарантирующих логарифмическое время доступа. Например, К. К. Фостер (С, С. Гое!ег) «САСЛХ 16 (1973), 513-517] рассмотрел бинарные деревья, которые получаются, если ограничить разность высот поддеревьев некоторой величиной Й.
Такие структуры называются НВ(А) (что означает "Ье!ЕЪ1-Ъа)апсебь — "сбалансированные по высоте'). В этих терминах рассмотренные сбалансированные деревья представляют собой частный случай НВ(1). Интересная концепция езеешенно-сбалансированнъх деревьев (юе(РАЕЫапсед !теез) была изучена Ю. Ннвергельтом (Л. %етегйе!с), Э. Рейнгольдом (Е. НешЕоЫ) и Ч, К. Вонгом (С. К. %опЕ). Они не рассматривали высоту деревьев, а поставили условие, которому должны удовлетворять подцеревья всех узлов: Однако требуемые для сохранения взвешенной сбалансированности накладные расходы отнимают больше времени, чем алгоритм А, и сохранение двух битов иа узле ие представляется достаточной компенсацией перерасхода времени.
Почему кы не сйвоите кх в тройки? (иау боот уои оэ? 'елт ир ьт гонии?) — Приписывается йджм ВЕр Л 1тОЕ Ввппд) Ой?О) Еще один интересный подход к АЫ -деревьям, называемый "2-3-деревья", был предложен Джоком Хопкрофтом (ЛоЬп Норсгой) в 1970 году )см. АЬо, Норсго1с, П!п1ап, ТЬе 1)ез)лп апд Апа)уев оу Сотритег А)йогНЬгов ~Веабт6, Маввд Абйвоп%ев)еу. 1974), Сйаргег 4).
Идея этого подхода заключается в том, что из каждого узла могут выходить либо две, либо три ветви; при этом требуется, чтобы все внешние узлы находились иа одном уровне. Каждый внутренний узел содержит либо адин, либо два ключа, как показано иа рис. 26, Рис. 26. 2-3-дерево. Вставку в 2-3-дерево пояснить несколько проще по сравнению со вставкой в Ач1 дерево: чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто вставить его как второй ключ. С другой стороны, если в узле уже содержатся два ключа, делим их иа два "одитжлючевых" узла и вставляем средний ключ в родительский узел. Это, в свою очередь, может принести к делению родительского узла.
На риг. 27 показан описанный процесс вставки ключа в 2-3- дерево, изображенное иа рис. 26, Рис. 27. Вставка иовото ключа И в 2-3-дерево, приведенное иа рис, 26. Дж. Э. Хопкрофт (3. Е. Норсгой) обнаружил, что удаление, конкатенация и разделение с 2-3-деревьями проводятся достаточно просто и очень похожк иа аналогичные операции с АЫ -деревьями.
Р. Байер (К. Вауег) сРгос. АСМЯ1СГ1ВЕТ%откяйор (1971), 219-235] предложил интересное представление 2-3-деревьев в виде бинариьж деревьев. Взгляните на рис. 28, на котором показано такое представление дерева, изображенного на рис. 26. Один бит калслого узла используется для того, чтобы отличать "горизонтальные" правые ссэллки 8118!С от "вертикальных". Заметьте, что ключи в таком дереве расположены, как и в бинарном дереве поиска, в симметричном порядке слева направо, Оказывается, что при вставке нового ключа в деревья такого типа необходимо выполнить те же преобразования, что и при вставке в бинарное дерево, а именно — однократные и двукратные повороты (хотя в этом случае требуется только одна версия каждого поворота без отражений относительно вертикальной оси, необходимых для алгоритмов А и С).
Рис. 28. 2-3-дерево (см. рис. 26), представленное в виде бинарного дерева поиска, Развитие этих идей привело к появлению различных вариялтов сбалансированных деревьев, среди которых особенно известны красно-черные деревья (гед-5!асй Сгсмя), именуемые также симметричными бинарными В-деревьями или полусбалансированными деревьями [К. Вауег, Асса 1п1оппайса 1 (1972), 290-306; 1,. Оп!Ьая апд К. Яес!Яен!с)с, КОСЯ 19 (1978), 8-21; Н. Л. О!стсй, ИА1КО 1п1оггпапцпе Тйеолцпе 16 (1982), 51-71; К. Е.
Тяг)ап, !пб Ргос. 1,еСсегя 16 (1983), 253 — 257; Т, Н. Сопиев, С. Е. Бесяегяоп апд К. 1. Кстеяс, 1псгодисйоп со А)8ог!сЛшя (М1Т Ргеяя, 1989), СЬарсег 14; К. Яедйекйссс, А!Яог!сйшя ш С (АйИяоп-%ея!еу, 1997), 313.4). Существует, кроме того, связанное семейство деревьев, называемых истерическими В-деревьями (Ьуясейса! В-сгеея) или (а,5)-деревьями, в частности (2,4)-деревья (11. Масег апс! Я. С.
Яа1теСег, 1п1 Ргос. Ьессегя 12 (1981), 199 — 202; Я. Нпсй!еясоп апд К. МеЫЬогп, АсСа 1пуоппая!са 17 (1982), 157-184). Когда одни ключи встречаются чаще других, логично разместить более "частые" ключи ближе к корню дерева, как в случае использования оптимальных бинарных деревьев„о которых шла речь в разделе 6.2.2. Динамические деревья, которые делают возможным поддержание взвешенной сбалансированности в заданных пределах около оптимальной, называемые "анси!синими" деревыми (Мазей !геев), были разработаны С.
В. Бентом (Я. %. Вепс), Д. Д. Слитором (О. О. Яеасог) и Р. Е. Таржаном (К.. Е. Тат)ап) (Я1СОМР 14 (1985), 545-568; 1. ГесйепЬапш апг! К. Е. Таг1ап, Вей Яуяяеш Тесй. Х 62 (1983), 3139-3158). К сожалению, соответствующие алгоритмы слишком сложны. Существенно проще самокорректирующиеся структуры данных, называемые вяпплнйтмми деревьями (яр(ау Сгее), которые были разработаны Д, Д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
