|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[130] ключи различны. а.Будем хранить в каждой вершине х 2-3-4 дерева поле height[x], хранящее высоту поддерева с корнем в х. Показать, что эту ин- хранить формацию можно поддерживать, не ухудшая асимптотику вре- хранящее мени поиска, добавления и удаления.- это б.Реализовать операцию объединения деревьев Т и Г", раз- неплохо! делённых ключом к. Время работы должно быть 0(\h - h"\), где Ы, h" - высоты деревьев. в.Пусть р - путь в 2-3-4 дереве Г от корня к заданному ключу к. Рассмотрим два множества ключей из Г: меньшие к (множество s) и большие к (множество s"). Показать, что s разбивается на деревья Tq,T[, .. ,Tm, разделенные ключами к[, к2, , кт (для всех у £ Г/ 1 и z £ Т выполнено у < Ц < z при г = 1, 2,..., т. Как связаны высоты деревьев T t и Т? На какие части путь р делит s"? г.Реализовать операцию разделения. Для этого следует объединить ключи из s в 2-3-4 дерево Т и ключи из s" в дерево Г". Для дерева с п ключами время работы этой операции должно быть О (log га). (Указание: при сложении стоимостей операций объединения происходит сокращение.) Замечания Сбалансированные деревья и Б-деревьев обсуждаются в Кнут [123], Ахо, Хопкрофт и Ульман [4] и Седжвик [175]. Подробный обзор Б-деревьев дан в Комер [48]. Гибас и Седжвик [93] рассмотрели взаимосвязи между разными видами сбалансированных деревьев, включая красно-чёрные и 2-3-4 деревья. В 1970 году Хопкрофт (J. Е. Hopcroft) предложил понятие 2-3 деревьев, которые явились предшественниками Б-деревьев и 2-34 деревьев. В этих деревьях каждая внутренняя вершина имеет 2 или 3 детей. Б-деревья были определены Байером и МакКрейтом в 1972 году [18]. В их работе не объяснён выбор названия. Биномиальные кучи В этой главе и в главе 21 рассматриваются структуры данных, известные как сливаемые кучи (mergeable heaps). Такая структура хранит несколько множеств (куч), элементы которых называют вершинами. Каждая вершина содержит поле key (ключ), в котором хранится некоторое число; кроме того, в вершине может храниться некоторая информация, сопровождающая это число. Сливаемые кучи позволяют выполнять следующие пять операций: Маке-Неар() создаёт и возвращает новую кучу, не содержащую элементов; lNSERT(ii, х) добавляет элемент (вершину) х в кучу Н (поле key элемента х должно быть заполнено заранее); Minimum (if) возвращает указатель на элемент кучи Н с минимальным ключом; Extract-Min (ii) изымает элемент с минимальным ключом из кучи if и возвращает указатель на изъятый элемент; Union (Hi, Н2) объединяет кучи Н\ и ii2, то есть создаёт и возвращает новую кучу, содержащую все элементы куч Н\ и Н2. Сами кучи iii и Я2 ПРИ этом исчезают. Структуры данных, описываемые в этой и следующей главах, поддерживают ещё две операции: decrease-key(ii, х, к) уменьшает ключ вершины х кучи Н, присваивая ему новое значение к (предполагается, что новое значение не превосходит старого); delete(ii, х) удаляет элемент (вершину) х из кучи Н. Как видно из таблицы 20.1, если мы не нуждаемся в операции Union, то (двоичные) кучи, с помощью которых мы сортировали массив в главе 7, весьма эффективны. Для них все операции, кроме операции Union, выполняются за время O(lgra) в худшем случае (а некоторые из операций - ещё быстрее). Но для выполнения операции Union нам приходится приписывать один массив к другому и затем выполнять процедуру Heapify, что требует времени О(га). В этой главе мы расскажем о «биномиальных кучах» (второй столбец таблицы). Обратите внимание, что объединение двух би- Процедура Двоичные кучи (в худшем случае) Биномиальные кучи Фибоначчиевы кучи (в худшем случае)(в среднем) EXTRACT-MlN Delete Decrease-Key Union Minimum Make-Heap Insert 0(1) ©(lgrx) 0(1) 0(lgn) 0(n) 0(lgn) 0(lgn) Рис. 20.1 Время выполнения различных операций для трёх видов сливаемых куч (п - общее число элементов в кучах на момент операции). номиальных куч, содержащих в сумме га элементов, требует всего лишь О (lgra) операций. В главе 21 мы рассматриваем «фибоначчиевы кучи», которые ещё более эффективны (третий столбец). Отметим, впрочем, что это улучшение достигается лишь для учётной стоимости операций при амортизационном анализе. В наших процедурах мы не занимаемся выделением и освобождением памяти для элементов куч. Все три вида куч, указанных в таблице, не позволяют эффективно реализовать поиск элемента с данным ключом (Search). Поэтому процедуры Decrease-Key и Delete получают в качестве параметра не ключ вершины, а указатель на неё (во многих случаях это требование не создаёт проблем). В разделе 20.1 определяются биномиальные деревья и кучи. Там же описывается представление биномиальных куч в программе. В разделе 20.2 показано, как реализовать все перечисленные операции за указанное в таблице 20.1 время. Биномиальная куча состоит из нескольких биномиальных деревьев. 20.1.1. Биномиальные деревья Биномиальные деревьями (binomial trees) называются упорядоченные (в смысле раздела 5.2.2) деревья Во, В\, В2, , определяемые индуктивно. Дерево Во состоит из единственной вершины (рис. 20.2а). Дерево Bk склеено из двух экземпляров дерева Bk-i. корень одного из них объявлен самым левым потомком корня другого. На рис. 20.26 показаны биномиальные деревья В0-В4. 20.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 | ||