Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 117
Текст из файла (страница 117)
В строке 10 обновляется количество ключей в у. И наконец строки 11 — 17 вставляют г в качестве дочернего узла х, перенося медиану из у в х для разделения у и г, и обновляют количество ключей в х. В строках 18-20 выполняется запись на диск всех модифицированных страниц. Процессорное время работы процедуры равно В(1) из-за циклов в строках 5 и 6, а также 8 и 9 (прочие циклы выполняют О(1) итераций). Процедура выполняет 0(1) дисковых операций.
Вепеавка ключа в В-дерево за один проход Вставка ключа и в В-дерево Т высотой А выполняется за один нисходящий проход по дереву, требующий 0(Ь) обращений к диску. Необходимое процессорное время составляет 0(и) = О(! 1о8, п). процедура В-ткее-1нзект использует процедуру В-Ткее-ЯРС1Т-Сн1СР для гарантии того, что рекурсия никогда не столкнется с заполненным узлом, В-Ткее-!Нзект (Т, (с) 1 г = Т. гоо1 2 Ы г. и == 21 — 1 3 в = А1Л.ОСАТЕ-ХОРЕ() 4 Т.гоо1 = в 5 и.!еа! = РАезе б з.п=О 7 з.с1 =г 8 В-Ткее-ЯРС!т-Сн11лэ(в, 1) 9 В-ТКЕЕ-1НБЕКТ-ХОХР15ЕЕ(в, 1с) 10 е!ае В-ТКЕЕ-1НБЕКТ-ХОНРШЛ. (г, й) Строки 3 — 9 обрабатывают случай, когда заполнен корень дерева г: при этом корень разбивается и новый узел в (у которого два дочерних узла) становится новым корнем В-дерева.
Высота В-дерева может увеличиваться только при разбиении корня. На рис. 18.6 проиллюстрирован такой процесс разбиения корневого узла. В отличие от бинарных деревьев поиска, высота В-деревьев увеличивается "сверху", а не "снизу". Завершается процедура вызовом другой процедуры— В-Ткее-1нзект-ХОну~лл., — которая выполняет вставку ключа Е в дерево с незаполненным корневым узлом. Данная процедура при необходимости рекурсивно спускается вниз по дереву, причем каждый узел, в который она входит, является незаполненным, что обеспечивается (при необходимости) вызовом процедуры В-Ткее-ЯРС1Т-Снп.Р. Вспомогательная рекурсивная процедура В-Ткее-!Нзект-Хонупее вставляет ключ /с в узел х, который при вызове процедуры должен быть незаполненным.
Операции В-Ткее-1нзект и В-Ткее-1нзект-Хонрпее гарантируют, что это условие незаполненности будет выполнено. Глава !д и-деревья Т. гооз г зал д,:Ё"' Й.'. о .,'Ф; у; ~ ! Т$ Тз Тз Тл Тз Ть Ут Тз Т~ Тз Тз Тл Тз Тг Т7 Тз Рис. 1Я.б. Разбиение корня при 1 = 4. Корневой узел г разбивается на два, и создастся новый корневой узел я. Новый корень содержит медианный клим г, а две половины г становятся его дочерними узлами. Высота В-дерева при разбиении корня увеличивается на едннипу.
В-ТКЕЕ-11тБЕКТ-МОХР1ЛЛ. (х, й) ! з=хп 2 !Т х. 1еаУ 3 жййе з > 1 и и < х.lсеуз х. Йеуз+1 — — х. Йеуз 5 з=з — 1 б х. )сеуз+1 — — й 7 х.п = х.п+ 1 8 Р1БК-зт'К1ТЕ(х) 9 е!яе зч!11!е з > 1 и и < х.кеу; 10 з=з — 1 11 с=с+1 12 01ЕК-КЕАО(х.с;) !3 !Рх.соп == 2! — 1 14 В-ТКЕЕ-БР1ЛТ-СНПЛ) (х, з) 15 !з Й > х.деус 16 а=с+1 !7 В-Ткее-11тэект-ХО1чрзззл.(х.с;,к) Процедура В-Ткее-1нэект-Хоннлл. работает следующим образом. Строки 3-8 обрабатывают случай, когда х является листом; при этом ключ и просто вставляется в данный лист.
Если же х не является листом, то необходимо вставить 1с в подходящий лист в поддереве, корнем которого является внутренний узел х. В этом случае строки 9 — 11 определяют дочерний узел х, в который спустится рекурсия. В строке 13 проверяется, не заполнен ли этот дочерний узел, и если он заполнен, то в строке 14 вызывается процедура В-Ткее-БР1лт-Снп О, которая разбивает его на два незаполненных узла, а строки 15 и 16 определяют, в каюй нз двух полученных в результате разбиения узлов должна спуститься рекурсия. (Обратите внимание, что в строке 16 после увеличения з операция чтения с диска 11!як-Кедп(х. с;) не нужна, поскольку процедура рекурсивно спускается в узел, толью что созданный процедурой В-Ткее-Брзлт-Снп О.) Строки 13-16 гарантируют, что процедура никогда не столкнется с заполненным узлом. Затем строка 17 Часть К Сложные струннрры оанньи (а) Исхоююе дерево (б) ВставленоВ (в) Вставлено Д (г) Встаалено1 ай~) й ьйй С Р)Ы„! ~ А Е „' '! Р Е л" Рнс.
18.7. Вставка ключей в В-дерево с минимальной степенью Г = 3, так что узел может содержать не более пяти ключей. Узлы, модифицированные в процессе вставки, вьщелены светлой штриховюй, (а) Июккщое дерево лля приведенного примера. (6) Результат вставки В в исходное дерево. Это простая вставка в лист. (в) Результат вставки Я в предыдущее дерево. Узел ВЯТКУ разбивается на два узла, содержащих ВЯ и (!Ъ', ключ Т переноситси вверх в юрень, а Я вставляется в левую половину (узел ВЯ). (г) Результат вставки Е в предыдущее дерево.
Корень, будучи заполненным, разбиааепж, и высота В-дерева увеличщается на единицу. Затем Е вставляется в лист, содержащий .Улз. (д) Результат вставки Е в предьиущее дерево. Узел АВСРЕ разбивается перед вставкой Е в правую половину (узел РЕ). рекурсивно вызывает процедуру В-Ткее-1)чзект-Хо)чр(лл. для вставки Ь в соответствующее поддерево. На рис. 18.7 проиллюстрированы различные ситуации, возникающие при вставке в В-дерево. Количество обращений к диску, выполняемых процедурой В-Ткее-1)чзект для В-дерева высотой Ь, составляет О(Ь), поскольку между вызовами В-Ткее- 1)чзект-ХО)чр(л.е выполняется только О(1) операций 1)!Бк-йеАР и 1)!Бк-Жн!Те. Необходимое процессорное время равно О((Ь) = О(11оя, и). Поскольку в про- 535 Раааа! В.
В-деревья цедуре В-Ткее-1неект-)ь(океиье использована оконечная рекурсия, ее можно реализовать итеративно с помощью цикла ьвййе, тем самым демонстрируя, что количество страниц, которые должны находиться в оперативной памяти, в любой момент времени равно 0(1). Упражнения иг1 Покажите результат вставки ключей Г, Я, Я, К, С, Ь, Н, Т, У, И', М, Я, )У, Р, А, В, Х, У, 12, Е, Е в указанном порядке в изначально пустое В-дерево с минимальной степенью 2.
Изобразите только конфигурации дерева непосредственно перед выполнением разбиения и окончательный вид дерева. иг.г Поясните, при каких условиях могут выполняться излишние операции Пшкйелп и?Изк-%к!те в процессе работы процедуры В-Ткее-1мзект (если таковые могут иметь место). Под излишней операцией чтения подразумевается чтение страницы, уже находящейся в оперативной памяти, а под излишней записью — запись на диск информации, идентичной уже имеющейся там.
1В.2.3 Как найти минимальный ключ в В-дереве? Как найти элемент В-дерева, предшествующий данному ключу? И24 * Предположим, что ключи (1, 2,..., п) вставлены в пустое В-дерево с минимальной степенью 2. Сколью узлов будет иметь полученное в результате В-дерево? И2.5 Поскольку листья не содержат указателей на дочерние узлы, в них можно разместить больше ключей, чем во внутренних узлах при том же размере дисковой страницы. Покажите, как следует изменить процедуры создания В-дерева и вставки в него для работы с таким видоизмененным В-деревом. И2.6 Предполвким, что линейный поиск в узле в процедуре В-Ткее-беяксн заменен бинарным поиском, Покажите, что прн этом процессорное время, необходимое для выполнения процедуры В-Ткее-белксн, равно 0(1к и) (и не зависит от г).
И2. 7 Предположим, что дисковое аппаратное обеспечение позволяет произвольно выбирать размер дисковой страницы, но время, необходимое для чтения дисковой страницы, равно а + сь', где а и Ь вЂ” определенные константы, а 1 — минимальная степень В-дерева, использующего страницу данного размера. Как следует вы- ьласть и Сложные структуры данных 53б брать 1, чтобы (приближенно) минимизировать время поиска в В-дереве? Оцените оптимальное значение 1 для а = 5 мс и 5 = 10 мкс.
18.3. Удаление ключа из В-дерева Удаление ключа из В-дерева, хотя и аналогично вставке, представляет собой более сложную задачу. Это связано с тем, что ключ может быть удален из любого узла, а не только из листа, а удаление из внутреннего узла требует определенной перестройки дочерних узлов. Как и в случае вставки,мы должны обеспечить сохранение свойств В-дерева при выполнении операции удаления. Аналогично тому, как мы обеспечивали отсутствие переполнения при вставке нового ключа, нам предстоит обеспечивать условие, чтобы узел не становился слишком мало заполненным в процессе удаления ключа (за исключением корневого узла, который может иметь менее 1 — 1 ключей). Так же, как алгоритму вставки может потребоваться возврат, если узел на пути вставки ключа заполнен, так и алгоритму удаления может потребоваться возврат, если узел (не корневой) на пути вставки ключа имеет минимально допустимое количество ключей.
Итак, пусть процедура В-Ткее-Рееете должна удалить ключ (с из поддерева, корнем которого является узел т. Эта процедура разработана таким образом, что при ее рекурсивном вызове для узла х гарантировано наличие в этом узле по меньшей мере 1 ключей. Заметим, что это условие требует наличия в узле количества ключей, на один больше минимально требуемого свойствами В-дерева, так что иногда ключ может быть перемещен в дочерний узел перед тем, как рекурсия опустится в этот дочерний узел.
Такое ужесточение свойства В-дерева (наличие "запасного" ключа) дает нам возможность выполнить удаление ключа за один нисходящий проход по дереву (с единственным исключением, которое будет пояснено позже). Следует также учесть, что если корень дерева х становится внутренним узлом, не содержащим ни одного ключа (такая ситуация может возникнуть в рассматриваемых ниже случаях 2, (в) и 3, (б) на с.
537), то узел т удаляется, а его единственный дочерний узел х.с1 становится новым корнем дерева (при этом уменьшается высота В-дерева и сохраняется его свойство, требующее, чтобы корневой узел непустого дерева содержал как минимум один ключ). Вместо того чтобы представить вам полный псевдокод процедуры удаления узла из В-дерева, мы просто набросаем последовательность выполняемых действий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
