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

Все .эти алгоритмы могут использоваться как с полями KEY, так и с полями RANK (или с обоими), хотя в случае конкатенации с помощью ключей все ключи дерева L2 должны быть больше ключей дерева Li. Для общих целей часто предпочтительнее использовать деревья с тремя связями, в которых наряду с полями LLINK и RLINK применяется поле UP, которое указывает на родительский узел, и однобитовое поле, указывающее, каким потомком является данный узел: левым или правым. Такие деревья упрощают используемые алгоритмы и позволяют определить узел без явного указания пути к нему. Можно написать подпрограмму для удаления узла NODE(P) по заданному Р, удаления узла, следующего за NODE(P) в симметричном порядке, для нахождения списка, содержащего NODE(P), и т. д. В алгоритме удаления для деревьев с тремя связями не нужно строить список (16), так как ссылки UP предоставляют всю необходимую информацию. Конечно, при вставке, удалении или повороте в таких деревьях требуется немного больше усилий для изменения ссылок. Использование "трехсвязных" деревьев вместо двухсвязных аналогично использованию двойных связей вместо одинарных: можно начать работу с любого места и двигаться как вперед, так и назад. Полное описание алгоритмов, основанных на трехсвязных деревьях, приводится в диссертации Крейна (Stanford University, 1972).

Альтернативы AVL-деревьям. Помимо использования AVL-деревьев, было предложено несколько других подходов к организации деревьев, гарантирующих логарифмическое время доступа. Например, К. К. Фостер (С. С. Foster) [САСМ 16 (1973), 513-517] рассмотрел бинарные деревья, которые получаются, если ограничить разность высот поддеревьев некоторой величиной к. Такие структуры называются НВ(А;) (что означает "height-balanced" - "сбалансированные по высоте"). В этих терминах рассмотренные сбалансированные деревья представляют собой частный случай НВ(1).

Интересная концепция взвешенно-сбалансированных деревьев {weight-balanced trees) была изучена Ю. Нивергельтом (J. Nievergelt), Э. Рейнгольдом (Е. Reingold) и Ч. К. Вонгом (С. К. Wong). Они не рассматривали высоту деревьев, а поставили условие, которому должны удовлетворять поддеревья всех узлов:

v-l<i5<v+l, (17)

правый вес

где левый и правый веса означают количество внешних узлов в левом и правом поддеревьях соответственно. Можно показать, что при вставке взвешенную сбалансированность можно поддерживать с помощью однократных и двукратных поворотов, как в алгоритме А (см. упр. 25). Однако при вставке могут оказаться необходимыми несколько ребалансировок дерева. При ослаблении условия (17) количество нужных ребалансировок уменьшается (правда, за счет увеличения времени поиска).

На первый взгляд может показаться, что для взвешенно-сбалансированных деревьев необходимо больше памяти, однако иногда ее нужно даже меньше, чем для обычных сбалансированных деревьев! Если в каждом узле уже имеется поле RANK для представления линейного списка, то это и есть вес левого поддерева, а соответствующие правые веса могут быть определены при движении вниз по дереву.

Однако требуемые для сохранения взвешенной сбалансированности накладные расходы отнимают больше времени, чем алгоритм А, и сохранение двух битов на узле не представляется достаточной компенсацией перерасхода времени.

Почему вы не сдвоите их в тройки? (Why dont you pair em up in ttirees?) - Приписывается ЁДЖИ БЕРРА (YOGI BERRA) (1970)

Еще один интересный подход к AVL-деревьям, называемый "2-3-деревья", был предложен Джоном Хопкрофтом (John Hopcroft) в 1970 году [см. Aho, Hopcroft, Ullman, The Design and Analysis of Computer Algorithms (Reading, Mass.: Addison-Wesley, 1974), Chapter 4]. Идея этого подхода заключается в том, что из каждого узла могут выходить либо две, либо три ветви; при этом требуется, чтобы все внешние узлы находились на одном уровне. Каждый внутренний узел содержит либо один, либо два ключа, как показано на рис. 26.

Рис. 26. 2-3-дерево.

