Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 70
Текст из файла (страница 70)
Определим случайно иосизроенное бинарное дерево ионска (звш)ош1у Ьп111 Ь!лагу зеагсЬ тгее) с п ключами как дерево, которое возникает при вставке ключей в изначально пустое дерево в случайном порядке, когда все п! перестановок входных ключей равновероятны (в упр. 12яЬЗ требуется показать, что это условие отличается от условия равно- вероятности всех возможных бинарных деревьев поиска с п узлами).
В данном разделе мы докажем следующую теорему. Теорана 12.4 Математическое ожидание высоты случайно построенного бинарного дерева поиска с п различными ключами равно 0(!я п). Доказавачьсэиво. Начнем с определения трех случайных величин, которые помогут определить высоту случайного бинарного дерева поиска. Обозначая высоту случайного бинарного дерева поиска с п ключами как Х„, определим эксионенцнвльную высоэиу У„= 2~".
При построении бинарного дерева поиска с п ключамн мы выбираем один из них в качестве корня. Обозначим через Л„случайную величину, равную рангу корневого ключа в множестве из всех п ключей, т.е. Л„ содержит позицию, которую бы занимал ключ, если бы множество было отсортяровано. Значение В„с равной вероятностью может быть любым элементом множества 11, 2,..., п). Если В„= э', то левое поддерево корня представляет собой случайно построенное бинарное дерево поиска с 1 — 1 ключами, а правое— с и — 1 ключами. Поскольку высота бинарного дерева на единицу больше наибольшей из высот поддеревьев корневого узла, экспоненциальная высота бинарного дерева в два раза больше экспоненциальной высоты наивысшего из поддеревьев корневого узла.
Если мы знаем, что Л = г, то У„= 2 шах(У; ыУ„;) В качестве базового случая мы имеем Уз = 1, поскольку экспоненциальная высота дерева с одним узлом составляет 2о = 1, и для удобства мы определим Уо = О. Далее мы определим индикаторные случайные величины Е„д, Я„з,..., Е„„, где Я„я =1(В„= ь) Поскольку В„с равной вероятностью может быть любым элементом множества !1,2,...,п), Рг(В = г) = 1/п для 1 = 1,2,...,и, а следовательно, сошасно лемме 5.1 мы имеем Е [Ешь) = 1/п (!2.!) Часть!3!. Стауктуаы даинта 334 для 1 = 1, 2,..., и. Поскольку ровно одно значение Яи! равно 1, а все прочие равны О, мы также имеем Уи = ~~ Бил(2 шах(У! 1,Уи 1)) 1=1 Е[Уи] = Е ~4„,1(2.
глах(У; мУи;)) 1=1 Е[Я„;(2 шах(У-мУ- ))] и Е [Я„,;] Е [2 шах(У; 1, Уи,)] 1=1 — . Е [2 . шах(У; 1, Уи ,)] 1 =1 2 — ~~> Е [шах(У1 1, Уи;)] "1=1 — (Е [У; 1] + Е [У„з]) 1=1 (из линейности математического ожидания) (из независимости) (согласно (12.1)) (согласно (В.22)) (из упр. В.З.4) . Поскольку каждый член Е [1'с], Е [У1],..., Е [Уи 1] появляется в последней сумме дважды, как Е [Уз 1] и как Е [Уи,], мы получаем следующее рекурреитное соотношение; и — 1 Е[Уи] ( — у Е [У!] .
(12.2) 1=0 Мы покажем, что Е [Уи] полиномиально зависит от и, что неизбежно приводит к выводу, что Е [Х„] = 0(1я и). Мы утверждаем, что индикаторная случайная переменная 4 „; = 1(Ви = 1) не зависит от значений Уз 1 и У„ ;. Если В„ = 1', то левое поддерево, экспоненциальная высота которого равна У! и случайным образом строится из г — 1 ключей, ранги которых меньше 1.
Это поддерево ничем не отличается от любого другого случайного бинарного дерева поиска из 1 — 1 ключей. Выбор В = 1 никак ие влияет на структуру этого дерева, а влияет только на количество содержащихся в нем узлов. Следовательно, случайные величины У, 1 и Я„; независимы.
Аналогично правое поддерево, экспоненциальная высота которого равна Уи и строится случайным образом из и — 1 ключей, ранги которых больше 1. Структура этого дерева не зависит от Л„, так что случайные величины Уи 1 и 4,„3 независимы. Следовательно, мы имеем Глава 12. Бинарные деревьв юаиска 335 Используя метод подстановок, покажем, что для всех натуральных и рекуррентное соотношение (12.2) имеет следуюшее решение: Е[У„] <— При этом мы воспользуемся тождеством Е,('") =( ") (12.3) (В упр. 12,4.1 данное тождество предлагается доказать самостоятельно.) Заметим, что для базовых случаев границы 0 = Уо = Е [Уо] < (1/4) (зз) = 1/4 и 1 = У1 = Е [У1] < (1/4) ( + ) = 1 справедливы.
По индукции имеем н-1 Е [Ъи] < — ~~ Е [Уе] э=о 4" '1( -:-з) =.-'Е("') 1 и+3 1 (и+ 3)! п 4! (и — 1)! 1 (и+ 3)! 4 3!о! 1 и+3 (согласно гипотезе индукции) (согласно (12.3)) 2к!х ! < Е [2х ] = Е[У„], Мы получили границу для Е [У„], но наша конечная цель — найти границу Е [Х„]. В упр. 12.4.4 требуется показать, что функция Д(к) = 2и выпуклая вниз (см. с. 1251). Таким образом, мы можем применить неравенство Йенсена (В.26), которое гласит, что Чаать Ш. Структуры данньи н получить 2Е(Х)~ 1 и+3 1 (и+ 3)(п+ 2)(и+ 1) 4 6 из 1 бпз 1 11и 1 б Взятие логарифма от обеих частей дает нам Е '1Х„'1 = 0(13 п).
Упражнения 12.4.1 Докажите уравнение (12.3). 12.4.2 Приведите пример бинарного дерева поиска с и узлами, такого, что средняя глубина узла в дереве равна 9(13 и), в то время как высота дерева — м(13 и). Найдите асимптотическую верхнюю границу высоты бинарного дерева поиска с и узлами, средняя глубина узла в котором составляет 9(13 и). 12.4.3 Покажите, что понятие случайного бинарного дерева поиска с п ключами, когда выбор каждого дерева равновероятен, отличается от понятия случайно построенного бинарного дерева поиска, приведенного в этом разделе.
(Указание: рассмотрите все возможные деревья при и = 3.) 12.4.4 Покажите, что функция 1(х) = 2а является выпуклой вниз. 12.4.5 * Рассмотрим процедуру Клмоомиео-ОО1скзокт, работающую с входной последовательностью из и различных чисел. Докажите, что для любой константы )г > О время работы алгоритма превышает 0(п 1яп) только для 0(1/п")-й части всех возможных и! перестановок. Задачи 12.1. Бинарные деревья ноиска с одинаковыми ключами Одинаковые ключи приводят к проблеме при реализации бинарных деревьев поиска. Чему равно асимптотическое время работы процедуры Тнее-1мзект при вставке п одинаковых ключей в изначально пустое дерево? Гяаы!2 Бонарине деревья вряскв Мы предлагаем улучшить алгоритм ТКЕЕ-1!ЧЗЕКТ, добавив в него перед строкой 5 проверку равенства г.йеу = х.йеу, а перед строкой 11 — проверку равенства г. Ьеу = у. Йеу.
Если равенства выполняются, мы реализуем одну из описанных далее стратегий. Для каждой из ннх найдите асимптотическое время работы при вставке п одинаковых ключей в изначально пустое дерево. (Описания приведены для строки 5, в которой сравниваются ключи г и х. Для строки 11 замените в описании х на у.) б. Храним в узле х булев флаг х. Ь и устанавливаем х равным либо х.
1еф, либо х. пдЬ1, в зависимости от значения х. Ь, которое поочередно принимает значения РА1ЗЕ и ТКУЕ при каждом посещении х в процессе вставки узла с тем же ключом, что и у х. в. Храним все элементы с одиныввыми ключами в одном узле х с помощью списка и при вставке просто добавляем элемент г в этот список. г. Случайным образом присваиваем х значение х. 1еД или х. пдЫ. (Каково будет время работы такой стратегии в наихудшем случаед Оцените ожидаемое время работы данной стратегии.) 12.2. Цифровые деревья Пусть имеются две строки а = аоа!... ар н Ь = ЬоЬ!...
Ьч, в которых все символы а, и Ь принадлежат некоторому упорядоченному множеству. Мы говорим, что строка а лексикографически меньше строки Ь, если выполняется одно из двух условий: 1, существует целое 0 < 2 < ппп(р, д), такое, что а, = Ь, для всех 1 = О, 1,..., ! — 1 и а < Ь, или 2. р < д и а; = Ь; для всех з = О, 1,..., р.
Например, если а и Ь представляют собой битовые строки, то 10100 < 10110 согласно правилу 1 (полагая 2 = 3), а 10100 < 101000 согласно правилу 2. Это упорядочение подобно упорядочению слов в словаре естественного языка по алфавиту. Структура данных цифрового дерева (гад(х ггее), показанная на рнс. 12.5, хранит битовые строки 1011, 10, 011, 100 н О. При поиске ключа на глубине 1 мы переходим к левому узлу, если а, = О, н к правому, если а, = 1. Пусть Я— множество различных битовых строк с суммарной длиной п.
Покажите, как использовать цифровое дерево для лексикографической сортировки за время Ез(п). В примере, приведенном на рис. 12.5, отсортированная последовательность должна выглядеп следующим образом: О, 011, 1О, 100, 1011. 12.3. Средняя глубина вершины в случайно построенном бинарном дереве яонскв В данной задаче мы докажем, что средняя глубина узла в случайно построенном бинарном дереве поиска с п узлами равна 0(!к п). Хотя этот результат и является более слабым, чем в теореме 12.4, способ доказательства демонстрирует Часть!И.
Структуры далиых 338 О, О Рис. 13.5. Цифровое дерево с битовыми строками 1011, 1О, 011, 100 и О. Ключ кавщого узла можно определить путем прохода по простому пути от юрия к атому узлу. Следовательно, ист иеобходимости хранить ключи в узлах; здесь значения ключей приведеиы только в иллюстративных целях. Узлы заштриховвиы темным цветом, если соответствующие им юиочи отсутствуют в дереве; такие узлы существуют только для устаповлеиив путей к друтим узлам. интересные аналогии между построением бинарного дерева поиска и работой алгоритма йдыпомзкю-(;нлскаокт из раздела 7.3. Определим общую длину иуюеи Р(Т) бинарного дерева Т как сумму глубин всех узлов х Е Т, которую мы будем обозначать как И(х, Т). а. Покажите, что средняя глубина узла в дереве Т равна 1 — с1(х, Т) = -Р(Т) .
1 еСГ Таким образом, нужно показать, что математическое ожидание Р(Т) равно 0(п 1к и). б. Обозначим через Тт. и Тн соответственно левое и правое поддеревья дерева Т. Покажите, что если дерево Т имеет и узлов, то Р(Т) = Р(Тс.) + Р(Тл) + и — 1 . а Обозначим через Р(п) среднюю общую длину путей случайно построенного бинарного дерева поиска с п узлами. Покажите, что 1 и — 1 Р(п) = — ~~ (Р(з)+Р(п — з' — 1)+и — 1) и с=о а Покажите, как переписать Р(п) как 2 и — 1 Р(п) = — ~~ Р(й) + 9(п) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
