ДБ- И СДБ- ДЕРЕВЬЯ. ОПЕРАЦИИ, СЛОЖНОСТЬ.

ДБ-дерево.

Максимальное количество ключей на странице – 2, ссылки могут быть не только вертикальными, но и горизонтальными. Реализация (представление в виде массива не удобно и не эффективно, поэтому используют линейные списки):

struct DBTree {

Tdata data;

struct DBTree *left;

struct DBTree *right;

bool h; //чтобы обозначить, по горизонтали или по вертикали направлена правая ветвь

}

Максимальная длина пути = 2log N, при включении характерен рост к корню.

Схемы включения в ДБ-дерево:

Пример:

СДБ-дерево.

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

Свойства:

· Каждая вершина имеет 1 ключ и не более 2 ссылок на поддеревья.

· Ссылки могут быть вертикальными и горизонтальными. Нет ни одного пути поиска с 2 подряд идущими ссылками.

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

Длина самого протяженного пути поиска не более, чем вдвое, превышает высоту дерева log N,

т. е. путь поиска <= 2 log N.

СДБ удобно для вставки.

Реализация:

struct SDBTree {

Tdatadata;

struct SDBTree *left;

struct SDBTree *right;

boo lhr;

boo lhl;

}

Операция вставки:

Пример:

Операция поиска занимает 2 log N – на одном уровне можем сделать <= 2 действий.

Не нашли, что искали? Воспользуйтесь поиском: