Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 66
Текст из файла (страница 66)
Удаленный узел у возвращается в строке 17, с тем чтобы вызывающая процедура могла при необходимости освободить или использовать занимаемую им память. Время работы описанной процедуры с деревом высотой Ь составляет О (Ь). Таким образом, в этом разделе мы доказали следующую теорему. 328 Часть !!!. Структуры данных предшествующего или последующего узла, приводит к большей сбалансированности дерева. Каким образом следует изменить процедуру Ткее РееЕТе для реализации указанной стратегии? * 12.4 Случайное построение бинарных деревьев поиска Мы показали, что все базовые операции с бинарными деревьями поиска имеют время выполнения О (6), где 6 — высота дерева.
Однако при вставке и удалении элементов высота дерева меняется. Если, например, все элементы вставляются в дерево в строго возрастающей последовательности, то такое дерево вырождается в цепочку высоты и — 1. С другой стороны, как показано в упражнении Б.5-4, 6 > '1)кп). Как и в случае быстрой сортировки, можно показать, что поведение алгоритма в среднем гораздо ближе к наилучшему случаю, чем к наихудшему. К сожалению, в ситуации, когда при формировании бинарного дерева поиска используются и вставки, и удаления, о средней высоте образующихся деревьев известно мало, так что мы ограничимся анализом ситуации, когда дерево строится только с использованием вставок, без удалений.
Определим случайное бинарное дерево поиска (гапдош1у Ьш!! Ь1пагу зеагсЬ !гее) с п ключами как дерево, которое возникает при вставке ключей в изначально пустое дерево в случайном порядке, когда все п! перестановок входных ключей равновероятны (в упражнении 12.4-3 требуется показать, что это условие отличается от условия равновероятности всех возможных бинарных деревьев поиска с п узлами). В данном разделе мы покажем, что математическое ожидание высоты случайного бинарного дерева поиска с п ключами равно О (!к п).
Мы считаем, что все ключи различны. Начнем с определения трех случайных величин, которые помогуг определить высотуслучайного бинарногодерева поиска. Обозначая высоту случайного бинарного дерева поиска с и ключами через Х„, определим экслоненциальиую высоту У„= 2~". При построении бинарного дерева поиска с п ключами мы выбираем один из них в качестве корня. Обозначим через В„случайную величину, равную рангу корневого ключа в множестве из всех и ключей, т.е.
В содержит позицию, которую бы занимал ключ, если бы множество было отсортировано. Значение В„ с равной вероятностью может быть любым элементом множества (1,2,...,и). Если В„= г', то левое поддерево корня представляет собой случайное бинарное дерево поиска с 1 — 1 ключами, а правое — с п — г' ключами. Поскольку высота бинарного дерева на единицу больше наибольшей из высот поддеревьев корневого узла, экспоненциальная высота бинарного дерева в два раза больше наибольшей экспоненциальной высоты поддеревьев корневого узла. Если В„= г', то У„= 2 тпах(У; ВУ„;).
Глава 12. Бинарные деревья поиска 329 Очевидно, что Уз = 1„поскольку экспоненциальная высота дерева с одним узлом равна 2о = 1; кроме того, для удобства определим Уо = О. Далее мы определим индикаторные случайные величины Я„л, Я„д,..., Я„„, где Поскольку В„с равной вероятностью может быть любым элементом множества 11,2,...,п), Рг(В„= Ц = 1/и для всех 1 от!до и, а значит, согласнолемме 5.1, Е [Як,з] = 1/и (12. 1) для всех г = 1, 2,..., и. Кроме того, поскольку только одно значение Я„; равно 1, а все остальные равны О, имеем 1'„= ,'~ Я„,;(2 шахЯ ыУ„;)). з=з Е[У] = Е ,'> Я„;(2. шах(У; ыУ„;)) ~=1 (в силу линейности математи- ческого ожидания) ~~> Е[Я„;(2 щах[У; ыУ„;))] = в=1 и ~~> Е[Е„,]Е[2 шах[У; з,У„;)] = в=1 ~> — . Е [2 шах (У; ы У„;)] = 1 ~=1 (в силу независимости Я и У) (в соответствии с (12.1)) Мы покажем, что Е [У„] полиномиально зависит от и, что неизбежно приводит к выводу, что Е [Х„] = 0 (1б п).
Индикаторная случайная переменная Я„; =? (В„= 1) не зависит от значений У; з и У„;. Если В„= 1, то левое поддерево, экспоненциальная высота которого равна У, з, случайным образом строится из з — 1 ключей, ранги которых меньше з. Это поддерево ничем не отличается от любого другого случайного бинарного дерева поиска из г — 1 ключей. Выбор В„= г никак не влияет на структуру этого дерева, а только на количество содержащихся в нем узлов. Следовательно, случайные величины У; з и У„; независимы. Аналогично, правое поддерево, экспоненциальная высота которого равна У„;, строится случайным образом нз и — г ключей, ранги которых больше г.
Структура этого дерева не зависит ат В„, так что случайные величины У„; и Я„; независимы. Следовательно, Часть Ш. Структуры данных 330 2 Е[птах(У; 1,У„;)] < з=1 2 < — ~~1 (Е [У, 1] + Е [У„;]) (в соответствии с (В.21)) (см. упражнение В.3-4). зз-1 Е [У„] < — ~> Е [Уз]. з=о (12.2) Используя метод подстановок, покажем, что для всех натуральных и рекуррентное соотношение (12.2) имеет следующее решение: Е[У„] <— При этом мы воспользуемся тождеством (12.3) (В упражнении 12.4-1 предлагается самостоятельно доказать данное тождество.) Убедимся, что для базовых случаев полученные границы справедливы: О = УО = Е [УО] < — [ [ = -з 4 з,З,з' 4' 1 /1+ 3'1 1 = У1 = Е [У1] < — [ ~ = 1.
4 [, З,з' Используя подстановку, получаем: Е [У„] < — ~ Е [Уз] < з=о 4" з(з.зз) з ~(зз-з) 1 и+3 (в соответствии с гипотезой индукции) (в соответствии с (12.3)) Каждый член Е [УО], Е [У1],..., Е [У„1] в последней сумме встречается дважды: один раз как Е [У; 1], и второй — как Е [У„;], так что мы получаем следующее рекуррентное соотношение: Глава 12. Бинарные деревья поиска 331 1 (и+ 3)! п 4! (и — 1)! 1 (и+ 3)! 4 3!и! 1 и + 3 Итак, мы получили границу для Е ]У„], но наша конечная цель — найти границу Е [Х„].
В упражнении 12.4-4 требуется показать, что функция Г (х) = 2* выпуклая вниз (см. раздел В.З). Таким образом, мы можем применить неравенство Йенсена (В.25), которое гласит, что 2н!х.! < Е Рх.1 Е]У] и получить, что 1(п+3''! 1 (и+3)(п+2)(п+1) пз+бп +11п+6 6 24 Логарифмируя обе части неравенства, находим, что Е 1Х„] = О(!кп). Таким образом, нами доказана следующая теорема. Теорема 12.4. Математическое ожидание высоты случайного бинарного дерева поиска с и ключами равно О (!б и). Упражнения 12.4-1. Докажите уравнение (12.3).
12.4-2. Приведите пример бинарного дерева поиска с и узлами, такого что средняя глубина узла в дереве равна О (1к и), в то время как высота дерева— ы (1я и). Найдите асимптотическую верхнюю границу высоты бинарного дерева поиска с и узлами, средняя глубина узла в котором составляет О (1я и). 12.4-3. Покажите, что при нашем определении случайных бинарных деревьев поиска с п узлами они не являются равновероятными.
(Указание: рассмотрите все возможные деревья при п = 3.) 12.4-4. Покажите, что функция ) (х) = 2* является выпуклой вниз. * 12.4-5. Рассмотрим алгоритм КАмюм~гнпЯаскзокт, работающий с входной последовательностью из п различных чисел. Докажите, что для любой константы й ) О время работы алгоритма превышает О (п!яп) толью для О (1/п~)-й части всех возможных и! перестановок. 332 Часть 01. Структуры данных Задачи 12-1. Бинарные деревья поиска с одинаковыми ключами Одинаковые ключи приводят к проблеме при реализации бинарных деревьев поиска.
а) Чему равно асимптотическое время работы процедуры Ткал 1мзнкт при вставке п одинаковых ключей в изначально пустое дерево? Мы предлагаем улучшить алгоритм Ткле 1нзнкт, добавив в него перед строкой 5 проверку равенства Ьеу [х] = Ьеу [х], а перед строкой 11— проверку равенства Ьеу [я] = Ьеу [у]. Если равенства выполняются, мы реализуем одну из описанных далее стратегий.
Для каждой из них найдите асимптотическое время работы при вставке п одинаковых ключей в изначально пустое дерево. (Описания приведены для строки 5, в которой сравниваются ключи х и х. Для строки 11 замените в описании х на у.) б) Храним в узле х флаг Ь [х] с логическим значением гл~.зе или тле, которое и определяет выбор 1е~( [х] нли г(дй1 [х] при вставке ключа со значением, равным ключу х. Значение флага при каждой такой вставке изменяется на противоположное, что позволяет чередовать выбор дочернего узла. в) Храним все элементы с одинаковыми ключами в одном узле при помощи списка„и при вставке просто добавляем элемент в этот список.
г) Случайным образом выбираем дочерний узел (еГг [х] или яда [х]. (Каково будет время работы такой стратегии в наихудшем случае? Оцените среднее время работы данной стратегии.) 12-2. Цифровые деревья Пусть имеется две строки а = аоа1... ар и Ь = ЬоЬ1... Ьд, в которых все символы принадлежат некоторому упорядоченному множеству. Мы говорим, что строка а лексикографически меныие строки Ь, если выполняется одно из двух условий. 1) Существует целое 0 < д < ш(п(р, д), такое что а; = Ь; для всех 1=0,1,...,д — 1иа <Ь.
2) р < д и для всех г = О, 1,..., р выполняется равенство а; = Ь;. Например, если а и Ь вЂ” битовые строки, то 10100 < 10110 в соответствии с правилом 1 (здесь з = 3), а 10100 < 101000 согласно правилу 2. Такое упорядочение подобно упорядочиванию по алфавиту слов в словаре естественного языка. Глава 12. Бинарные деревья поиска 333 6 В".:-~ ( р 'йФфь :; |0'7 з г,~ Рнс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
