Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 67
Текст из файла (страница 67)
12.5. Цифровое дерево. Ключ узла определяется путем прохода от корня к данному узлу и не должен храниться в дереве. Темным цветом показаны промежуточные узлы, не имеющие ключей Структура цифрового дерева (гайх 1гее) показана на рис. 12.5. Приведенное на рисунке дерево хранит битовые строки 1011, 10, 011, 100 и О. При поиске ключа а = аоа1... ар на г-м шаге мы переходим к левому узлу, если сч = О, и к правому, если а; = 1.
Пусть Я вЂ” множество различных бинарных строк с суммарной длиной и. Покажите, как использовать цифровое дерево для лексикографической сортировки за время 9 (и). Для примера, приведенного на рис. 12.5, отсортированная последовательность должна выглядеть следующим образом: О, 011, 10, 100, 1011. 12-3. Средняя глубина вершины в случайном бинарном дереве поиска В данной задаче мы докажем, что средняя глубина узла в случайном бинарном дереве поиска с п узлами равна О (!я и). Хотя этот результат и является более слабым, чем в теореме 12.4, способ доказательства демонстрирует интересные аналогии между построением бинарного дерева поиска и работой алгоритма КАмпоьпхнп Я01скзокт из раздела 7.3.
Определим общую длину путей Р(Т) бинарного дерева Т как сумму глубин всех узлов х Е Т, которые мы будем обозначать как о'(х, Т). а) Покажите, что средняя глубина узла в дереве Т равна — ,'> И (х, Т) = — Р (Т) . 1 1 п ' и хгг Таким образом, нам надо показать, что математическое ожидание Р(Т) равно 0(п1яп). Часть 111.
Структуры данных 334 б) Обозначим через Тг. и Тл соответственно левое и правое подаеревья дерева Т. Покажите, что если дерево Т имеет и узлов, то Р (Т) = Р (Ть) + Р (Тл) + и — 1. в) Обозначим через Р(и) среднюю общую длину путей случайного бинарного дерева поиска с и узлами.
Покажите, что 1 и-1 Р (и) = — ~1 (Р (г) + Р (и — г' — 1) + и — 1). 1=О г) Покажите, что и-1 Р( 1) = — ~~1 РЯ+ 9(и). а=1 д) Вспоминая анализ рандомизированной версии алгоритма быстрой сортировки из задачи 7-2, сделайте вывод, что Р (и) = О (и 1я и). В каждом рекурсивном вызове быстрой сортировки мы выбираем случайный опорный элемент разделения множества сортируемых элементов. Каждый узел в бинарном дереве также отделяет часть элементов, попадающих в поддерево, для которого данный узел является корневым. е) Приведите реализацию алгоритма быстрой сортировки, в которой в процессе сортировки множества элементов выполняются те же сравнения, что и для вставки элементов в бинарное дерево поиска.
(Порядок, в котором выполняются сравнения, может быть иным, однако сами множества сравнений должны совпадать.) 12-4. Количество различных бинарных деревьев Обозначим через Ь„количество различных бинарных деревьев с и узлами. В этой задаче будет выведена формула для Ь„и найдена ее асимптотическая оценка. а) Покажите, что Ьо = 1 и что для и > 1 и-1 Ь„= ~ ~Ь„Ь„, б) Пусть В (х) — производящая функция (определение производящей функции можно найти в задаче 4.5): В(х) = ,'> Ь„х".
и=о Глава 12. бинарные деревья поиска 335 Покажите, что В (х) = хВ (х) + 1 и, следовательно, В (х) можно записать как 1 В(х) = — (1 — Л вЂ” 4х) . 2х Разложение а ряд Тейлора функции /' (х) вблизи точки х = а определяется как - ~("() /(х) = ~), (х — а), а=о где /(~1(х) означает Й-ю производную функции / в точке х. в) Покажите, что б„ является и-м числом Каталана — (") используя разложение в ряд Тейлора функции ~/1 — 4х вблизи точки х = О. (Если хотите, то вместо использования разложения в ряд Тейлора можно использовать обобщение биномиального разложения (В.4) для нецелого показателя степени и, когда для любого действительного числа п н целого /с выражение Щ) интерпретируется как и (и — 1)...
(и — й + 1)/'Ы при к ) 0 и 0 в противном случае.) г) Покажите, что 4" 3/2 ( (~/ и Заключительные замечания Подробное рассмотрение простых бинарных деревьев поиска (которые были независимо открыты рядом исследователей в конце 1950-х годов) и их различных вариаций имеется в работе Кнута (Кпш)з) [185). Там же рассматриваются и цифровые деревья. В разделе 15.5 будет показано, каким образом можно построить оптимальное бинарное дерево поиска, если частоты поисков известны заранее, до начала построения дерева.
В этом случае дерево строится таким образом, чтобы прн наиболее частых поисках просматривалось минимальное количество узлов дерева. Граница математического ожидания высоты случайного бинарного дерева поиска в разделе 12.4 найдена Асламом (Аз!ат) [23]. Мартинец (Мап(лет) и Роура (Коша) [211) разработали рандомизированный алгоритм для вставки узлов в бинарное дерево поиска и удаления их оттуда, при использовании которого в результате получается случайное бинарное дерево поиска. Однако их определение случайного бинарного дерева поиска несколько отлично от приведенного в данной главе.
ГЛАВА 13 Красно-черные деревья В главе 12 было показано, что бинарные деревья поиска высоты 6 реализуют все базовые операции над динамическими множествами (БиАксн, РннпнснззОк, Биссвззок, М~ямцм, МАх~мим, 1ьбннт и Рв.втв) за время О (Ь). Таким образом, операции выполняются тем быстрее, чем меньше высота дерева. Однако в наихудшем случае производительность бинарного дерева поиска оказывается ничуть не лучше, чем производительность связанного списка.
Красно-черные деревья представляют собой одну из множества "сбалансированных" схем деревьев поиска, которые гарантируют время выполнения операций над динамическим множеством О (1б и) даже в наихудшем случае. 13.1 Свойства красно-черных деревьев Красно-черное дерево представляет собой бинарное дерево поиска с одним дополнительным битом ивеюиа в каждом узле. Цвет узла может быть либо красным, либо черным. В соответствии с накладываемыми на узлы дерева ограничениями, ни один путь в красно-черном дереве не отличается от другого по длине более чем в два раза, так что красно-черные деревья являются приближенно сбалансированными. Каждый узел дерева содержит поля со1ог, йеу, 1е~1, тюдор и р. Если не существует дочернего или родительского узла по отношению к данному, соответствующий указатель принимает значение м~.
Мы будем рассматривать эти значения ип. как указатели на внешние узлы (листья) бинарного дерева поиска. При этом все "нормальные" узлы, содержащие поле ключа, становятся внутренними узлами дерева. Глава 13. Красно-черные деревья 337 Бинарное дерево поиска является красно-черным деревом, если оно удовлетворяет следующим красно-черным свойствам. 1. Каждый узел является красным или черным. 2.
Корень дерева является черным. 3. Каждый лист дерева (ы!ь) является черным. 4. Если узел — красный, то оба его дочерних узла — черные. 5. Для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов. На рис. ! 3.1а показан пример красно-черного дерева. На рисунке черные узлы показаны темным цветом, красные — светлым. Возле каждого узла показана его "черная" высота.
У всех листьев она, само собой разумеется, равна О. Для удобства работы с красно-черным деревом мы заменим все листья одним ограничивающим узлом, представляющим значение нп. (с этим приемом мы уже встречались в разделе 10.2). В красно-черном дереве Т ограничитель из! (Т] представляет собой объект с теми же полями, что и обычный узел дерева. Значение со!ог этого узла равно в!.Аск (черный), а все остальные поля могут иметь произвольные значения. Как показано на рис. 13.1б, все указатели на мп. заменяются указателем на ограничитель и!! [Т(. Использование ограничителя позволяет нам рассматривать дочерний по отношению к узлу х м!!. как обычный узел, родителем которого является узел х. Хотя можно было бы использовать различные ограничители для каждого значения ми.
(что позволило бы точно определять их родительские узлы), згот подход привел бы к неоправданному перерасходу памяти. Вместо этого мы используем единственный ограничитель для представления всех и!ь — как листьев, так и родительского узла корня. Величины полей р, 1е(1, пдиг и кеу ограничителя не играют никакой роли, хотя для удобства мы можем присвоить им те или иные значения.
В целом мы ограничим наш интерес к красно-черным деревьям только их внутренними узлами, поскольку только они хранят значения ключей. В оставшейся части данной главы при изображении красно-черных деревьев все листья опускаются, как это сделано на рис. 13.1в. Количество черных узлов на пути от узла х (не считая сам узел) к листу будем называть черной высотой узла (Ыас)с-Ье!ф!) и обозначать как Ьй (х). В соответствии со свойством 5 красно-черных деревьев, черная высота узла — точно определяемое значение. Черной высотой дерева будем считать черную высоту его корня. Следующая лемма показывает, почему красно-черные деревья хорошо использовать в качестве деревьев поиска.
Лемма 13.1. Красно-черное дерево с п внутренними узлами имеет высоту не более чем 21к(и+1). ззв Часть 1й. Структуры данных --'©--- — . ,'Ф.; 4В. 1': С. © , 3; Щв ЯЯ 1йй ЯЩ ЯЯ ЯЯ ЯЯ Яй ЯЯ ЯЯ аяа ЯЭ ~И Рис. 13.1. Пример красно-черного дерева Доказаюиельстао. Начнем с того, что покажем, что поддерево любого узла х содержит как минимум 2ьь(е~ — 1 внутренних узлов. Докажем это по индукции по высоте х. Если высота х равна О, то узел х должен быть листом (оЯ ~Т]) и поддерево узла х содержит не менее 2ь"~*~ — 1 = 2е — 1 = О внутренних узлов. Теперь рассмотрим узел х, который имеет положительную высоту и представляет собой внутренний узел с двумя потомками.
Каждый потомок имеет черную высоту либо Ьй (х), либо ЬЬ (х) — 1, в зависимости от того, является ли его цвет соответственно красным или черным. Поскольку высота потомка х меньше, чем Глава 13. Красно-черные деревья 339 высота самого узла х, мы можем использовать предположение индукции и сделать вывод о том, что каждый из потомков х имеет как минимум 2ь"1*1 — 1 внутренних узлов. Таким образом, дерево с корнем в вершине х содержит как минимум (2ьь1з) 1 — 1) + (2ь" 1*1 1 — 1) + 1 = 2ьь(*1 — 1 внутренних узлов, что и доказывает наше утверждение. Для того чтобы завершить доказательство леммы, обозначим высоту дерева через Ь. Согласно свойству 4, по крайней мере половина узлов на пути от корня к листу, не считая сам корень, должны быть черными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
