начальное дерево F удалена: случай 1 М удалена: случай 2а G удалена: случай 26

Рис. 19.8 Удаление элемента из Б-дерева. Для этого Б-дерева минимальная степень равна 3, т. е. вершина содержит не менее 2 элементов. Светлые вершины были изменены при удалении, (а) Б-дерево рисунка 19.7 (е). (б) Случай 1: удаление буквы F из листа, (в) Удаление буквы М. Это случай 2а: буква-предшественница Г перешла на её место, (г) Удаление буквы G. Это случай 2в: сначала G отправили вниз, где образовался лист DEGJK, из которого G и удалили (случай 1). (д) Удаление буквы D. Это случай 36: мы не можем рекурсивно обработать вершину С Г, в которой всего два элемента, поэтому спускаем вниз Р и получаем вершину СГРТХ. После этого удаляем D из листа (случай 1). (е) После удаления D корень стал пустым и мы удалили его. Высота дерева уменьшилась на единицу, (е) Удалили В. Это случай За: С спустили на место В, а Е подняли на место С.

Задачи к главе 19

397

D удалена: случай 36 уменьшение высоты дерева В удалена: случай За

б). Пусть оба соседа вершины сг-[ж] содержат по t - 1 элементу. Тогда объединим вершину сг-[ж] с одним из соседей (как в случае 2в). При этом ключ, разделявший их в вершине ж, станет ключом-медианой новой вершины.

Описанная процедура требует более одного прохода только в случаях 2а и 26 (когда она заменяет удаляемый элемент его предшественником или последователем). Заметим, что это происходит, только если требуется удалить элемент из внутренней вершины. Большинство вершин Б-дерева - листья, так что эти случаи будут редкими.

Хотя процедура выглядит запутанно, она требует всего 0(h) обращений к диску для Б-дерева высоты h. (Между двумя рекурсивными вызовами выполняется 0(1) команд Disk-Read и Disk-Write). Вычисления требуют времени 0(th) = 0(tlogth).

Упражнения

19.3-1 Показать результат удаления вершин С, Р и V (в указанном порядке) из дерева рис. 19.8 (f).

19.3-2 Написать процедуру B-Tree-Delete.

Задачи

19-1 Стеки на диске

Представим себе, что мы хотим реализовать стек на машине с небольшой оперативной памятью и большим жестким диском (стек

не помещается в оперативную память, и должен по большей части храниться на диске).

При простейшей (но неэффективной) реализации стека на диске хранится всё, кроме переменной р (указатель стека), которая определяет место вершины стека на диске таким образом: вершиной будет (р mod то)-ый элемент [р/т\-го сектора диска (то - размер сектора).

Чтобы добавить элемент в стек, мы читаем соответствующий сектор, на нужное место помещаем новый элемент, увеличиваем значения указателя на единицу и снова записываем сектор на диск. Аналогично реализуется операция удаления элемента из стека. (Мы читаем сектор с диска и уменьшаем на единицу значение указателя. Так как сектор не менялся, то записывать его на диск не нужно.)

Будем учитывать количество обращений к диску, а также время вычислений, при подсчете которого каждое обращение к диску считается требующим О(то) единиц времени.

а.Сколько обращений к диску требуется в худшем случае для п операций со стеком при этой реализации? Чему равно общее время? (Здесь и далее требуется ответ в терминах то и п.)

Рассмотрим другую реализацию стека, при которой один сектор целиком хранится в памяти. (Кроме того, нам требуется помнить номер хранимого сектора.) По мере необходимости мы будем возвращать этот сектор на диск и считывать новый. Если нужный сектор уже находится в памяти, то обращаться к диску не нужно.

б.Сколько обращений к диску требуется для добавления п элементов в стек (в худшем случае)? Чему равно время вычислений?

в.Сколько обращений к диску требуется в худшем случае для п операций со стеком? Чему равно время вычислений?

Существует более эффективная реализация, при которой в оперативной памяти хранятся два сектора (и ещё несколько чисел).

г.Как сделать так, чтобы каждая операция требовала (при амортизационном анализе) 0(1/то) обращений к диску и времени 0(1)?

19-2 Объединение и разделение 2-3-4 деревьев

Операция объединения (join) получает на входе два множества S и S" и элемент ж, для которых кеу[х] < кеу[х] < кеу[х"] при всех ж £ S и ж" £ S". Ее результатом является множество S = S U {ж} U S". Разделение (split) - операция, обратная объединению. Она получает на входе множество S и элемент ж £ S и создаёт два других множества S и S", состоящих соответственно из меньших и из больших ж элементов множества S. В этой задаче требуется реализовать эти операции для 2-3-4 деревьев. Для удобства будем считать, что элементы состоят только из ключей, и все