при увеличении роста левого и правого поддеревьев, поэт организация ББ-дерева кажется несколько HCKyccTBeHB - У нас нет доказательств необычности такой организащ^! и лишь интуиция говорит нам, что здесь что-то не то , и следует избавиться от такой асимметрии. Это ведет к ПОНЯТ1Г' симметричного бинарного Б-дерева (СББ-дерева), kotoiiI° также было предложено Бэйером [4.4] в 1972 г. Такое ncf

(LL)

(LR!

Рис. 4.52. Включение в СББ-деревья.

строение дает в среднем несколько более эффективные деревья поиска, но алгоритмы включения и удаления при этом несколько сложнее. Кроме того, теперь каждый узел требует двух разрядов (булевские переменные th и rh) для обозначения природы его ссылок.

Поскольку мы собираемся детально остановиться на проблеме включения, то нам надо еще раз определить раз.чичия в четырех случаях роста поддеревьев. Они показаны рис. 4.52, на котором наглядно видна полученная симметри*-Заметим, что всегда, когда растет поддерево узла А, не име щего братьев, корень этого поддерева становится братом Этот случай не нуждается в дальнейшем обсуждении..

Четыре случая, приведенные на рис. 4.52, иллюстрируют переполнение страницы и последующее ее расщепление. Они К^ечты в соответствии с направлениями горизонтальных ( ылок, связывающих трех братьев на рисунках в среднем лхолбце. Исходная ситуация показана в левом столбце, в срец-jjefj столбце показано, что узел, находящийся внизу, подни-яается с ростом поддерева; на рисунках правого столбца по-[iijaan результ-ат перестановки узлов при расщеплении страницы.

Желательно больше не возвращаться к понятию страниц, да основе которого разработана эта организация, так как все, к чему мы стремимся, - это ограничить максимальную длину пути поиска значением 2-\ogN. Для этого нужно только, чтобы нигде на пути поиска не встречались две последовательные горизонтальные ссылки. Но нет причины запрещать любые узлы с горизонтальными ссылками налево и направо. Поэтому мы определяем СББ-дерево как дерево со следующими свойствами:

(Каждый узел содержит один ключ и не более двух по.ц-liepeBbeB (ссылок). Каждая ссылка либо горизонтальная, либо вертикальная. Ни на каком пути поиска нет двух последовательных горизонтальных ссылок. 3. Все терминальные узлы (узлы, не имеющие потомков) находятся на одном (терминальном) уровне.

Из этого определения следует, что самый длинный путь поиска не более чем в два раза превосходит высоту дерева. Так как никакое СББ-дерево с N узлами не может иметь высоту, большую [logЛ/], то 2-[logЛ/] является верхним пределом длины пути поиска.

Чтобы читатель наглядно представил себе, как растут эти деревья, мы отсылаем его к рис. 4.53. На нем показаны изменения четырех деревьев при последовательных включениях Элементов с ключами, перечисленными в строках (4.85), где Точки с запятой отмечают моменты увеличения высоты дерева:

(1) 1 2; 3; 4 5 6; 7;

(2) 5 4; 3; 1 2 7 6; (4.85)

(3) 6 2; 4; 1 7 3 5;

(4) 4 2 6; 1 7; 3 5;

ти рисунки особенно наглядно иллюстрируют третье свой-тво Б-деревьев: все терминальные узлы находятся на одном iPoBHe. Поэтому хочется сравнить эти структуры с только что Подстриженными садовыми кустарниками. Мы будем называть такие структуры кустарниками.

duu 4. динамические ижрормациюнные структуры

Алгоритм построения кустарников сформулирован в {4 в^. Он основан на определении типа узла (4.86) с двумя коцп нентами lh и rh, обозначающими горизонтальность дев и правой ссылок. °

type node - record key: integer;

count: integer;

left,right: ref; (4.86)

/А,гЛ: boolean

Рекурсивная процедура search вновь строится по основной схеме алгоритма включения в бинарное дерево [см. (4.87)] Добавляется третий параметр h\ он указывает, изменилась ли структура .поддерева с корнем р, и полностью соответствует параметру h в программе поиска в Б-дереве. Однако нужно отметить последствия представления страниц в виде связанных списков: проход любой страницы происходит с помощью одного или двух обращений к процедуре поиска. Мы должны различать два случая: когда поддерево (обозначенное вертикальной ссылкой) выросло, и когда узел-брат (обозначенный горизонтальной ссылкой) получил другого брата и, следовательно, требуется расщепление. Эта проблема легко рещается введением следующих трех значений h:

1. ft = 0: никаких изменений структуры дерева не требуется.

2. h=\: узел р получил брата.

3. ft = 2: поддерево р увеличилось в высоте.

Заметим, что действия, предпринимаемые для переупорядочения узлов, очень напоминают те, которые были разработаны для алгоритма поиска в сбалансированном дерене (4.63). Из (4.87) видно, что все четыре случая можно реа.пй-зовать простыми поворотами ссылок: однократными поворотами налево или направо и двукратными поворотами налево и направо или направо и налево. В самом деле, процедуре (4.87) оказывается несколько проще, чем (4.63). Ясно, что схема кустарниковых деревьев является альтернативой критерию АВЛ-сбалансированности. Поэтому возможно и желательно сравнение их характеристик.

Мы отказываемся от анализа точными, математическим-методами и обратим основное внимание на некоторые су ственные различия. Можно доказать, что АВЛ-сбалансировИ ные деревья являются подмножеством кустарниковых ревьев. Таким образом, класс последних щире. Отсюда дует, что их длина пути в среднем больше, чем у АВЛ-Д ревьев. Отметим, что в этом отношении наихудший с