|
|||||||||||||||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[87] вершин на пути от корня к листу, не считая корень, составляют чёрные вершины. Следовательно, чёрная высота дерева не меньше /г/2. Тогда га > 2hl2 - 1. Перенося 1 налево и перейдя к логарифмам, получаем lg(ra + 1) /г/2, или /г 21g(ra + 1). Лемма доказана.□ Тем самым для красно-чёрных деревьев операции Search, Minimum, Maximum, Successor и Predecessor выполняются за время О (lgra), так как время их выполнения есть 0(h) для дерева высоты /г, а красно-чёрное дерево с га вершинами имеет высоту О (lgra). Сложнее обстоит дело с процедурами Tree-Insert и Tree-Delete из главы 13: проблема в том, что они могут испортить структуру красно-чёрного дерева, нарушив RB-свойства. Поэтому эти процедуры придётся модифицировать. Мы увидим в разделах 14.3 и 14.4, как можно реализовать добавление и удаление элементов за время О (lgra) с сохранением RB-свойств. Упражнения 14.1-1 Нарисуйте полное двоичное дерево поиска высоты 3 с ключами {1, 2,..., 15}. Добавьте NlL-листья и покрасьте вершины тремя способами так, чтобы получившиеся красно-чёрные деревья имели чёрную высоту 2, 3 и 4. 14.1-2 Предположим, что корень красно-чёрного дерева красный. Если мы покрасим его в чёрный цвет, останется ли дерево красно-чёрным? 14.1-3 Покажите, что самый длинный путь вниз от вершины х к листу не более чем вдвое длиннее самого короткого такого пути. 14.1-4 Какое наибольшее и наименьшее количество внутренних вершин может быть в красно-чёрном дереве чёрной высоты kl 14.1-5 Опишите красно-чёрное дерево, содержащее га ключей, с наибольшим возможным отношением числа красных внутренних вершин к числу чёрных внутренних вершин. Чему равно это отношение? Для какого дерева это отношение будет наименьшим, и чему равно это отношение? 14.2. Вращения Операции Tree-Insert и Tree-Delete выполняются на красно-чёрном дереве за время О (lgra), но они изменяют дерево, и резуль- Рис. 14.2 Операции вращения на двоичном дереве поиска. Операция RlGHT-RoTATE преобразует левое дерево в правое, меняя несколько указателей. Правое дерево можно перевести в левое обратной операцией Left-ROTATE. Вершины х и у могут находиться в любом месте дерева. Буквы а, /3 и у обозначают поддеревья. В обоих деревьях выполнено одно и то же свойство упорядоченности: ключи из а предшествуют кеу[х], который предшествует ключам из /3, которые предшествуют кеу[у], который предшествует ключам из у. тат может не обладать RB-свойствами, описанными в разделе 14.1. Чтобы восстановить эти свойства, надо перекрасить некоторые вершины и изменить структуру дерева. Мы будем менять структуру с помощью вращений (rotations). Вращение представляет собой локальную операцию (меняется несколько указателей) и сохраняет свойство упорядоченности. На рисунке 14.2 показаны два взаимно обратных вращения: левое и правое. Левое вращение возможно в любой вершине ж, правый ребёнок которой (назовём его у) не является листом (nil). После вращения у оказывается корнем поддерева, ж - левым ребёнком у, а бывший левый ребёнок у - правым ребёнком ж. В процедуре Left-Rotate предполагается, что right[x] ф nil. Left-Rotate (Г, ж)
На рисунке 14.3 показано действие процедуры Left-Rotate. Процедура Right-Rotate аналогична. Обе они работают за время 0(1) и меняют только указатели. Остальные поля вершин остаются неизменными. Рис. 14.3 Пример действия процедуры Left-Rotate. Дополнительные nil-листья не показаны. Порядок ключей в начальном и конечном деревьях один и тот же. Упражнения 14.2-1 Нарисуйте дерево, которое получится, если с помощью процедуры Tree-Insert добавить ключ 36 к дереву рис. 14.1. Если сделать добавленную вершину красной, будет ли полученное дерево обладать RB-свойствами? А если сделать её чёрной? 14.2-2 Напишите процедуру Right-Rotate. 14.2-3 Убедитесь, что вращения сохраняют свойство упорядоченности. 14.2-4 Пусть а, Ь и с - произвольные вершины в поддеревьях а, (3 и 7 на рис. 14.2 (справа). Как изменится глубина а, Ь и с при выполнении левого вращения? 14.2-5 Покажите, что произвольное двоичное дерево поиска с п вершинами может быть преобразовано в любое другое дерево с тем же числом вершин (и теми же ключами) с помощью 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 | |||||||||||||||||||||||||||||||||||||||