|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[129] начальное дерево 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 деревьев. Для удобства будем считать, что элементы состоят только из ключей, и все |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||