|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[83] больше числа сравнений, выполненных при добавлении этого элемента. Почему? 13.3-3 Набор из га чисел можно отсортировать, сначала добавив их один за другим в двоичное дерево поиска (с помощью процедуры Tree-Insert), а потом обойти дерево с помощью процедуры Inorder-Tree-Walk. Найдите время работы такого алгоритма в худшем и в лучшем случае. 13.3-4 Покажите, что, если вершина двоичного дерева поиска имеет двоих детей, то следующая за ней вершина не имеет левого ребёнка, а предшествующая ей вершина - правого. 13.3-5 Предположим, что указатель на вершину у хранится в какой-то внешней структуре данных и что предшествующая у вершина дерева удаляется с помощью процедуры Tree-Delete. Какие при этом могут возникнуть проблемы? Как можно изменить Tree-Delete, чтобы этих проблем избежать? 13.3-6 Коммутируют ли операции удаления двух вершин? Другими словами, получим ли мы одинаковые деревья, если в одном случае удалим сначала ж, а потом у, а в другом - наоборот? Объясните свой ответ. 13.3-7 Если у z двое детей, мы можем использовать в Tree-Delete не следующий за z элемент, а предыдущий. Можно надеяться, что справедливый подход, который в половине случаев выбирает предыдущий, а в половине - следующий элемент, будет приводить к лучше сбалансированному дереву. Как изменить текст процедуры, чтобы реализовать такой подход? ★ 13.4 Случайные двоичные деревья поиска Как мы видели, основные операции с двоичными деревьями поиска требуют времени 0(h), где h - высота дерева. Поэтому важно понять, какова высота «типичного» дерева. Для этого необходимо принять какие-то статистические предположения о распределении ключей и последовательности выполняемых операций. К сожалению, в общем случае ситуация трудна для анализа, и мы будем рассматривать лишь деревья, полученные добавлением вершин (без удалений). Определим случайное двоичное дерево (randomly built search tree) из га различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке (все га! перестановок считаем равновероятными). (Как видно из упр. 13.4-2, это не означает, что все двоичные деревья равновероятны, поскольку разные порядки добавления могут приводить к одному и тому же дереву.) В этом разделе мы докажем, что математическое ожидание высоты случайного дерева из п ключей есть 0(lg п). Посмотрим, как связана структура дерева с порядком добавления ключей. Лемма 13.3. Пусть Т - дерево, получающееся после добавления п различных ключей к\, к2, , кп (в указанном порядке) к изначально пустому дереву. Тогда к{ является предком kj в Т тогда и только тогда, когда г < j, и при этом ki = min{ki : 1 / г и k\ > kj} (ключ ki больше kj и их не разделяет ни один ключ среди к\,..., ki) или ki = max{ki : 1 / г и к\ < kj} (ключ ki меньше kj и их не разделяет ни один ключ среди к\,... , ki) Доказательство. =>: Предположим, что ki является предком kj. Очевидно, i < j (потомок появляется в дереве позже предка). Рассмотрим дерево Ti, которое получается после добавления ключей k\,k2, , ki. Путь в Ti от корня до ki тот же, что и путь в Г от корня до ki. Таким образом, если бы ключ kj был добавлен в Гг-, он стал бы правым или левым ребёнком ki. Следовательно (см. упр. 13.2-6), ki является либо наименьшим среди тех ключей из k\,k2, , ki, которые больше kj, либо наибольшим среди ключей из того же набора, меньших kj. -ч=: Предположим, что ki является наименьшим среди тех ключей k\,ki, ,ki, которые больше kj. (Другой случай симметричен.) Что будет происходить при помещении ключа kj в дерево? Сравнение kj с ключами на пути от корня к ki даст те же результаты, что и для ki. Следовательно, мы пройдём путь от корня до ki, так что kj станет потомком ki. Лемма доказана.□ Теперь можно понять, как зависит глубина каждого ключа от перестановки на входе. Следствие 13.4. Пусть Г - дерево, полученное из пустого добавлением п различных ключей k\,ki, ,kn (в указанном порядке). Для каждого ключа kj (при всех 1 j1 п) рассмотрим множества Gj = {ki : 1 . i < j н ki > ki > kj при всех / < г, для которых k\> к и Lj = {ki : 1 . i < j н ki < ki < kj при всех / < г, для которых к\ < kj Тогда ключи на пути из корня в kj - в точности Gj U Lj, а глубина kj в дереве Г равна На рисунке 13.5 изображены множества Gj и Lj. Их построение можно объяснить так. Считая для наглядности ключи числами, будем отмечать их на числовой оси: сначала к\, потом к2 и так далее вплоть до kj. В каждый момент на оси отмечено несколько точек ki,...,kt (где 1 t j - 1). Посмотрим, какая из этих точек будет ближайшей справа к будущему положению ключа kj. Множество всех таких ближайших точек (для всех моментов времени t = 1,2,... ,j - 1) и есть Gj. Ближайшие слева точки образуют множество Lj. Наша цель - оценить сверху количество элементов в Gj и Lj, поскольку сумма этих количеств равна глубине ключа kj. Фиксируем некоторое j. Число элементов в Gj будет случайной величиной, зависящей от порядка ключей на входе (имеет значение лишь порядок на ключах к\,..., kj). Мы хотим оценить это число сверху (доказать, что вероятность события «это число велико» мала). Следующий факт из теории вероятностей играет центральную роль при этой оценке. Лемма 13.5. Пусть ki,k2,...,kn есть случайная перестановка п различных чисел. Для каждого г от 1 до п рассмотрим минимальный элемент в множестве {к\, к2, , к{\. Множество всех таких элементов назовём S: Тогда P{\S\ (/3 + 1)Нп} 1/га2, где Нп - п-я частичная сумма гармонического ряда, а (3 рй 4,32 - корень уравнения (In (3 - 1)(3 = 2. Доказательство. Будем следить за тем, как меняется множество {ki,..., ki} с ростом г. На г-м шаге к нему добавляется элемент к{, причём он с равными вероятностями может оказаться первым, вторым,..., г-м по величине (каждой из этих возможностей соответствует равная доля входных перестановок). Таким образом, вероятность увеличения множества S на г-м шаге равна 1/г при любом порядке среди ключей ki,..., k{ i, так что для разных г эти события независимы. Мы приходим к ситуации, описанной в теореме 6.6: имеется последовательность независимых испытаний, вероятность успеха в г-м испытании равна 1/г. Нам надо оценить число успехов. Математическое ожидание этого числа равно 1 + 1/2 + .. .+ 1/г = Hi = In г+ 0(1), см. формулу (3.5) и задачу 6-2. Нам надо оценить вероятность того, что число успехов больше своего математического ожидания в /3 + 1 раз. •,Г) = 0, + S = {ki : 1 г га и к\ > ki для всех I < г}. |
Среды: 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 | ||