Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 109
Текст из файла (страница 109)
В строках 6-9 процедура либо завершает свою работу неудачей (если х является листом), либо рекурсивно вызывает себя для поиска в соответствующем поддереве х (после выполнения чтения с диска необходимого дочернего узла, являющегося корнем исследуемого поддерева). На рис. 18.1 показана работа процедуры В Ткее БеАксн: светлым цветом выделены узлы, просмотренные в процессе поиска ключа гс. Процедура В Ткее БеАксн, как и процедура Ткее БКАксн при поиске в бинарном дереве, проходит в процессе рекурсии узлы от корня в нисходящем порядке. Количество дисковых страниц, к юторым выполняется обращение процедурой В Ткее БеАксн, равно 0 (Л) = 0 (1о8, и), где Л вЂ” высота В-дерева, а и — количество содержащихся в нем узлов.
Поскольку и [х] < 2с, количество итераций цикла зчЫ1е в строках 2-3 в каждом узле равно 0 (с), а общее время вычислений — 0(/Л) = 0(т1об,п). Создание пустого В-дерева Для построения В-дерева Т мы сначала должны воспользоваться процедурой В Ткее СкеАте для создания пустого корневого узла, а затем вносить в него новые ключи при помощи процедуры В Ткее 1нзект. В обеих этих процедурах используется вспомогательная процедура А/.ьОсАте гуопе, которая выделяет дисковую страницу для нового узла за время 0 (1).
Мы можем считать, что зта 524 Часть Ч. Сложные структуры данных процедура не требует вызова П!зк КеА!э, поскольку никакой полезной информа- ции о новом узле на диске нет. В Ткее СкеАте(Т) 1 х ~ — А1л.ОсАте ХО!эе() 2 1еа1 [х] — ткг!е 3 п[х] — О 4 П!ЗК !НК!ТЕ(х) 5 гоог[Т] — х Процедура В ТкЕЕ СЕЕАтЕ требует О (1) дисковых операций и выполняется за время О (1). Вставка ключа в В-дерево Вставка ключа в В-дерево существенно сложнее вставки в бинарное дерево поиска. Как и в случае бинарных деревьев поиска, мы ищем позицию листа, в который будет вставлен новый ключ. Однако при работе с В-деревом мы не можем просто создать новый лист и вставить в него ключ, поскольку такое дерево не будет являться корректным В-деревом. Вместо этого мы вставляем новый ключ в существующий лист.
Поскольку вставить новый ключ в заполненный лист невозможно„мы вводим новую операцию — разбиение (зр1!пшд) заполненного (т.е. содержащего 21 — 1 ключей) узла на два, каждый из которых содержит по г — 1 ключей. Медиана, или средний ключ, — йеу! [у] (тегйап 1сеу) — при этом перемещается в родительский узел, где становится разделительной точкой для двух вновь образовавшихся поддеревьев. Однако если родительский узел тоже заполнен, перед вставкой нового ключа его также следует разбить, и такой процесс разбиения может идти по восходящей до самого корня. Как и в случае бинарного дерева поиска, в В-дереве мы вполне можем осуществить вставку за один нисходящий проход от корня к листу. Для этого нам не надо выяснять, требуется ли разбить узел, в который должен вставляться новый ключ.
Вместо этого при проходе от корня к листьям в поисках позиции для нового ключа мы разбиваем все заполненные узлы, через которые проходим (включая лист). Тем самым гарантируется, что если нам надо разбить какой-то узел, то его родительский узел не будет заполнен. Разбиение узла В-дерева Процедура В Ткее Беь!т Сн!егз получает в качестве входного параметра незаполненный внутренний узел х (находящийся в оперативной памяти), индекс ! и узел у (также находящийся в оперативной памяти), такой что у = с; [х] является заполненным дочерним узлом х.
Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля х, внося в него информацию о новом Глава 18. В-деревья 525 ,, ' ' »»» ',,и' М И" .,!»1 ~ Т $»,Л л,т,у' !"! !'., », »» Т, !'„Т', Т ТТ Я И' Р у л,~ ~т!т г Г Т,Т,,»,Т, »,!»»;Т., Рис. 18.5. Разбиение узла с ! = 4 В Ткее БР1!т Снп$»(х,г,у) 1 г — АЫ.ОСАТЕ 74ОПЕ() 2 1е У[я) 1 ~Ь] 3 п[х] ~ — $ — 1 4 $ог 7' » — 1 $о $ — 1 5»$о Иеуу[з) — 1сеу +,[у) 6 $Г по$1еаТ'[у) 7 $$»еп $о㻠— 1 $о $ 8 !$о су[а] - с ж»[у) 9 п[у] — $ — 1 10 $ог »' — п[х] + 1 !$озгпго 4 + 1 11 !$о с +! [х) +- с [х) 12 с,+! [х] — х 13 $ог 7 — п[х) !$озгпто $ 14 !$о Йеу +»[х] — Беях] 15 Йеу! [х] — Йеу, [у] 16 п[х) — п[х] + 1 17 $3!зк %н!те(у) 18 $3!8К %К!ТЕ(з) 19 13!8к %К!те(х) дочернем узле.
Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чеп» можем использовать вызов В Ткее Билт Снп !». При этом высота дерева увеличивается на 1. Разбиение — единственное средство увеличения высоты В-дерева. На рис. 18.5 показан этот процесс. Заполненный узел у разбивается медианой Я, которая перемещается в родительский узел.
Те ключи из у, которые больше медианы, помещаются в новый узел г, который становится новым дочерним узлом х. 526 Часть Ч. Сложные структуры данных Процедура В ТКЕЕ КРЫТ СН!ЬО использует простой способ "вырезать и вета. вить". Здесь у является 1-м дочерним узлом х и представляет собой именно тот узел, который будет разбит на два. Изначально узел у имеет 2! дочерних узла (содержит 2! — 1 ключей); после разбиения количество его дочерних узлов снизится до ! (Ф вЂ” 1 ключей).
Узел г получает ! ббльших дочерних узлов (! — 1 ключей) у и становится новым дочерним узлом х, располагаясь непосредственно после у в таблице дочерних узлов х. Медиана у перемещается в узел х и разделяет в нем у и в. В строках 1-8 создается узел в и в него переносятся ббльшие ! — 1 ключей и соответствующие Ф дочерних узлов у. В строке 9 обновляется поле количества ключей в у. И наконец, строки 10-16 делают г дочерним узлом х, перенося медиану из у в х для разделения у и в, и обновляют поле количества ключей в х. В строках 17-19 выполняется запись на диск всех модифицированных данных. Время работы процедуры равно с!(!) из-за циклов в строках 4 — 5 и 7-9 (прочие циклы выполняют О (!) итераций).
Процедура выполняет О (1) дисковых операций. Вставка ключа в В-дерево за один проход Вставка ключа lс в В-дерево Т высоты Б. выполняется за один нисходящий проход по дереву, требующий О (!х) обращений к диску. Необходимое процессорное время составляет О (Ш) = О (! !о8~ и). Процедура В ТКЕЕ !НЕЕкт использует процедуру В ТКЕЕ КРЫТ СНП.О для гарантии того, что рекурсия никогда не столкнется с заполненным узлом. В ТКЕЕ !ХБЕКТ(Т, )с) ! т — тоо![Т) 2 !1п[т) = 2! — 1 3 т!зеп в — АЫ.ОСАТЕ 740ОЕ() 4 тоос[Т) - в 5 !еа7'[в] - РАЬЗЕ 6 п[в) — О 7 с1 [в) — т 8 В ТКЕЕ БРЫТ СНП.О(в, 1, т) 9 В Ткее !Нзект )чОНГБ1ь(в, Й) !О е!ве В Ткее 1хзект !чонРОы.(т,!с) Строки 3-9 предназначены для случая, когда заполнен корень дерева: при этом корень разбивается и новый узел в (у которого два дочерних узла) становится новым корнем В-дерева.
Разбиение корня — единственный путь увеличения высоты В-дерева. На рис. 18.6 проиллюстрирован такой процесс разбиения корневого узла. В отличие аг бинарных деревьев поиска, у В-деревьев высота увеличивается "'сверху", а не "снизу". Завершается процедура вызовом другой про- Глава 18. В-деревья 527 мс~ ! Т! о о~ 1Т,' А,д,Г ХХ,Г.У Р.~ , ---;-+-', -, '-) — -) — ', Т ! с! Г„Т; Т„Г; Т! Г,Г,Г;Т, Т,,Т,ТсТ, Рис. 18.6.
Разбиение корня с $ = 4 цедуры — В Ткее 1нзект Хоыг~л.!., которая выполняет вставку ключа lс в дерево с незаполненным корнем. Данная процедура при необходимости рекурсивно спускается вниз по дереву, причем каждый узел, в который она входит, является незаполненным, что обеспечивается (при необходимости) вызовом процедуры В ТКЕЕ БР$.!Т СНП.Р. Вспомогательная процедура В Ткее 1нзект Хслчгин. вставляет ключ 1с в узел х, который должен быть незаполненным при вызове процедуры. Операции В Ткее 1нзект и В Ткее 1!сзект Хслсг!лл, гарантируют что это условие незаполненности будет выполнено. В Ткее 1хзект ХО!чР!л.ь(х, !с) 1 4 — п[х] 2 Ы 1еаГ'[х] 3 Феп ъййе г > 1 и 1с < 7сеу;[х] 4 йо ассу!+! [х] — Йеус[х) 5 4 -4 — 1 6 7сеус+! [х] — 7с 7 п[х) — п[х) + 1 8 13!зк %к!Те(х) 9 е1ае зтййе з > 1 и 1с < 7сеус[х] 1О Йо 4+- з — 1 11 1 -4+1 12 13!Бк кеА1з(сс[х)) 13 Ы п[с;[х]] = 21 — 1 14 1Ьеп В Ткее Балт Снп.!з(х,з,с,[х)) 15 11 lс > 7сеус[х] 16 тЬеп 4+-1+ 1 17 В Ткее 1нзект ХонР!!Щс;[х], к) 528 Часть Ч.
Сложные структуры данных Процедура В Ткее 1ызккт Хонды. работает следующим образом. Строки 3-8 обрабатывают случай, когда х является листом; при этом ключ )с просто вставляется в данный лист. Если же х не является листом, то мы должны вставить Й в подходящий лист в поддереве, корнем которого является внутренний узел х. В этом случае строки 9 — 11 определяют дочерний узел х, в который спустится рекурсия. В строке 13 проверяется, не заполнен ли этот дочерний узел, и если он заполнен, то вызывается процедура В Ткен Бкыт Сн~ьо, которая разбивает его на два незаполненных узла, а строки 15-16 определяют, в какой ю двух получившихся в результате разбиения узлов должна спуститься рекурсия.
(Обратите внимание, что в строке 16 после увеличения 1 операция чтения с диска не нужна, поскольку процедура рекурсивно спускается в узел, толью что созданный процедурой В Тккк Бкыт Снп.о.) Строки 13-16 гарантируют, что процедура ниюгда не столкнется с заполненным узлом. Строка 17 рекурсивно вызывает процедуру В Ткал 1нзЕкт Хонго~.~ для вставки к в соответствующее поддерево. На рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
