Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 118
Текст из файла (страница 118)
На рис. 18.8 показаны возникающие при удалении ключа из В-дерева ситуации. 1. Если ключ й находится в узле х и т является листом, удаляем ключ (с изх. 2. Если ключ й находится в узле х и х является внутренним узлом, делаем следующее. а) Если дочерний по отношению к х узел у, предшествующий ключу )с в узле х, содержит не менее 1 ключей, то находим Й' — предшественника (с в поддереве, корнем которого является у.
Рекурсивно удаляем Й' и заменяем (с 537 Глава И В-деревья в х ключом lс'. (Поиск ключа lс' и его удаление можно выполнить за один нисходящий цроход.) б) Если у имеет менее С ключей, то симметрично обращаемся к дочернему по отношению к х узлу х, который следует за ключом Й в узле х. Если г содержит не менее г ключей, то находим Й' — следующий за к ключ в поддереве, корнем которого является г. Рекурсивно удаляем Й' и заменяем lс в х ключом к'.
(Поиск ключа 1с' и его удаление можно выполнить за один нисходящий проход.) в) В противном случае, если и у, и х содержат по 1 — 1 ключей, вносим /с и все ключи з в у (при этом из х удаляются и Й, и указатель на я, а узел у после этого содержит 2с — 1 ключей), а затем освобождаем г и рекурсивно удаляем lс из у. 3. Если ключ (с отсутствует во внутреннем узле х, находим корень х.с, поддерева, которое должно содержать й (если таковой ключ имеется в данном В-дереве). Если х. с; содержит только 1 — 1 ключей, выполняем и.
3, (а) или (б) для того, чтобы гарантировать, что далее мы переходим в узел, содержащий как минимум 1 ключей, Затем мы рекурсивно удаляем к из соответствующего дочернего по отношению к х узла. а) Если х.с, имеет только 1 — 1 ключей, но при этом один нз его непосредственных соседей (под которым мы понимаем дочерний по отношению к х узел, отделенный от рассматриваемого ровно одним ключом-разделителем) содержит как минимум г ключей, передадим в х. с; ключ-разделитель между данным узлом и его непосредственным соседом из х, на его место поместим крайний ключ из соседнего узла и перенесем соответствующий указатель из соседнего узла ах.с;. б) Если и х.с„ и оба его непосредственных соседа содержат по 1 — 1 ключей, объединим х.
с; с одним из его соседей (при этом бывший ключ-разделитель из х будет перенесен вниз и станет медианой нового узла). Поскольку большинство ключей в В-дереве находится в листьях, можно ожидать, что на практике чаще всего удаления будут выполняться иэ листьев. Процедура В-Ткее-)3е~.ете в этом случае выполняется за один нисходящий проход по дереву, без возвратов. Однако при удалении ключа из внутреннего узла процедуре может потребоваться возврат к узлу, ключ из которого был удален, чтобы заменить ключ его предшественником или преемником (случаи 2, (а) и (6)).
Хотя описание процедуры выглядит достаточно запутанным, она требует всего лишь 0(сь) дисковых операций для В-дерева высотой 6, поскольку между рекурсивными вызовами процедуры выполняется только 0(1) вызовов процедур Пшк-Кеяп или Ршк-%к~те.
Необходимое процессорное время составляет 0(И) = 0(11оксп). Часть Г Сложные структуры данных 118 (а) Исходное дерево (б) Удалено Р: случай 1 (в) УдапеноМ:случай2,(а) (г) Удалено С: случай 2, (в) с . Бз Ез'К', Рнс. 18.8. Удаление ключей ю В-дерева, Минимальная степень данного В-дерева 1 = 3, так что узел (отличный от корня) не мотет иметь меньше двух ключей. Моднфюпируемые узлы выделены светлой пприховкой.
(а) В-дерево, приведенное на рис. 18.7,(д). (6) Удаление Р. Реализуется случай 1: простое удаление ю листа (в) Удаление М. Реализуется случай 2,(а); предшественник М (В) перемещается вверх н занимает место М. (г) Удаление С. Реализуется случай 2, (в): С переносится вниз в узел РЕСНИК, а затем выполняекя удаление С из листа (случай 1).
Упршкненнн гв.зл Изобразите результат удаления ключей С, Р и $' (в указанном порядке) из В- дерева, приведенного иа рис. (8.8,(е). гвз.г Напишите псевдокод процедуры В-ТВВВ-г)Н.Втй. Глава !и В-деревья 539 (д) Ъ)пасло В: случай 3, (б) пСЕ Р Г Х) ~::,''~~Ф~",~"; 1 Е ',~ Дэ ~ ';~))~~~!~ ~~ (д') Уменьшениевысоты "'": '.') 'фф;„-'АД ~~~.'.Ф!::ыФ~щ э,"~,::„:'~~ (е) Улавенодй (.Е, А Р Г Х ~ Рнс.
18.8 (првдолпмние). (д) Удаление В. Реализуется случай 3,(б); рекурсия не монет опуститься в узел СЬ, поскольку в нем пивко два узла, так что мы опускаем Р и сливаем его с СЬ и ТХ с образованием СИ'ТХ; затем мы удаляем Р из листа (случай 1). (д') После (д) удаляется корень, и высота дерева уменьшается на единицу. (е) Удаление В. Реализуется случай 3,(а): С перемелмется для заполнения позиции В, а Е перемещается для заполнения позиции С.
Задачи 18.1. Стеки во вторичной памяти Рассмотрим реализацию стека в компьютере с небольшой оперативной памятью, но относительно большим дисковым пространспюм. Поддерживаемые стеком операции Р()зн и Рор должны работать со значениями, представляющими отдельные машинные слова. Стек должен иметь возможность роста до размеров, существенно превышающих размер оперативной памяти, так что его ббльшая часть должна храниться на диске. Простая, но неэффективная реапнзация стека хранит его весь на диске. В памяти поддерживается только указатель стека, который представляет собой дисковый адрес элемента на вершине стека.
Если указатель имеет значение р, элемент на вершине стека является (р шос) т)-м словом на странице ()э/т) на диске, где т — количество слов в одной странице. Для реализации операции Р()зн мы увеличиваем указатель стека, считываем в оперативную память с диска соответствующую страницу, копируем вносимый в стек элемент в соотвегствуюп(ее место на странице и записываем страницу обратно на диск. Реализация операции Рор аналогична реализации операции Р()зн.
Мы уменьшаем указатель стека, считываем в оперативную память с диска соответствующую страницу и возвращаем элемент на вершине стека. Пот необходимости записывать страницу на диск, поскольку она не была мо)шфицирована. 540 Часта и Слансные структуры данные Поскольку дисковые операции достаточно дорогие в смысле времени их выполнения, мы учитываем при любой реализации стека две стоимости: общее количество обращений к диску и необходимое процессорное время.
Будем считать, что дисковые операции со страницей размером гп слов требуют одного обращения к диску и процессорного времени 0(т). Чему в наихудшем случае равно асимптотическое количество обращений к диску при такой простейшей реализации стека? Чему равно требуемое процессорное время для и стековых операций? (Ваш ответ на этот и последующие вопросы данной задачи должен выражаться через т и и.) Теперь рассмотрим реализацию стека, при которой одна страница стека находится в оперативной памяти (кроме того, небольшое количество оперативной памяти используется для отслеживания того, какая именно страница находится в оперативной памяти в настоящее время).
Само собой разумеется, что мы можем выполнять стековые операции только в том случае, если соответствующая дисковая страница находится в оперативной памяти. При необходимости страница, находящаяся в данный момент в оперативной памяти, может быть записана на диск, а в память считана новая дисковая страница. Если нужная нам страница уже находится в оперативной памяти, то выполнение дисковых операций не требуется. б.
Чему в наихудшем случае равно количество необходимых обращений к диску для и операций Рабан? Чему равно соответствующее процессорное время? в. Чему в наихудшем случае равно количество необходимых обращений к диску для и стековых операций? Чему равно соответствующее процессорное время? Предположим, что стек реализован таким образом, что в оперативной памяти постоянно находятся две страницы (в дополнение к небольшому количеству оперативной памяти, которое используется для отслеживания того, какие именно страницы находятся в оперативной памяти в настоящее время). а Как следует управлять страницами стека, чтобы амортизированное количество обращений к диску для любой стековой операции составляло 0(1/т), а амортизированное процессорное время — О(1)? 18.3.
Объединение и разделение 2-3-деревьев Операция объединения ()о)п) получает два динамических массива, У и Я", и элемент х, такой, что для любых х' е У и хн е У' выполняется з'.Йеу < к./сеу < хн. (сеу. Операция объединения возвращает множество Я = У 0 (х) 0 У'. Операция разделения (зр1й) представляет собой обращение операции обьединения: для данного динамического множества Я и элемента я Е Я она создает множество У, содержащее все элементы из Я вЂ” (х), ключи которых меньше х.lсеу, и множество ян, состоящее из всех элементов я — (х), ключи которых больше х.кеу. В данной задаче мы рассматриваем реализацию этих операций над 2-3-4-деревьями. Для удобства полагаем, что элементы представляют собой ключи и что все ключи различны. Глава Га Лчдеревья 54! а Покажите, каким образом для каждого узла х поддерживать хранение в каждом узле 2-3-4-дерева в виде атрибута я.
ЬеьдЬг информации о высоте поддерева, корнем которого является узел х, чтобы это не повлияло на асимптотическое время выполнения операций поиска, вставки и удаления. б. Покажите, как реализовать операцию объединения. Для данных 2-3-4-деревьев Т' и ТЯ и ключа )с объединение должно выполняться за время 0(1+ ~6' — Ь" ~), где 6' и Ьа — значения высоты деревьев Т' и Та соответственно. в.
Рассмотрим простой путь р от корня 2-3-4-дерева Т к заданному ключу й, множество о' ключей Т, которые меньше )с, и множество ол ключей Т, которые больше Ь. Покажите, что р разбивает У на множество деревьев [То, Тз,..., Т' ] и множество ключей [азы 102,..., й,'„], где для ( = 1, 2,..., т мы имеем у < Ь,' ( 2 для любых ключей у б Т,', и г Е Т,'. Как связаны высоты Т,', и Т,'? На какие множества деревьев и ключей р разбивает Яа? * Покажите, как реализовать операцию разделения 2-3-4-дерева Т. Воспользуйтесь операцией объединения для того, чтобы собрать ключи из У в единое 2-3-4-дерево Т', а ключи из Ял — в единое 2-3-4-дерево Т".
Время работы операции разделения должно составлять 0(1я и), где и — количество ключей в Т. (Указание: при сложении стоимости операций объединения происходит сокращение членов телескопической суммы.) Заключительные замечания Сбалансированные деревья и В-деревья достаточно подробно рассмотрены в книгах Кнута (Кппбз) [210]з, Ахо (АЬо), Хопкрофта (Норсгой), Ульмана (1) Пшап) (5] и Седжвика (Бебйеьу)01с) [304]. Подробный обзор В-деревьев дан Комером (Сошег) (73].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
