|
||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[127] B-Tree-Split-Child(2;, г, у)
Вершина у имела It детей; после преобразования в ней осталось t наименьших из них, а остальные t стали детьми новой вершины z, которая в свою очередь стала ребёнком вершины х. Ключ-медиана вершины у добавлен к вершине х и стал разделителем между вершиной у и следующей за ней вершиной z. Строки 1-8 формируют вершину z и передают ей детей. Строка 9 меняет вершину у. Наконец, строки 10-16 вносят соответствующие изменения в вершину х. Строки 17-19 сохраняют изменения на диске. Время работы циклов (строки 4-5 и 7-8) равно 0(£). (Для остальных циклов требуется не больше t шагов). Добавление элемента в Б-дерево Процедура B-Tree-Insert добавляет элемент к в Б-дерево Г, пройдя один раз от корня к листу. На это требуется время O(th) = 0(t\ogt п) и 0(h) обращений к диску, если высота дерева h. По ходу дела мы с помощью процедуры B-Tree-Split разделяем встречающиеся нам полные вершины, используя такое наблюдение: если полная вершина имеет неполного родителя, то её можно разделить, так как в родителе есть место для дополнительного ключа. В конце концов мы оказываемся в неполном листе, куда и добавляем новый элемент. Рис. 19.6 Рис. 19.6. Корень г Б-дерева (с t = 4) является полной вершиной. Он делится на две половины; при этом создается новый корень s, детьми которого становятся эти вершины. Новый корень s содержит ключ-медиану старого корня. Высота Б-дерева увеличилась на единицу. 10 else B-Tree-Insert-Nonfull (г, к) Строки 3-9 относятся к случаю добавления в дерево с полным корнем (пример на рис. 19.6). Именно в этом случае увеличивается высота Б-дерева. Отметим, что точкой роста Б-дерева является корень (а не лист, как в двоичных деревьях поиска). Сделав корень неполным (если он не был таковым с самого начала), мы вызываем процедуру B-TREE-lNSERT-NoNFULL(a;, к), которая добавляет элемент к в поддерево с корнем в неполной вершине х. Эта процедура рекурсивно вызывает себя, при необходимости (если вершина оказалась полной) выполнив разделение. B-Tree-Insert(T, к) 1г <- root[T] 2if n[r] = 2t-l 3then s <- Allocate-Node() 4root[T] <- s 5leaj[s] - false 6n[s] <- 0 7ci[s] <- r 8B-Tree-Split-Child(s 9B-Tree-Insert-Nonfu B-Tree-Insert-Nonfull (ж, к) 1г 4- п[х] 2if leaj[x} 3then while / 1 and к < кегц[х] 4do кеуг+1[х] <- А;ег/г[ж] 5 6A;eyi+i[a.] «- /г 7га[ж] <- га[ж] + 1 8Disk-Write (ж) 9else while г 1 and к < keyi[x] 10do / <- г - 1 11г - г + 1 12Disk-Read(c8]) 13if га[сг[ж]] = 2t - 1 14then B-Tree-Split-Child (ж, i, ct[x]) 15if к > &е?/г[ж] 16then г <r- i + 1 17B-Tree-Insert-Nonfull (сг[ж], /г) Эта процедура работает следующим образом. Если вершина ж - лист, то ключ к в него добавляется (строки 3-8; напомним, что вершина ж предполагается неполной). В противном случае нам нужно добавить к к поддереву, корень которого является ребёнком ж. В строках 9-11 мы находим нужного ребёнка вершины ж. Если этот ребёнок оказывается полной вершиной (строка 13), то в строке 14 он разделяется на две неполных вершины, и в строках 15-16 определяется, в какое из новых поддеревьев следует добавить к. (Заметим, что после изменения г в строке 16 нет необходимости обращаться к диску - вновь созданная вершина, к которой мы обратимся в строке 17, уже находится в оперативной памяти.) Таким образом, мы знаем, что вершина сг[ж] - неполная, и в строке 17 добавляем ключ к в соответствующее поддерево с помощью рекурсивного вызова процедуры B-Tree-Insert-Nonfull. На рис. 19.7 показаны разные случаи добавления элемента в Б-дерево. Процедура B-Tree-Insert-Nonfull использует 0(1) операций Disk-Read и Disk-Write (если не считать рекурсивного вызова). Следовательно, для Б-дерева высоты h процедура B-Tree-Insert обращается к диску 0(h) раз. Время вычислений есть 0(th) = 0(t\ogth). В процедуре B-Tree-Insert-Nonfull рекурсивный вызов является последним оператором (tail recursion), и поэтому мы могли бы заменить рекурсию циклом. Отсюда видно, что число секторов, которые необходимо держать в оперативной памяти, есть 0(1). |
Среды: 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 | ||||||||||||||||||||||||||||||||||||||