Б-деревья (B-tree) - другая форма сбалансированного дерева, которая более
наглядна, чем AVL-деревья. Каждый узел в Б-дереве содержит ключи данных
и несколько указателей на дочерние узлы. По-
скольку каждый узел хранит несколько эле-
ментов, узлы часто называются сегментами.
Между каждой парой смежных дочерних
указателей в узле находится ключ, который вы
можете использовать для определения вет-
ви, по которой следует двигаться при добав-
лении или поиске элемента. Рис. 7.14. Окно программы AVL
Например, в дереве, изображенном на рис. 7.15, корневой
узел содержит два ключа - G и R. Чтобы разместить элемент со значением мень-
ше G, нужно следовать вниз по первой ветви. Чтобы найти значение между G и R,
необходимо пройти вниз по второй ветви. Разместить элемент со значением боль-
ше R можно, выбрав третью ветвь. Б-дерево порядка К обладает следующими свойствами:
- каждый узел содержит максимум 2 * К ключей;
- каждый узел, за исключением корня, содержит не менее К ключей;
- внутренний узел, где расположено М ключей, имеет М + 1 дочерних узлов;
- все листья дерева находятся на одном уровне
Б-дерево на рис. 7.15 имеет порядок 2. Каждый узел может содержать до че-
тырех ключей. Каждый узел, кроме корня, должен иметь не менее двух ключей.
Для удобства в узлы Б-дерева обычно поме-
щают четное количество ключей, поэтому по-
рядок является, как правило, целым числом.
Требование, чтобы каждый узел в Б-де-
реве порядка К содержал от К до 2 * К клю-
чей, поддерживает баланс дерева. Поскольку
каждый узел должен содержать, по крайней
мере, К ключей, он должен иметь не меньше К + 1 дочерних узлов, поэтому дерево не
может стать слишком высоким и тонким. Б-дерево, содержащее N узлов, может
иметь глубину максимум O(logK+1(N). Следовательно, сложность алгоритма поиска
в таком дереве будет порядка O(logN). Хотя это и не так очевидно, добавление и уда-
ление элементов из Б-дерева также имеют сложность порядка O(logN). РИС. 7.15. Б-дерево
Опубликовал Kest
October 29 2009 09:54:46 ·
1 Комментариев ·
12026 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
MOZGoEZIK June 17 2011 21:54:44
Очень полезная штука :-)
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
