Алгоритмы - построение и анализ (1021735), страница 108
Текст из файла (страница 108)
вставляет ключ 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 и й < 7сеус[х] 1О Йо 4+- з — 1 11 1 -4+1 12 13!Бк кеА!з(сс[х)) 13 Ы п[с;[х]] = 21 — 1 14 !Ьеп В Ткее ЯРе!т Снп.!з(х,з,с,[х)) 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нзЕкт Хонго~.~ для вставки к в соответствующее поддерево. На рис. 18.7 проиллюстрированы различные ситуации, возникающие при вставке в В-дерево. Количество обращений к диску, выполняемых процедурой В Тким 1нзккт для В-дерева высотой Ь, составляет 0(л), поскольку между вызовами В Ткек 1нБект Хоннлл.
выполняется только 0 (1) операций 131зк Ккло и 131зк тук1тк Необходимое процессорное время равно 0(гй) = 0(г1об,п). Поскольку в В Ткек 1нзект Хонгоы. использована оконечная рекурсия, ее можно реализовать итеративно с помощью цикла и Ы1е, наглядно показывающего, что количество страниц, которые должны находиться в оперативной памяти, в любой момент времени равно 0 (1). Упражнения 18.2-1. Покажите результат вставки ключей Г, Я, Я, К, С, Ь, Н, Т, 1', И', М, Я, Ф, Р, А, В, Х, У, Р, Я, Е в указанном порядке в изначально пустое В-дерево с минимальной степенью 2. Нарисуйте только конфигурации дерева непосредственно перед выполнением разбиения и оюнчательный вид дерева.
18.2-2. Поясните, при каких условиях могут выполняться излишние операции В~як Кело и Р1зк %катк в процессе работы процедуры В Тккк 1нзккт (если таковые могут иметь место). Под излишней операцией чтения подразумевается чтение страницы, уже находящейся в оперативной памяти, а под излишней записью — запись на диск информации, идентичной уже имеющейся там. 18.2-3. Как найти минимальный ключ в В-дереве? Как найти элемент В-дерева, предшествующий данному? Глава 18. В-деревья 529 а) Нсаоавосвсгсво В) Вставка В )Х В С ВГ в~ Гк савка с) ),а г.а~~ В~1 с) Вставка ).
1 к й'-'-,'- ~,в~;;8. с) Всмвка ) ) с 6 и Рис. 18.7. Вставка ключей в В-дерево с минимальной степенью 3. Узлы, изменяемые в процессе вставки, выделены светлым цветом * 18.2-4. Предположим, что ключи (1, 2,..., ак1 вставлены в пустое В-дерево с минимальной степенью 2. Сколько узлов будет иметь получившееся в результате В-деревень 18.2-5. Поскольку листья не содержат указателей на дочерние узлы, в них можно разместить большее количество ключей, чем во внутренних узлах при том же размере дисковой страницы. Покажите, как надо изменить процедуры создания В-дерева и вставки в него для работы с таким видоизмененным В-деревом. 530 Часть Ч.
Сложные структуры данных 18.2-6. Предположим, что линейный поиск в узле в процедуре В Тквн БиАксн заменен бинарным поиском. Покажите, что при этом процессорное врь мя, необходимое для выполнения процедуры В Ткев Яилксн, равно О (18 и) (и не зависит от 1). 18.2-7. Предположим, что дисювое аппаратное обеспечение позволяет произвольно выбирать размер дисковой страницы, но время, необходимое для чтения дисювой страницы, равно а + Ьт, где а и Ь вЂ” определенные ков. станты, а т — минимальная степень В-дерева, использующего страницу данного размера. Каким образом выбрать 1, чтобы (приближенно) минимизировать время поиска в В-дереве? Оцените оптимальное значение 1 для а = 5 мс и Ь = 10 мкс.
18.3 Удаление ключа из В-дерева Удаление ключа из В-дерева, хотя и аналогично вставке, представляет собой более сложную задачу. Это связано с тем, что ключ может быть удален из любого узла, а не толью из листа, а удаление из внутреннего узла требует определенной перестройки дочерних узлов. Как и в случае вставки, мы должны обеспечить, чтобы при выполнении операции удаления не были нарушены свойства В-дерева. Аналогично тому, как мы имели возможность убедиться, что узлы не слишком сильно заполнены для вставки нового ключа, нам предстоит убедиться, что узел не становится слишком мало заполнен в процессе удаления ключа (за исключением корневого узла, который может иметь менее т — 1 ключей, хотя и не может иметь более 21 — 1 ключей).
Итак, пусть процедура В Твен Рн.вте должна удалить ключ к из поддерева, корнем юторого является узел х. Эта процедура разработана таким образом, что при ее рекурсивном вызове для узла х гарантировано наличие в этом узле по крайней мере т ключей. Это условие требует наличия в узле большего количества ключей, чем минимальное в обычном В-дереве, так что иногда ключ может быть перемещен в дочерний узел перед тем, как рекурсия обратится к этому дочернему узлу. Такое ужесточение свойства В-дерева (наличие "запасного" ключа) дает нам возможность выполнить удаление ключа за один нисходящий проход по дереву (с единственным исключением, которое будет пояснено позже). Следует также учесть, что если корень дерева х становится внутренним узлом, не содержащим ни одного ключа (такая ситуация может возникнуть в рассматриваемых ниже случаях 2в и 36), то узел х удаляется, а его единственный дочерний узел с1 ~х) становится новым корнем дерева (при этом уменьшается высота В-дерева и сохраняется его свойство, требующее, чтобы корневой узел непустого дерева содержал как минимум один ключ).
Глава 18. В-деревья 531 Вместо того чтобы представить вам полный псевдокод процедуры удаления узла из В-дерева, мы просто набросаем последовательность выполняемых действий. На рис. 18.8 показаны различные возникающие при этом ситуации. 1. Если узел Й находится в узле х и х является листом — удаляем Й из х. 2. Если узел Й находится в узле х и х является внутренним узлом, выполняем следующие действия. а) Если дочерний по отношению к х узел у, предшествующий ключу Й в узле х, содержит не менее Ф ключей, то находим Й' — предшественника Й в поддереве, корнем которого является у. Рекурсивно удаляем Й' и заменяем Й в х ключом Й'.
(Поиск ключа Й' и удаление его можно выполнить в процессе одного нисходящего прохода.) б) Ситуация, симметричная ситуации вс если дочерний по отношению к х узел х, следующий за ключом Й в узле х, содержит не менее г ключей, то находим Й' — следующий за Й ключ в поддереве, корнем которого является х. Рекурсивно удаляем Й' и заменяем Й в х ключом Й'. (Поиск ключа Й' и удаление его можно выполнить в процессе одного нисходящего прохода.) в) В противном случае, если и у, и х содержат по г — 1 ключей, вносим Й и все ключи х в у (при этом из х удаляется Й и указатель на х, а узел у после этого содержит 2г — 1 ключей), а затем освобождаем г и рекурсивно удаляем Й из у.
3. Если ключ Й отсутствует во внутреннем узле х, находим корень с; [х] поддерева, которое должно содержать Й (если таковой ключ имеется в данном В-дереве). Если с; [х] содержит только г — 1 ключей, выполняем шаг За или Зб для того, чтобы гарантировать, что далее мы переходим в узел, содержащий как минимум 1 ключей. Затем мы рекурсивно удаляем Й из поддерева с корнем с; [х]. а) Если с; [х] содержит только г — 1 ключей, но при этом один из ее непосредственных соседей (под которым мы понимаем дочерний по отношению к х узел, отделенный от рассматриваемого ровно одним ключом-разделителем) содержит как минимум г ключей, передадим в с; [х] ключ-разделитель между данным узлом и его непосредственным соседом из х, на его место поместим крайний ключ из соседнего узла и перенесем соответствующий указатель из соседнего узла в с; [х]. б) Если и с; [х] и оба его непосредственных соседа содержат по г — 1 ключей, объединим с; [х] с одним из его соседей (при этом бывший ключ-разделитель из х станет медианой нового узла).
Часть Ч. Сложные структуры данньж 532 н Исхо,'икс ззссзо б~ молельне г юг си ~ Щи чтя. ' ~ д е Гс а з к оулсс1иец сч ивзв Ж фу', и в т а я~ и Рис. 18.8. Удаление узла из В-дерева с минимальной степенью 3. Модифици- русмые узлы показаны светлым цветом Поскольку большинство ключей в В-дереве находится в листьях, можно ожидать, что на практике чаще всего удаления будут выполняться из листьев.
Процедура В Ткне Рн.нтн в этом случае выполняется за один нисходящий проход по дереву, без возвратов. Однако при удалении ключа из внутреннего узла процедуре может потребоваться возврат к узлу, ключ из которого был удален и замешен его предшественником или последующим за ним ключом (случаи 2а и 2б). Хотя описание процедуры выглядит достаточно запутанным, она требует всего лишь 0(Ь) дисковых операций для дерева высотой й, поскольку между рекурсивными вызовами процедуры выполняется только 0(1) вызовов процедур Глава 18.
В-дереаья 533 л) узюсные О, случал уз г- -- — 1 — — —-- 1г 1 Р гх Гя у х ,г! уысньшлие ~ьиупуы о уилслис В: ~лузгай и ~ Г т Р г х з с' Гу к 13вк Кнлп или 131зк %н~тн. Необходимое процессорное время составляет 0(ГЬ) = 0(11об,п). Упражнения 18.3-1. Изобразите результат удаления ключей С, Р и 1' (в указанном порядке) из В-дерева, приведенного на рис. 18.8е. 18.3-2. Напишите псевдокод процедуры В Ткни Энг.нтн. Задачи 18-1. Стеки во вторичной памяти Рассмотрим реализацию стека в компьютере с небольшой оперативной памятью, но относительно большим дисковым пространством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
