|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[86] Рис. 13.6 Цифровое дерево хранит строки 1011, 10, 011, 100 и 0. Каждой вершине соответствует ключ - строка, которую можно прочесть, идя из корня в эту вершину, поэтому эти ключи не надо хранить специально (на рисунке они показаны для наглядности). Тёмные вершины не соответствуют ключам, а являются промежуточными для других вершин. 14 Красно-чёрные деревья В главе 13 мы показали, что основные операции с двоичным деревом поиска высоты h могут быть выполнены за 0(h) действий. Деревья эффективны, если их высота мала - но малая высота не гарантируется, и в худшем случае деревья не более эффективны, чем списки. Красно-чёрные деревья - один из типов «сбалансированных» деревьев поиска, в которых предусмотрены операции балансировки, гарантирующие, что высота дерева не превзойдёт O(lgn). 14.1. Свойства красно-чёрных деревьев Красно-чёрное дерево (red-black tree) - это двоичное дерево поиска, вершины которого разделены на красные (red) и чёрные (black). Таким образом, каждая вершина хранит один дополнительный бит - её цвет. При этом должны выполняться определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза, поэтому дерево можно назвать сбалансированным (balanced). Каждая вершина красно-чёрного дерева имеет поля color (цвет), key (ключ), left (левый ребёнок), right (правый ребёнок) и р (родитель). Если у вершины отсутствует ребёнок или родитель, соответствующее поле содержит nil. Для удобства мы будем считать, что значения nil, хранящиеся в полях left и right, являются ссылками на дополнительные (фиктивные) листья дерева. В таком пополненном дереве каждая старая вершина (содержащая ключ) имеет двух детей. Двоичное дерево поиска называется красно-чёрным деревом, если оно обладает следующими свойствами (будем называть их RB-свойствами, по-английски red-black properties): 1.Каждая вершина - либо красная, либо чёрная. 2.Каждый лист (nil) - чёрный. Рис. 14.1 Красно-чёрное дерево. Чёрные вершины показаны как тёмные, красные - как серые. Каждая вершина либо красная, либо черная. Все nil-листья чёрные. Дети красной вершины - чёрные. Для каждой вершины все пути от неё вниз к листьям содержит одинаковое количество чёрных вершин. Около каждой вершины (кроме листьев) записана её чёрная высота. Чёрная высота листьев равна 0. 3.Если вершина красная, оба её ребёнка чёрные. 4.Все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин. Пример красно-чёрного дерева показан на рисунке 14.1. Рассмотрим произвольную вершину х красно-чёрного дерева и пути, ведущие вниз от неё к листьям. Все они содержат одно и то же число чёрных вершин (добавим к ним путь из корня в х и применим свойство 4). Число чёрных вершин в любом из них (саму вершину х мы не считаем) будем называть чёрной высотой (black-height) вершины х и обозначать ЬЬ(ж). Чёрной высотой дерева будем считать чёрную высоту его корня. Следующая лемма показывает, что красно-чёрные деревья хороши как деревья поиска. Лемма 14.1. Красно-чёрное дерево с п внутренними вершинами (т.е. не считая ть-листъев) имеет высоту не больше 21g(ra+l). Доказательство. Сначала покажем, что поддерево с корнем в х содержит по меньшей мере 2hh(x) - 1 внутренних вершин. Доказательство проведём индукцией от листьев к корню. Для листьев чёрная высота равна 0, и поддерево в самом деле содержит не менее 2ЪНХ) - 1 = 2° - 1 = 0 внутренних вершин. Пусть теперь вершина х не является листом и имеет чёрную высоту к. Тогда оба её ребёнка имеют чёрную высоту не меньше к - 1 (красный ребёнок будет иметь высоту к, чёрный - к - 1). По предположению индукции левое и правое поддеревья вершины х содержат не менее 2fc 1 - 1 вершин, и потому поддерево с корнем в х содержит по меньшей мере 2fc 1 - 1 + 2fc 1 - 1+1 = 2fc - 1 внутренних вершин. Чтобы завершить доказательство леммы, обозначим высоту дерева через h. Согласно свойству 3, по меньшей мере половину всех |
Среды: 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 | ||