|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[128] Рис. 19.7 Добавление элемента в Б-дерево, для которого t = 3, (вершина содержит до 5 ключей). Светлые вершины были изменены при добавлении, (а) Начальное дерево, (б) Добавили букву В (в неполный лист), (в) Добавление Q приводит к разделу вершины BSTUV на BS и UV, буква Т перешла в корень, после чего букву Q добавили к вершине BS. (г) В предыдущее дерево добавили L: корень был полной вершиной, поэтому его пришлось разделить на две и высота дерева увеличилась на единицу. Букву L вставили в лист J К. (д) В предыдущее дерево добавили F. Вершину ABCDE разделили на две и в половинку DE добавили F. Упражнения 19.2-1 Проследить, за добавлением в пустое Б-дерево элементов F, S, Q, К, С, L, Я, Г, V, W, М, R, N, Р, А, В, X, У, D, Z, Е в указанном порядке (нарисовать только состояния дерева перед разделением какой-то из вершин, а также последнее состояние) 19.2-2 Выяснить, исполняются ли лишние операции Disk-Read или Disk-Write при вызове процедуры B-Tree-Insert. (Лишняя операция Disk-Read читает сектор, уже загруженный в оперативную память. Лишняя операция Disk-Write сохраняет на диске не изменившийся сектор.) 19.2-3 Как найти минимальный элемент в Б-дереве? Как найти элемент Б-дерева, предшествующий данному элементу? 19.2-4* Ключи 1, 2,..., га добавляют по одному в пустое Б-дерево минимальной степени 2. Сколько вершин у полученного Б-дерева? 19.2-5 Так как у листьев нет указателей на детей, то в них может поместиться больше ключей, чем во внутренние вершины. Как будут выглядеть процедуры создания Б-дерева и добавления в него элемента, использующие это обстоятельство? 19.2-6 Заменим в процедуре B-Tree-Search линейный поиск двоичным. Показать, что тогда время вычислений для этой процедуры станет равным О (log га) (константа не зависит от tl). 19.2-7 Предположим, что мы можем сами выбрать размер сектора, причем время чтения сектора, вмещающего вершину Б-дерева степени t, будет а+Ы, где а и Ь - некоторые константы. Как следует выбрать t, чтобы уменьшить время поиска в Б-дереве? Оцените оптимальное значение t в случае а = 30 миллисекунд, Ь = 40 микросекунд. 19.3. Удаление элемента из Б-дерева Удаление элемента из Б-дерева (процедура B-Tree-Delete) происходит аналогично добавлению, хотя немного сложнее. Мы не будем приводить процедуру удаления полностью, а объясним, как она работает. Пусть нужно удалить ключ к из поддерева с корнем в вершине х. Наша процедура будет устроена так, что при каждом ее рекурсивном вызове вершина х содержит по меньшей мере t ключей, где t - минимальная степень Б-дерева. По правилам вершина Б-дерева должна содержать не меньше t - 1 ключа, так что в нашем случае имеется запасной ключ. Этот прием (следить, чтобы запасной ключ всегда был) позволяет удалить элемент, пройдя Б-дерево один раз от корня к листу и не делая шагов в обратном направлении (с единственным исключением, которое мы его разберем позже). Договоримся, что если в результате удаления корень дерева стал пустым, то он удаляется, и его единственный ребенок становится новым корнем, при этом высота Б-дерева уменьшается на единицу, и корень уже не пуст (если только всё дерево не пусто). На рис. 19.8 показаны разные случаи удаления элемента из Б-дерева. 1.Если ключ к находится в вершине ж, являющейся листом, то удаляем к из ж. 2.Если ключ к находится во внутренней вершине ж, то делаем следующее: а). Если ребенок у вершины ж, предшествующий к, содержит не менее t элементов, то находим ключ к, непосредственно предшествующий ключу к. Этот ключ находится в листе поддерева с корнем в у. Найти его можно за один просмотр поддерева от корня к листу. Рекурсивно вызываем процедуру: удаляем к. Заменяем в ж ключ к на к. б). Если ребенок z, следующий за к, содержит не менее t элементов, поступаем аналогично. в). Если и у, и z содержат по t - 1 элементу, соединяем вершину у, ключ к, вершину z, помещая всё это в вершину у, которая теперь содержит 24 - 1 ключ. Стираем z и выкидываем из ж ключ к и указатель на z. Рекурсивно удаляем к из у. 3.Если ж - внутренняя вершина, но ключа к в ней нет, найдем среди детей вершины ж корень сг[ж] поддерева, где должен лежать ключ к (если этот ключ вообще есть). Если сг[ж] содержит не менее t ключей, можно рекурсивно удалить к из поддерева. Если же сг[ж] содержит всего t - 1 элемент, то предварительно сделаем шаг За или 36. а). Пусть вершина сг[ж] содержит t - 1 элемент, но один из её соседей (например, правый) содержит по крайней мере t элементов. (Здесь соседом мы называем такого ребенка вершины ж, который отделен от сг[ж] ровно одним ключом-разделителем.) Тогда добавим ребёнку сг[ж] элемент его родителя ж, а родителю передадим левый элемент этого соседа. При этом самый левый ребёнок соседа станет самым правым ребенком вершины сг[ж]. |
Среды: 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 | ||