Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



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




Читайте также:
  1. Bonpoс 19 Сплавы на основе алюминия и магния. Свойства и области применения.
  2. D) определение стратегии развития общества.
  3. D.определение стратегии
  4. PR: понятие и определение.
  5. А) Необходимость истинного Богопознания для отсечения лжеучений (2,1-8).
  6. А. Определение фольклора
  7. Адаптации, определение понятия, классификация.
  8. Активное и реактивное сопротивление элементов сети (физический смысл, математическое определение), полное сопротивление сети.
  9. Акустические материалы. Значение в строительстве, область применения.
  10. Алгоритмы

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

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

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

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

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

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

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

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

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

1) ki<x<ki+1 для 1<=i<m. Мы продолжаем поиск на странице pi^;

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

3) x<k1. Продолжаем поиск на странице p0^.

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

 
 

 

 


Дата добавления: 2015-04-18; просмотров: 26; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2020 год. (0.004 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты