Главная | Случайная
Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






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




ДБ-дерево.

Максимальное количество ключей на странице – 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 действий.

 

 




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

vikidalka.ru - 2015-2019 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных