Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 71
Текст из файла (страница 71)
Ь=1 Глава ББ Бинарные деревья наивна 339 д. Вспоминая альтернативный анализ рандомизированной версии алгоритма быстрой сортировки из задачи 7.3, сделайте вывод о том, что Р(п) = 0(п!б п). В каждом рекурсивном вызове быстрой сортировки мы выбираем случайный опорный элемент для разделения множества сортируемых элементов.
Каждый узел в бинарном дереве поиска также отделяет часть элементов, попадающих в поддерево, для которого данный узел является корневым. с Опишите реализацию алгоритма быстрой сортировки„в которой в процессе сортировки множества элементов выполняются те же сравнения, что и для вставки элементов в бинарное дерево поиска. (Порядок, в котором выполняются сравнения, может быть иным, однако сами множества сравнений должны совпадать.) И4 Количество различных бинарных деревьев Обозначим через Ь„количество различных бинарных деревьев с п узлами.
В этой задаче будет выведена формула для Ь„и найдена ее асимптотическая оценка. а Покажите, что Ьо = 1 и что для п > 1 Ь„=~ Ь„Ь„,, б. Пусть В(х) — производящая функция (определение производящей функции можно найти в задаче 4.4) В(х) = Еь.х". н=о Покажите, что В(х) = хВ(х)з + 1, и, следовательно, В(х) можно записать в аналитическом виде как В(х) = — (1 — ь/à — 4х) 1 2х Разложение в ряд Тейлора функции 3'(х) вблизи точки х = а определяется как 3 !ь)(а) 3(х) = ~~ь, (х — а) а=о где 3(")(х) — й-я производная ! в точке х. в. Покажите, что Часть 11!. Структуры данньи 340 (и-е число Каталана)„используя разложение в ряд Тейлора функции ь2à — 4х вблизи точки х = О.
(Если хотите, вместо разложения в ряд Тейлора используйте обобщение биномиального разложения (В.4) для нецелого показателя степени и, когда для любого действительного числа п н целого к выражение © интерпретируется как п(п — 1) . (и — к+ 1)/Ы при к > 0 и как 0— в противном случае.) 2. Покажите, что 4п 3/3 ( Заключительные замечания Подробное рассмотрение простых бинарных деревьев поиска (которые были независимо открыты рядом исследователей в конце 1950-х годов) и их различных вариаций имеется в книге Кнута (Клвг(у) [210]'.
Там же рассматриваются и цифровые деревья. Цифровые деревья часто называют "лучами*' (ап(еа"), термином, образованным из средних букв слова "получение" (агейтееуаГ). Во многих книгах, включая два предыдущих издания данной книги, приводится несколько более простой метод удаления узла нз бинарного дерева поиска при наличии обоих дочерних узлов. Вместо замены узла 2 следующим за ним узлом у мы удаляем узел у, но копируем его ключ и сопутствующие данные в узел ж Недостатком такого подхода является то, что в действительности удаляемый узел может не совпадать с узлом, передаваемым процедуре удаления.
Если другие компоненты программы работают с указателями на узлы дерева, в результате они могут оказаться с устаревшими указателями на реально удаленные узлы. Хотя метод удаления, представленный в этом издании книги, немного сложнее использовавшегося ранее, он гарантирует, что вызов для удаления узла з в действительности удалит узел 2 и только его. В разделе 15.5 будет показано, каким образом можно построить оптимальное бинарное дерево поиска, если частоты поисков известны заранее, до начала построения дерева. В этом случае дерево строится таким образом, чтобы прн наиболее частых поисках просматривалось минимальное количество узлов дерева.
гимеегся русский перевод: Д Киуя Лскусстяо программирования, и. а Сортировка и лоиск, 2-е ияд.— Мл И.Д "Вильямс", 2000. Глава 13. Красно-черные деревья В главе 12 было показано, что бинарные деревья поиска высоты Ь реализуют все базовые операции над динамическими множествами, такие как Белксн, Ркепесеззок, Бпссеззок, М1н1мпм, Млх1мцм, 1нзект и Пееете, со временем работы О()г). Таким образом, операции выполняются тем быстрее, чем меньше высота дерева. Однако в наихудшем случае производительность бинарного дерева поиска оказывается ничуть не лучшей, чем производительность связанного списка.
Красно-черные деревья представляют собой одну из множества "сбалансированных" схем деревьев поиска, которые гарантируют время выполнения операций над динамическим множеством 0(1б п) даже в наихудшем случае. 13.1. Свойства красно-черных деревьев Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным битом цвета в каждом узле. Цвет узла может быть либо красным (кеп), либо черным (велск). В соответствии с накладываемыми на узлы дерева ограничениями ни один простой путь от корня в красно-черном дереве не отличается от другого по длине более чем в два раза, так что красно-черные деревья являются приближенно сбалансированными.
Каждый узел дерева содержит атрибуты со1ог, )геу, 1етг, пдЫ и р. Если не существует дочернего или родительского узла по отношению к данному, соответствующий указатель принимает значение н1е. Мы будем рассматривать зги значения нш как указатели на внешние узлы 1листья) бинарного дерева поиска. При зтом все "нормальные" узлы, содержащие поле ключа, становятся внутренними узлами дерева.
Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным саойсгааам, 1. Каждый узел является либо красным, либо черным. 2. Корень дерева является черным узлом. 3. Каждый лист дерева (иге) является черным узлом. 4. Если узел красный, то оба его дочерних узла черные. Часть ГГГ. Структуры данныс 5.
Для каждого узла все простые пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов. На рис. 13.1, (а) приведен пример красно-черного дерева. Для удобства работы с граничными условиями в красно-черных деревьях мы заменим все листья одним ограничивающим узлом, представляющим значение нп. (с этим приемом мы уже встречались — см. с. 270).
В красно-черном дереве Т ограничитель Т. пй представляет собой объект с теми же атрибутами, что и обычный узел дерева. Значение со1ог этого узла равно вьлск (черный), а все остальные атрибуты — р, 1еД, пдЫ и lсеу — могут иметь произвольные значения. Как показано на рис. 13.1,(б), все указатели на нп.
заменяются указателями на ограничитель Т. пс1. Использование ограничителя позволяет нам рассматривать дочерний по отношению к узлу х нп. как обычный узел, родителем которого является узел х. Хотя можно было бы использовать различные ограничители для каждого значения нп. (что позволило бы точно определять их родительские узлы), этот подход привел бы к неоправданному перерасходу памяти. Вместо этого мы используем единственный ограничитель Т.пй для представления всех ни. — как листьев, так и родительского узла корня. Значения атрибутов р, 1еД, г1дЬГ и /сеу ограничителя не играют никакой роли, хотя для удобства мы можем присвоить им те или иные значения.
В целом мы ограничим наш интерес к красно-черным деревьям только их внутренними узлами, поскольку лишь они хранят значения ключей. В оставшейся части данной главы при изображении красно-черных деревьев все листья опускаются, как это сделано на рис. 13.1, (в). Количество черных узлов на любом простом пути от узла х (не считая сам узел) к листу будем называть черной высотой (Ыаск-Ье(КЬГ) узла и обозначать как ЬЬ(х). В соответствии со свойством 5 красно-черных деревьев черная высота узла — точно определяемое значение, поскольку все нисходящие простые пути из узла содержат одно и то же количество черных узлов. Черной высотой дерева будем считать черную высоту его корня. Следующая лемма показывает, почему красно-черные деревья хорошо использовать в качестве деревьев поиска.
Лемма 13.1 Красно-черное дерево с и внутренними узлами имеет высоту, не превышаю- щую 21я(п+ 1). Доказательство. Начнем с того, что покажем, что поддерево любого узла х содержит как минимум 2ьь( ) — 1 внутренних узлов. Докажем это по индукции по высоте х. Если высота х равна О, то узел х должен быть листом (Т. пй), а поддерево узла х содержит не менее 2ь"ск) — 1 = 2о — 1 = 0 внутренних узлов.
Теперь для выполнения шага индукции рассмотрим узел х, который имеет положительную высоту и представляет собой внутренний узел с двумя потомками. Каждый дочерний узел имеет черную высоту либо ЬЬ(х), либо ЬЬ(х) — 1 в зависимости от того, является ли его цвет соответственно красным или черным. Поскольку Ряаел ! 3. Кресло-черльге дг)ссеья М3 *©-. '(4~Ф.. со:ф з ~ ф ) ф ~ "-"'33!! 43 аь)в ~~:~!$": яаяхг (ьпю а)ьяг 43 ( (эМ': ~ 'е.:'М'~ (:.3:;) Йл ьав ЙВ ьйв а)В ЯВ Ж ФЙЯВЮЮ айа (с) Т.
яй (в) — -©--- гй Ф" Э © .Ф„. (ь) Рве. 1К1. Красно-черное дерево с более темными черными узлами и более светаымн красныии. Кпкдый узел красно-черного дерева либо красный, либо черный; оба дочерних узла красного ума — черные, н количеспю черных узлов одинааово на юокдом простом пути от узла до его наследяию-листа. (а) Каждый лист, показанный как н)ь, черный. Каждый не-н(ь узел помечен его черной высотой; листья нп. имеют черную высоту О. (6) То яю красно-черное дерево, но все мп. в нем заменены единствеинмм ограничителем Т.о((, который клеща черный, а черные высоты узлов опущены.
родителем корневого узла также являегся ограничитель. (и) То же красно-черное дерево, но с опущенными листьями и родителем корневого узла. Именно этот стиль изображения красно-черных деревьев будет попользоваться далее в этой главе. Часть йа Структуры даккык высота потомка х меньше, чем высота самого узла х, мы можем использовать предположение индукции и сделать вывод о том, что каждый из потомков х имеет как минимум 2ьь1к1 з — 1 внутренних узлов.
Таким образом, дерево с корнем в вершине х содержит как минимум (2ьь('1 з — 1)+(2ь"(') з — 1)+1 = 2ьь(к) — 1 внутренних узлов, что и доказывает наше утверждение. Для того чтобы завершить доказательство леммы, обозначим высоту дерева через Ь. Согласно свойству 4 по крайней мере половина узлов на любом простом пути от корня к листу, не считая сам корень, должны быть черными. Следовательно, черная высота корня должна составлять как минимум Ь/2; значит, и ) 2ьсз — 1 Перенося 1 в левую часть и логарифмируя, получим, что 1я(п + 1) > 6/2, или 6 < 2 1к(п+ 1).
Непосредственным следствием леммы является то, что такие операции над динамическими множествами, как Яплксн, М1н1мим, Мхх1мим, Ркпппспззок н Яисспзюк, при использовании красно-черных деревьев выполняются за время 0(1я6), поскольку, как показано в главе 12, время работы этих операций на дереве поиска высотой Ь составляет 0(Ь), а любое красно-черное дерево с и узлами является деревом поиска высотой 0(!я и). (Само собой разумеется, обращения к мп. в алгоритмах в главе 12 должны быть заменены обрашеннями к Т. пй.) Хотя алгоритмы Ткпп-1нзпкт и Ткпп-Он.птп из главы 12 и характеризуются временем работы 0(1я и), если использовать их для вставки и удаления из красно-черного дерева, непосредственно использовать их для выполнения операций !нзпкт и 13пьптп нельзя, поскольку онн не гарантируют сохранение красно-черных свойств после внесения изменений в дерево.
Однако в разделах 13.3 и 13.4 вы увидите, что эти операции также могут быть выполнены за время 0(1к и). Упражнения 13.1.1 Начертите в стиле рис. 13.1, (а) полное бинарное дерево поиска высотой 3 с ключами (1, 2,..., 15). Добавьте к нему листья н1ь и раскрасьте полученное дерево разными способами, так, чтобы в результате получились красно-черные деревья с черной высотой 2, 3 и 4. Начертите красно-черное дерево, которое получится в результате вставки с помощью алгоритма Ткпп-1мзпкт ключа 36 в дерево, изображенное на рис. 13.1. Если вставленный узел закрасить красным, будет ли полученное в результате дерево красно-черным? А если закрасить этот узел черным? 13.1.3 Определим ослабленное красно-черное дерево как бинарное дерево поиска, которое удовлетворяет красно-черным свойствам 1, 3, 4 и 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
