Студопедия

КАТЕГОРИИ:

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



Операция включения в В – дерево.




Читайте также:
  1. Агропромышленная интеграция и кооперация в сельскохозяйственном производстве (значение, понятие, виды)
  2. Б-деревья. Определение Алгоритмы поиска, включения и исключения. Необходимость их применения.
  3. Билет № 13 Загрузка компьютера: Тест начального включения – POST. Загрузка DOS
  4. Билет № 14 Загрузка компьютера: Тест начального включения – POST. Загрузка MS Windows 9.x
  5. Валютная политика: понятие, цели, формы и инструменты. Валютные ограничения по текущим и финансовым операциям.
  6. ВАЛЮТНОЕ РЕГУЛИРОВАНИЕ И КОНТРОЛЬ, ОСУЩЕСТВЛЯЕМЫЙ БАНКОМ ПО ЭКСПОРТНЫМ И ИМПОРТНЫМ ОПЕРАЦИЯМ.
  7. Включения записи в БД
  8. Вопрос 24 Учет расчетов с персоналом по прочим операциям
  9. Вопрос 60. Учет затрат по нормам. Порядок списанная и включения отклонений от норм в себестоимость отдельных изделий.
  10. Вопрос № 60 Топография толстой кишки. Колостомия. Операция наложения противоестественного заднего прохода по способу Майдля.

Предположим, что страница уже считана в оперативную память. Она представляет собой последовательность ключей.

k1 £ k2 £ … £ km

 

 

 


Для поиска при больших m может быть использован бинарный поиск. Если поиск неудачен, то мы попадаем в одну из следующих ситуаций:

1. k i < x < k i + 1,1 < i £ m поиск продолжается по указателю pi ^

2. x < k m поиск продолжается по указателю po ^

3. x > km поиск продолжается по указателю pm^

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

При m < 2*n алгоритм прост.

Пример.

 

 

       
   

 

 


Необходимо включить 22.

1. Поиск этого элемента, если нет, то

2. Определение страницы, где он должен находиться (в данном случае вторая)

3. Если необходимо, расщепить страницу. Суть этой операции : при включении элемента В – дерево должно оставаться В – деревом. Количество элементов 2*n + 1 делится поровну между новой и старой страницей.

 

 

 
 

 

 


Медиана ( средний элемент ) передаётся вверх к родителю . Родитель тоже может быть переполнен включением нового элемента, над этим родителем происходит операция расщепления и так до корня . Такая схема сохраняет все характерные свойства В – дерева и в крайнем случае включение элемента может подняться до самого корня . Фактически только в этом случае может увеличиться высота В – дерева . Таким образом В – дерево растёт от листьев к корню .

Типы переменных, которые используются в В – дереве .

Type Ptr = ^Page ;

Index = 0 .. 2*n ;

Element = record

key : integer ;

p : Ptr ;

count : integer ;

end ;

 

Page = record

M : Index ;

p0 : Ptr ;

e : array [ 1 .. 2*n ] of element

end ;


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





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