Бинарные Б-деревья

Бинарное Б-дерево - это Б-дерево первого порядка (n =1).

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

Бинарное Б-дерево (ББ-дерево)

· состоит из узлов с одним или двумя элементами;

· содержит две или три ссылки на потомков (еще его называют 2-3 дерево);

· все листья находятся на одном уровне;

· все нетерминальные страницы содержат два или три потомка.

Для представления ББ-дерева можно выбрать следующую структуру:

typedef struct node {
int key;
node *left;
node *right;
int h;
};

left - указатель на страницу-наследник;

right - указатель либо на страницу-потомок, либо на страницу-брата; для различия используется показатель h (при одном значении фиксируется горизонтальное перемещение, а при другом - вертикальное).

Такое дерево поиска гарантирует максимальную длину пути .

Включение в ББ-дерево

Возможны следующие варианты:

1. Растет правое поддерево узла А и когда А - единственный ключ на странице, тогда потомок В становится братом А (вертикальная ссылка становится горизонтальной).

2. Если А уже имеет брата, тогда получаем страницу с тремя узлами. Необходимо ее расщепить, т.е. средний узел В передается на ближайший более высокий уровень.

3. Узел В один на странице. Увеличилась высота левого поддерева узла В. Левое поддерево А может стать братом В, но необходим поворот, так как левая ссылка не может быть горизонтальной.

4. Если В уже имеет брата, тогда подъем А даст страницу с тремя узлами, что требует расщепления: С становится потомком В, который поднимается на ближайший более высокий уровень.

Алгоритм включения с левой и правой стороны различен, поэтому использовать ББ-деревья несколько неудобно.

Лучше использовать Симметричное бинарное Б-дерево.

У такого дерева узел может иметь горизонтальные ссылки и направо, и налево.

СББ-дерево имеет следующие свойства:

1. Каждый узел содержит один ключ и не более двух поддеревьев (ссылок).

2. Каждая ссылка либо горизонтальная, либо вертикальная. Ни на каком пути поиска нет двух последовательных горизонтальных ссылок.

3. Все терминальные узлы находятся на одном терминальном уровне.

Структура СББ-дерева включает в себя две переменные lh, rh для обозначения природы ссылок.

Самый длинный путь поиска не более чем в два раза превосходит высоту дерева.

Максимальная высота СББ-дерева с n узлами – log n.

Самый длинный путь – 2 log n.

Основное свойство Б-деревьев – все терминальные узлы находятся на одном уровне.

Такие структуры еще называют кустарниками (т.к. их можно сравнить с подстриженными кустарниками).

При построении Б-деревьев действия, предпринимаемые для переупорядочивания узлов, подобны действиям, выполняемым в сбалансированном дереве. Таким образом, можно сказать, что AVL -деревья являются подмножеством кустарниковых деревьев.

1. У кустарниковых деревьев длина пути в среднем больше, чем у AVL -деревьев, зато перестройка узлов у кустарниковых деревьев будет происходить реже.

2. Сбалансированные деревья предпочтительны в тех случаях, когда поиск ключей происходит намного чаще, чем включение (или удаление).