Вставку в 2-3-дерево пояснить несколько проще по сравнению со вставкой в AVL-дерево: чтобы поместить новый ключ в узел, в котором содержится ровно один ключ, необходимо просто вставить его как второй ключ. С другой стороны, если в узле уже содержатся два ключа, делим их на два "одноключевых" узла и вставляем средний ключ в родительский узел. Это, в свою очередь, может привести к делению родительского узла. На рис. 27 показан описанный процесс вставки ключа в 2-3-дерево, изображенное на рис. 26.

Рис. 27. Вставка нового ключа М в 2-3-дерево, приведенное на рис. 26.

Дж. Э. Хопкрофт (J. Е. Hopcroft) обнаружил, что удаление, конкатенация и разделение с 2-3-деревьями проводятся достаточно просто и очень похожи на аналогичные операции с AVL-деревьями.

p. Байер (R. Bayer) [Proc. ACM-SIGFIDET Workshop (1971), 219-235] предложил интересное представление 2-3-деревьев в виде бинарных деревьев. Взгляните на рис. 28, на котором показано такое представление дерева, изображенного на рис. 26. Один бит каждого узла используется для того, чтобы отличать "горизонтальные" правые ссылки RLINK от "вертикальных" Заметьте, что ключи в таком дереве расположены, как и в бинарном дереве поиска, в симметричном порядке слева направо. Оказывается, что при вставке нового ключа в деревья такого типа необходимо выполнить те же преобразования, что и при вставке в бинарное дерево, а именно - однократные и двукратные повороты (хотя в этом случае требуется только одна версия каждого поворота без отражений относительно вертикальной оси, необходимых для алгоритмов А и С).

Рис. 28. 2-3-дерево (см. рис. 26), представленное в виде бинарного дерева поиска.

Развитие этих идей привело к появлению различных вариантов сбалансированных деревьев, среди которых особенно известны красно-черные деревья {red-black trees), именуемые также симметричными бинарными В-деревьями или полусбалансированными деревьями [R. Bayer, Acta Informatica 1 (1972), 290-306; L. Guibas and R. Sedgewick, FOCS 19 (1978), 8-21; H. J. Olivie, RAIRO Informatique Theorique 16 (1982), 51-71; R. E. Tarjan, Inf. Proc. Letters 16 (1983), 253-257; T. H. Gormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms (MIT Press, 1989), Chapter 14; R. Sedgewick, Algorithms in С (Addison-Wesley, 1997), §13.4]. Существует, кроме того, связанное семейство деревьев, называемых истерическими В-деревьями (hysterical B-trees) или (а, 6)-деревьями, в частности (2,4)-деревья [D. Maier and S. С. Salveter, Inf. Proc. Letters 12 (1981), 199-202; S. Huddleston and K. Mehlhorn, Acta Informatica 17 (1982), 157-184].

Когда одни ключи встречаются чаще других, логично разместить более "частые" ключи ближе к корню дерева, как в случае использования оптимальных бинарных деревьев, о которых шла речь в разделе 6.2.2. Динамические деревья, которые делают возможным поддержание взвешенной сбалансированности в заданных пределах около оптимальной, называемые "смещенными" деревьями {biased trees), были разработаны С. В. Бентом (S. W. Bent), Д. Д. Слитором (D. D. Sleator) и Р. Е. Таржаном (R. Е. Tarjan) [SICOMP 14 (1985), 545-568; J. Feigenbaum and R. E. Tarjan, Bell System Tech. J. 62 (1983), 3139-3158]. К сожалению, соответствующие алгоритмы слишком сложны.

Существенно проще самокорректирующиеся структуры данных, называемые вытянутыми деревьями {splay tree), которые были разработаны Д. Д. Слитором и Р. Е. Таржаном [JACM 32 (1985), 652-686]. Они основаны на идеях, подобных используемым при эвристических перемещениях и перестановках (см. раздел 6.1). Данная технология была исследована Б. Алленом (В. Allen) и Дж. Мунро (J. Munro) [JACM 25 (1978), 526-535], а также Дж. Битнером (J. Bitner) [SICOMP 8 (1979),