|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[126] Рис. 19.4 Б-дерево высоты 3 содержит минимально возможное число ключей. Внутри каждой вершины х записано число п[х] ключей в ней. 19.1-3 Найти все Б-деревья минимальной степени 2, представляющие множество {1, 2, 3,4, 5} 19.1-4 Найти точную верхнюю оценку для числа ключей, хранящихся в Б-дереве высоты h и минимальной степени t. 19.1-5 Описать структуру данных, которая получится, если в красно-чёрном дереве каждую чёрную вершину соединить с ее красными детьми, а их детей сделать детьми этой чёрной вершины. 19.2. Основные операции с Б-деревьями В этом разделе мы подробно рассмотрим операции B-Tree-Search (поиск), B-Tree-Create (создание Б-дерева) и B-Tree-Insert (добавление элемента). Мы считаем, что: •Корень Б-дерева всегда находится в оперативной памяти, т.е. операция Disk-Read для корня никогда не требуется; однако всякий раз, когда мы изменяем корень, мы должны его сохранять на диске. •Все вершины, передаваемые как параметры, уже считаны с диска. Наши процедуры обрабатывают дерево за один проход от корня к листьям. Поиск в Б-дереве Поиск в Б-дереве похож на поиск в двоичном дереве. Разница в том, что в каждой вершине х мы выбираем один вариант из (га[ж] + 1), а не из двух. Как и процедура Tree-Search (для двоичных деревьев), рекурсивной процедура B-Tree-Search получает на вход указатель х на корень поддерева и ключ к, который мы ищем в этом поддереве. Для поиска ключа к в Б-дереве Г следует скомандовать B-Tree-Search(гоо£(Т), к), где root(T) указывает на корень. Если процедура обнаруживает ключ к в дереве, она возвращает пару (у, г), где у - вершина, г - порядковый номер указателя, для которого keyi[y] = к. В противном случае процедура возвращает константу nil. B-Tree-Search, к) 1 2while г п[х] and к > keyi[x] 3do г <- г + 1 4if г п[х] and к = keyi[x] 5then return (ж,г) 6if leaj[x] 7then return nil 8else DlSK-READ(c;[a:]) 9return B-Tree-Search(c8], k) В строках 1-3 ищется наименьшее г, для которого к keyi[x]; если такого нет, то в г помещается п[х] +1 (линейный поиск). Если нужный ключ найден, работа прекращается (строки 4-5). Затем (строки 6-7) программа либо останавливается, если поиск завершился безрезультатно (ж - лист), либо рекурсивно вызывает себя, предварительно считав с диска корень нужного поддерева (строки 8-9). На рис. 19.1 показана работа этой программы. Светлые вершины просмотрены при поиске буквы R. Как и процедура Tree-Search, наша программа просматривает вершины дерева от корня к листу. Поэтому число обращений к диску есть в(h) = 0(logf га), где h - высота дерева, а га - количество ключей. Так как га[ж] 2t, то цикл while в строках 2-3 повторяется O(t) раз, и время вычислений равно O(th) = 0(t\ogt га). Создание пустого Б-дерева При работе с Б-деревом Г, мы сначала создаем с помощью процедуры B-Tree-Create пустое дерево, а затем записываем в него данные с помощью процедуры B-Tree-Insert. Обе эти процедуры используют подпрограмму Allocate-Node, которая находит место на диске для новой вершины. Мы считаем, что подпрограмма Allocate-Node требует времени 0(1) и не использует операцию Disk-Read. Рис. 19.5 Разбиение вершины дерева минимальной степени t = 4. Делим вершину у на две: у и г. Ключ-медиана S вершины у переходит к ее родителю х. B-Tree-Create(T) 1ж <- Allocate-Node() 2leaj[x] <- true 3п[х] <- О 4Disk-Write) 5root[T] <- ж Процедура B-Tree-Create требует одного обращения к диску, время работы - 0(1). Разбиение вершины Б-дерева на две Добавление элемента в Б-дерево - значительно более сложная операция, чем добавление элемента в двоичное дерево поиска. Ключевым местом является разбиение (splitting) полной (с 2t - 1 ключами) вершины у на две вершины, имеющие по t - 1 элементов в каждой. При этом ключ-медиана (median key) keyt[y] отправляется к родителю ж вершины у и становится разделителем двух полученных вершин. Это возможно, если вершина ж неполна. Если у - корень, процедура работает аналогично. В этом случае высота дерева увеличивается на единицу. Таков механизм роста Б-дерева. Процедура B-Tree-Split-Child делит вершину у на две и меняет соответствующим образом её родителя ж. На рис. 19.5 показано, как это происходит. Ключ-медиана S вершины у переходит к её родителю ж, а большие S элементы переписываются в нового ребенка z вершины ж. Входными данными процедуры являются неполная внутренняя вершина ж, число г и полная вершину у, для которых у = сг[ж]. Мы считаем, что вершины хну уже находятся в оперативной памяти. |
Среды: 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 | ||