AOP_Tom3 (1021738), страница 131
Текст из файла (страница 131)
упр. 25). Однако при вставке могут оказаться необходимыми несколько ребалансировок дерева. При ослаблении условия (17) количество нужных ребалансировок уменьшается (правда, за счет увеличения времени поиска). На первый взгляд может показаться, что для взвешенно-сбалансированных деревьев необходимо больше памяти, однако иногда ее нужно даже меныпе, чем для обычных сбалансированных деревьев! Если в каждом узле уже имеется поле КАИК для представления линейного списка, то это и есть вес левого поддерева, а соответствующие правые веса могут быть определены при движении вниз по дереву.
Альтернативы Ач'Ь-деревьям. Помимо использования АЪ'Ь-деревьев, было предложено несколько других подходов к организации деревьев, гарантирующих логарифмическое время доступа. Например, К. К. Фостер (С. С. Гоэ1ег) (САСМ 16 (1973). 513 — 517) рассмотрел бинарные деревья, которые получаются, если ограничить разность высот поддеревьев некоторой величиной к. Такие структуры называются НВ(/с) (что означает "Ье!ЕЬ1-Ьа!апсед" — "сбалансированные по высоте").
В этих терминах рассмотренные сбалансированные деревья представляют собой частный случай НВ(1). Интересная концепция взвешемно-сбалансированных деревьев (юе!дЫ-5а!апсед 1геез) бььта изучена Ю. Нивергельтом (1. %еиегйе!1), Э. Рейнгольдом (Е. Ве!пбо!б) и сЬ К. Вонгом (С. К. 1топЕ). Они не рассматривали высоту деревьев, а поставили условие, которому должны удовлетворять поддеревья всех узлов: Однако требуемые для сохранения взвешенной сбалансированности накладные расходы отнимают больше времени, чем алгоритм А, и сохранение двух битов на узле не представляется достаточной компенсацией перерасхода времени. Почему вы не сдвоите их в тройки? (иФу ооп'г уои Ратх 'етп ио т гптеев?) — пРиписывается ед?ки ВеРРА (уОБ! ВеяяА) С9?0) Еще один интересный подход к АЪ'1.-деревьям, называемый "2-3-деревья", был предложен Джоном Хопкрофтом (,1ойп Норсго11) в 1970 году !см.
АЬо, Норсгой., Н))шап, ТЛе 1)ев)йп апд Апа!уз!в о1 Соп1ригег А)боП1Лтв (Яеадтб, Мазал Аоп)зон%ее)еу, 1974), СЬаргег 4]. Идея этого подхода заключается в том, что из каждого узла могут выходить либо две, либо три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа, как показано на рис. 26. Рис. 26.
2-3-дерево, Вставку в 2-3-дерево пояснить несколько проще по сравнению со вставкой в АЪ'1;дерево: чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто вставить его как второй ключ. С другой стороны, если в узле уже содержатся два ключа, делим их на два "одноключевых" узла и вставляем средний ключ в родительский узел. Это, в свою очередь, может привести к делению родительского узла. На рис. 27 показан описанный процесс вставки ключа в 2-3- дерево, изображенное на рис. 26. Рис. 27.
Вставка нового ключа И в 2-3-дерево, приведенное на рис. 26. Дж. Э. Хопкрофт !Д. Е. Норсгой) обнаружил, что удаление, конкатенация и разделение с 2-3-деревьями проводятся достаточно просто и очень похожи на аналогичные операции с А1'Ь-деревьями. Р. Байер (Н. Вауег) [Ргос. АСМ-ЯСГ1ОЕТ ХогкэЛор (1971), 219-235) предложил интересное представление 2-3-деревьев в виде бинарных деревьев.
Взгляните на рис. 28, на котором показано такое представление дерева, изображенного на рис. 26. Один бнт каждого узла используется для того, чтобы отличать "горизонтальные" правые ссылки 81.168 от "вертикальных'! Заметьте, что ключи в таком дереве расположены, как и в бинарном дереве поиска, в симметричном порядке слева направо. Оказывается, что при вставке нового ключа в деревья такого типа необходимо выполнить те же преобразования. что и прн вставке в бинарное дерево, а именно -- однократные и двукратные повороты (хотя в этом случае требуется только одна версия каждого поворота без отражений относительно вертикальной оси, необходимых для алгоритмов А и С).
Рис. 28. 2-3-дерево (см рис. 26), представленное в виде бинарного дерева поиска. Развитие этих идей привело к появлению различных вариантов сбалансированных деревьев, среди которых особенно известны красно-черные деревья (геН-5!асй !геев), именуемые также симметричными бинарными В-деревьями или полусбалансированными деревьями [Н. Вауег, Асса 1пЕогтапса 1 (1972), 290-306; Ь. СшЬаэ апс! Н. Бебйекчс)с, РОСЯ 19 (1978), 8-21; Н. 3. О!!г!е, НАЖО ЕпХогшабцие ТЛйопцие 16 (1982), 51 — 71; Н. Е, Таг1ап, 1пб Ргос. Легсесч 16 (1983), 253 — 257; Т. Н. Согшеп, С. Е. ?е!эегвоп апг! Н. 1.
Н!геэ1, 1пггобисг!оп го А!8оПгЛтэ (М1Т Ргеэв, 1989), СЬар!ег 14; Н. Бебйевчс)г, А!8огНЛпи !и С (АсЫ!зоп-%еэ!еу, 1997), 313.4). Существует, кроме того, связанное семейство деревьев, называемых истерическими В-деревьями (Ьуэ!ег!са! В-!геев) или (а,Ь)-деревьями, в частности (2,4)-деревья [1). Ма!ег апс! Б. С. Ба(ге!ег, Хпб Ргос.
Ъесгегэ 12 (1981), 199-202; Б. НпсЫ!езгоп апд К. МеЫЬогп, Ас!а 7лГогтаИса 17 (1982), 157-184[. Когда одни ключи встречаются чаще других, логично разместить более "частые" ключи ближе к корню дерева, как в случае использования оптимальных бинарных деревьев, о которых шла речь в разделе 6.2.2. Динамические деревья, которые делают возможным поддержание взвешенной сбалансированности в заданных пределах около оптимальной, называемые "смещеннмми" деревьями (Ьгаэсв аггея), были разработаны С.
В. Вентом (8. %. Веп!), Д. Д. Слитором (В. В. 8!еагог) и Р. Е. Таржаном (Н. Е. Таг1ап) [ЯСОМР 14 (1985), 545-568: д. Ге!8епЬашп апб Н. Е. Тат)ап, Ве!! Яуэсеш ТесЛ. Х 62 (1983), 3139-3158). К сожалению, соответствующие алгоритмы слишком сложны. Существенно проще самокорректирующиеся структуры данных, называемые вмшлиутььми деревьями (эр!ау !гее), которые были разработаны Д, Д. Слитором и Р.
Е. Таржаном [ХАСМ 32 (1985), 652-686]. Они основаны на идеях, подобных используемым при эвристических перемещениях и перестановках (см. раздел 6.1). Данная технология была исследована Б. Алленом (В. А!!еп) и Дж. Мунро (Я. Манго) [,УАСМ 25 (1978), 526-535[, а также Дж. Битнером (3. В!!пег) ~Б1СОМР 8 (1979), 82-110].
Вытянутые деревья, подобно другим видам уже упоминавшихся сбалансированных деревьев, поддерживают операции как вставки и удаления, так и конкатенации и разделения, причем достаточно простым образом. Более того, время, необходимое для доступа к данным в вытянутом дереве, не превышает времени доступа в статически оптимальном дереве, умноженного на некоторую небольшую константу (в установившемся режиме после серии операций с деревом).
Слитор и Таржан предположили, что общее время доступа в вытянутом дереве не превышает оптимального времени доступа к данным и времени, необходимого для выполнения динамических поворотов согласно любому алгоритму работы с бинарными деревьями, умноженного на константу. Рандомнзация позволяет использовать методы, даже более быстрые н простые, чем вытянутые деревья.
Жан Вуйлемен (Леан Ушйеппп) (САСМ 23 (1980), 229-239) ввел понятие декартовых деревьев (саггеебап 1геея), в которых каждый узел имеет два ключа (х,у). Часть х упорядочена слева направо, как в бинарных деревьях поиска; часть у упорядочена сверху вниз, как в случае приоритетной очереди (см. раздел 5.2.3). С.
Р. Арагон (С. В. Ага8оп) и Р. Г. Зайдель (В. О. БеЫе)) присвоили таким структурам данных очень цветастое название егеар, которое получено в результате комбинирования частей слов 1геез и пеарэ. (Видимо, наилучший русский термин должен звучать как дуча — от дерева и кучи. — Прим. перев.) Только одна дуча может быть построена на основе п данных пар ключей (хы уг), ..., (х„, у„), егли все х и у различны. Один из путей получения дучи — вставка х согласно алгоритму 6.2.2Т в соответствии с порядком у. Однако имеется еще один простой алгоритм для непосредственной вставки любых новых пар в дучу.
Арагон и Зайдель обнаружили (РОС8 30 (1989), 540 — 546), что, если х представляют собой обычные ключи, а у выбираются случайным образом, можно быть уверенным, что дуча имеет вид случайного бинарного дерева поиска. В частности, дуча со случайными значениями у всегда будет сбалансирована, за исключением случая зкспоненциально малой вероятности (см. упр.
5.2.2 — 42). Арагон и Зайдель также показали, что дучи могут быть легко "скошены", так что, например, ключ х с относительной частотой 1 будет располагаться вблизи корня в соответствии со своей частотой, если с ним будет ассоциирована величина у = С'11, где ь7 — случайное число между 0 и 1. Дучи, в целом, предпочтительнее вытянутых деревьев, как показали некоторые проведенные Д. Э.
Кнутом эксперименты, связанные с расчетами выпуклых оболочек (3АСМ 45 (1998), 288-323]. В следующее издание книги планируется добавить раздел 6.2.5, посвященный Ф рандомлзированяым структурам данных. В нем будут рассмотрены спнскн с пропусками (И'. Рнбй, САСМ 33 (1990), 668-6761, рандомвзнрованные бинарные деревья поиска (В. Волга апд С.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
