Б-деревья. Определение Алгоритмы поиска, включения и исключения. Необходимость их применения. Главная страница сайта Об авторах сайта Контакты сайта

Б-деревья. Определение Методы поиска, включения и исключения. Необходимость их внедрения.


Рейтинг документа: 10
Голосовал 271 человек 271 10

Одна из важных областей применения деревьев – это формирование и использование крупномасштабных деревьев поиска. Если множество данных, состоящее, например, из миллиона элементов, хранится в виде бинарного дерева, то для поиска элемента потребуется в среднем около , т.е. приблизительно 20 шагов поиска. Если происходит обращение к некоторому одиночному элементу, то без больших дополнительных затрат можно обращаться также к целой группе элементов. Отсюда следует, что дерево нужно разбить на поддеревья, считая, что все эти поддеревья одновременно полностью доступны. Такие поддеревья будем называть страницами.

Предположим, что мы решили помещать на странице 100 узлов, тогда дерево поиска, содержащее миллион элементов, потребует в среднем только =3 обращения к страницам вместо 20. Но если дерево растет «случайным образом», то наихудший случай может потребовать даже обращений. Поэтому в случае сильно ветвящихся деревьев почти обязательна схема управления их ростом.

Критерии Р.Бэйера для управления ростом дерева:

1) каждая страница содержит не более 2n элементов (ключей);

2) каждая страница, кроме корневой, содержит не менее n элементов;

3) каждая страница является либо листом, т.е. не имеет потомков, либо имеет m+1 потомков, где m – число находящихся на ней ключей;

4) все листья находятся на одном и том же уровне.

В дереве с N элементами и максимальном размере страницы 2n узлов наихудший случай потребует обращений к страницам.

Если необходимо найти элемент x среди ключей k1, …, km мы имеем одну из следующих ситуаций:

1) ki

2) x>km. Продолжаем поиск на странице pm^;

3) x

Если в каком-то случае ссылка равна nil, .т.е нет соответствующего потомка, то элемента с ключом x нет во всем дереве и поиск заканчивается.



Другие страницы сайта


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