Алгоритмы - построение и анализ (1021735), страница 107
Текст из файла (страница 107)
Опишите структуру данных, которая получится, если в красно-черном дереве каждый черный узел поглотит красные дочерние узлы, а их потомки станут дочерними узлами этого черного узла. 18.2 Основные операции с В-деревьями В этом разделе мы более подробно рассмотрим операции В Тккп Яплксн, В Ткни Скнлтн и В Ткнп 1нзнкт. При рассмотрении этих операций мы примем следующие соглашения.
° Корень В-дерева всегда находится в оперативной памяти, так что операция 01зк Кнлп для чтения юрневого узла не нужна; однако при изменении корневого узла требуется выполнение операции Р|зк %итп, сохраняющей внесенные изменения на диске. ° Все узлы, передаваемые в качестве параметров, уже считаны с диска. Все представленные здесь процедуры выполняются за один нисходяший проход по дереву. Поиск в В-дереве Поиск в В-дереве очень похож на поиск в бинарном дереве поиска, но с тем отличием, что если в бинарном дереве поиска мы выбирали один из двух путей, то здесь предстоит сделать выбор из большего количества альтернатив, зависящего от того, сколько дочерних узлов имеется у текущего узла.
Точнее, в каждом внутреннем узле х нам предстоит выбрать один из и 1х) + 1 дочерних узлов. Операция В Ткпп Бплксн представляет собой естественное обобщение процедуры Ткпп Бплксн, определенной для бинарных деревьев поиска. В качестве параметров процедура В Ткпн Зклксн получает указатель на корневой узел Глава 18. В-дереаья 523 х поддерева и ключ /с, который следует найти в этом поддереве.
Таким образом, вызов верхнего уровня для поиска во всем дереве имеет вид В ТКЕЕ БеАксн(гоос [т), /с). если ключ /с имеется в В-дереве, процедура В ткее БеАксн вернет упорллоченную пару (у,1), состоящую из узла у и индекса г, такого что Леу, [у) = /с. В противном случае процедура вернет значение нп.. В ТКЕЕ БЕАКСН(х, /с) 1 г< — 1 2 зтЫ1е г < п[х] и /с > Йеус[х] 3 с1ог+ — 1+1 4 Н г < п[х] и /с = /сеу;[х] 5 гиен ге$цгп (х,1) б П 1еа/'[х) 7 Ф/зев гегигп нп.
8 е!ае 13!Як ВеАп(с,[х]) 9 ге1пгв В Ткее БеАксн(с;[х),Л) В строках 1-3 выполняется линейный поиск наименьшего индекса г, такого что /с < /сеу; [х] (иначе 1 присваивается значение и [х]+ 1). В строках 4-5 проверяется, не найден ли ключ в текущем узле, и если он найден, то выполняется его возврат. В строках 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 ~ Т $», И 8, Т, Л' 1 "! '1'., 1, 1» Т, 1'„Т', 1' ТТ Я И' Р У Л,~ ~Т1Т И Г Т, Т,, 1, Т, 1, 1» 1; Т., Рис. 18.5. Разбиение узла с ! = 4 В Ткее Билт Снп$»(х,г,у) 1 г — АЫ.ОСАТЕ 74ОПЕ() 2 1е У[я) 1 ~Ь] 3 п[х] ~ — $ — 1 4 $ог 7' » — 1 $о $ — 1 5»$о Иеуу[з) — 1сеу +,[у) 6 $Г по$1еаТ'[у) 7 $$»еп $ог 1 — 1 $о $ 8 !$о су[а] - с ж![у) 9 п[у) — $ — 1 10 $ог 1' — п[х] + 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нзект Хслчгин.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
