Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 110
Текст из файла (страница 110)
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 о Исхо,иксззссзо . Й88й б~ молельне г юг си ~ ЛВ Гс о з к оулсс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. Стеки во вторичной памяти Рассмотрим реализацию стека в компьютере с небольшой оперативной памятью, но относительно большим дисковым пространством.
Поддерживаемые стеком операции Ризи и Ров должны работать со значениями, представляющими отдельные машинные слова. Стек должен иметь возможность роста до размеров, существенно превышающих размер оперативной памяти, так что его большая часть должна храниться на диске. Простая, но неэффективная реализация стека хранит его весь на диске. В памяти поддерживается только указатель стека, который представляет собой дисковый адрес элемента на вершине стека.
Если указатель имеет значение р, элемент на вершине стека является (р пюс1 т)-м словом на странице 1р/ууз), где т — количество слов в одной странице. 534 Часть Ч. Сложные структуры данных Для реализации операции Рази мы увеличиваем указатель стека, счятываем в оперативную память с диска соответствующую страницу, хо. пируем вносимый в стек элемент в соответствующее место на странице и записываем страницу обратно на диск. Реализация операции Рор аналогична реализации операции Рьян.
Мы уменьшаем указатель стещ считываем в оперативную память с диска соответствующую страницу и возвращаем элемент на вершине стека. Нет необходимости записывать страницу назад на диск, поскольку она не была модифицирована. Поскольку дисковые операции достаточно дорогие в смысле времени их выполнения, мы учитываем при любой реализации стека две стоимости: общее количество обращений к диску и необходимое процессорное время.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
