Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 68
Текст из файла (страница 68)
Следовательно, черная высота корня должна составлять как минимум Ь/2; следовательно, и > 2ч~ — 1. Перенося 1 в левую часть и логарифмируя, получим, что 1к (и+ 1) > Ь/2, или Ь < 21Е(я+ 1). м Непосредственным следствием леммы является то, что такие операции над динамическими множествами, как ЗеАксн, М!н!мам, МАх[мим, Ркеоесеззок и ББссезяок, при использовании красно-черных деревьев выполняются за время О (1й Ь), поскольку, как показано в главе 12, время работы этих операций на дереве поиска высотой Ь составляет О (Ь), а любое красно-черное дерево с и узлами является деревом поиска высотой О (!к и). (Само собой разумеется, ссылки на мь в алгоритмах в главе 12 должны быть заменены ссылками на пя [з).) Хотя алгоритмы Тепе 1нзект и Ткее Эеьете из главы 12 и характеризуются временем работы О (1б и), если использовать их для вставки и удаления из красно- черного дерева, непосредственно использовать их для выполнения операций 1нзект и 13еьете нельзя„поскольку они не гарантируют сохранение красно-черных свойств после внесения изменений в дерево.
Однако в разделах 13.3 и 13.4 вы увидите, что эти операции также могут быть выполнены за время О (!к и). Упражнения 13.1-1. Начертите в стиле рис. 13.1а полное бинарное дерево поиска высоты 3 с ключами (1, 2,..., 15). Добавьте к нему листья н!ь и раскрасьте получившееся дерево разными способами, так чтобы в результате получились красно-черные деревья с черной высотой 2, 3 и 4. 13.1-2. Начертите красно-черное дерево, которое получится в результате вставки при помощи алгоритма Ткее 1!чзепт ключа 36 в дерево, изображенное на рис. 13.1. Если вставленный узел закрасить красным, будет ли получившееся в результате дерево красно-черным? А если закрасить этот узел черным? Часть 111. Структуры данных 340 13.1-3. Определим ослабленное красно-черное дерево как бинарное дерево поиска, юторое удовлетворяет красно-черным свойствам 1, 3, 4 и 5. Другими словами, корень может быть как черным, так и красным.
Рассмотрите ослабленное красно-черное дерево Т, корень которого красный. Если мы перекрасим корень дерева Т из красного цвета в черный, будет ли получившееся в результате дерево красно-черным? 13.1-4. Предположим, что каждый красный узел в красно-черном дереве "поглощается" его черный родительским узлом, так что дочерний узел красного узла становится дочерним узлом его черного родителя (мы не обращаем внимания на то, что при этом происходит с ключами в узлах). Чему равен возможный порядок черного узла после того, как будут поглощены все его красные потомки? Что вы можете сказать о глубине листьев получившегося дерева? 13.1-5. Покажите, что самый длинный нисходящий путь от вершины х к листу красно-черного дерева имеет длину, не более чем в два раза превышающую кратчайший нисходящий путь от х к листу.
13.1-6. Чему равно наибольшее возможное число внутренних узлов в красно- черном дереве с черной высотой )с? А наименьшее возможное число? 13.1-7. Опишите красно-черное дерево с и ключами с наибольшим возможным отношением количества красных внутренних узлов к количеству черных внутренних узлов. Чему равно это отношение? Какое дерево имеет наименьшее указанное отношение, и чему равна его величина? 13.2 Повороты Операции над деревом поиска Ткее 1хзект и Ткее )Зеваете, будучи применены к красно-черному дереву с п ключами, выполняются за время 0(1бп). Поскольку они изменяют дерево, в результате их работы могут нарушаться красно-черные свойства, перечисленные в разделе 13.1. Для восстановления этих свойств мы должны изменить цвета некоторых узлов дерева, а также структуру его указателей.
Изменения в структуре указателей будут выполняться при помощи повороиюв (готат1опз), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска. На рис. 13.2 показаны два типа поворотов — левый и правый (здесь ст,,О и у — произвольные поддеревья). При выполнении левого поворота в узле х предполагается, что его правый дочерний узел р не является листом ттт1 '[Т). Левый поворот выполняется "вокруг" связи между х и у, делая у новым юрием поддерева, левым дочерним узлом которого становится х, а бывший левый потомок узла у — правым потомком зь Глава 13.
Красно-черные деревья 341 гоп а.лдпцк о — — ь т д х ! х у Ф Рнс. 13.2. Операции поворота в бинарном де- реве поиска В псевдокоде процедуры 1.егт Котлте предполагается, что гтдЬС[х] ?~ и11[Т], а родитель корневого узла — и11[Т]. 1.вгт Котлтн(Т, х) 1 у - гтдЬС[х] 2 тъдЬС [х] — 1егС [у] С> Устанавливаем у. > Левое поддерево у становится ~> правым поддеревом х 3 и 1ефу] ф и11[Т] 4 Сйеп р[1е~С[у]] — х 5 р[у] — р[х] > Перенос родителя х в у б !1 р[х] = и11[Т] 7 СЬев гооС[Т] - у 8 е1ае их = 1ефр[х]] 9 СЬеп 1еф[р[х]] - у 1О е1зе тздЬС[р[х]] — у 1 1 1е~С[у] — х с х — левый дочерний у 12 р[х] — у Упражнения 13.2-1. Запишите псевдокод процедуры К~онт Котлте.
13.2-2. Покажите, что в каждом бинарном дереве поиска с и узлами имеется ровно и — 1 возможных поворотов. 13.2-3. Пусть а, Ь и с — произвольные узлы в поддеревьях а, 13 и ? в левой части рис. 13.2. Как изменится глубина узлов а, Ь и с при левом повороте в узле х? 13.2-4. Покажите, что произвольное бинарное дерево поиска с и узлами может быть преобразовано в любое другое бинарное дерево поиска с п узлами На рис.
13.3 показан конкретный пример выполнения процедуры 1.вгт Котлтв. Код процедуры К|онт Котлтв симметричен коду 1.нгт Котлте. Обе зти процеду- ры выполняются за время О (1). При повороте изменяются только указатели, все остальные поля сохраняют свое значение.
Часть 111. Структуры данных 342 т„") ~2О! ь за Й(лаз('7, л! '® 62~ ~1 ) л() Рис. 13.3. Пример выполнения процедуры альт Котлтв с использованием 0(п) поворотов. (Указание: сначала покажите, что п — 1 правых поворотов достаточно для преобразования дерева в правую цепочку.) * 13.2-5. Назовем бинарное дерево поиска Тз иравонреобразуемым в бинарное дерево поиска Тз, если можно получить Тз из Т~ путем выполнения серии вызовов процедуры Кюнт Котлтн. Приведите пример двух деревьев Тз и Тз, таких что Т~ не является правопреобразуемым в Тз.
Затем покажите, что если дерево Т~ является правопреобразуемым в Тз, то зто преобразование можно выполнить при помоши 0 (пз) вызовов процедуры К~сит КотАтш 13.3 Вставка Вставка узла в красно-черное дерево с п узлами может быть выполнена за время 0 (1б и). Для вставки узла я в дерево Т мы используем немного модифицированную версию процедуры Ткни 1нзнкт (см. раздел 12.3), которая вставляет узел в дерево, как если бы это было обычное бинарное дерево поиска, а затем окрашивает его в красный цвет. Для того чтобы вставка сохраняла красно-черные свойства дерева, после нее вызывается вспомогательная процедура КВ 1нзект г 1хБР, которая перекрашивает узлы и выполняет повороты. Вызов КВ 1мзект(Т, г) вставляет в красно-черное дерево Т узел г с заполненным полем йеу: Глава 13.
Красно-черные деревья 343 КВ 11чзект!Т> г) 1 у +- пП[Т) 2 х — тоо![Т) 3 иЬПе х ~ пП[Т] 4 йоу — х 5 [К Йеу[г) < Йеу(х) 6 1йеп х — !е7! [х) 7 е!зе х — тздп![х) 8 р[г] — у 9 !Т у = пП[Т] 10 гйеп тоо1(Т) — г 11 е1ве Ы Йеу[г) < Йеу[у] 12 Гпеп !ефу) — г 13 е1ае ттдл![у] + — г 14 !егг[г) — пй[Т] 15 лдл! [г) — пЫ [Т) 16 со!от[г) — кю 17 КВ 11чзект р0шР(Т> г) с Случай 2 1ь Случай 2 1> Случай 3 1ь Случай 3 Есть четыре отличия процедуры Ткее 11чзект от процедуры К.В 1нзект.
Вопервых, все 1чн. в Ткее 11чзект заменены на пП [Т]. Во-вторых, для поддержки корректности структуры дерева в строках 14-15 процедуры КВ 11чзект выполняется присвоение пП [Т] указателям 1е7г [г] и тздй! [г]. В третьих, в строке 16 мы назначаем узлу г красный цвет. И наконец, поскольку красный цвет г может вызвать нарушение одного из красно-черных свойств, в строке 17 вызывается вспомогательная процедура КВ 11чзект р1хОР[Т,г), предназначение которой— восстановить красно-черные свойства дерева: КВ 11чзект р!хОР(Т> г) 1 зтпйе со!от[р[г)) = кю 2 йо!Т р(г] = !е7с(р[р[г))] 3 гйеп у - тздл!(р(р[г]]] 4 П' со!от[у) = кю 5 1йеп со!от(р[гЦ > — ВСАск с Случай 1 6 со!от[у) — ЕЬАСК 1> Случай 1 7 со!от [р(р[г)]] — кю с Случай 1 8 р[р[г]) с Случай 1 9 е1зе Ы г = тздй1[р[г)] 10 1йеп г — р[г] 11 ЕЕРТ КОТАТЕ(Т, г) 12 со!от(р[г) ] — Е1.АСК 13 со!от[р[р[г])] — кю Часть!11.
Структуры данных 344 14 К!0нт КОтАте(Т, р[р[лП) 15 е!яе (то же, что и в "Феи", с заменой !еЯ на пдЫ и наоборот) 16 со!от[тоодТИ вЂ” иьАск с Случай 3 1 Случаи 2 и 3 ие являются взаимоисключающими. Для того чтобы понять, как работает процедура КВ 1мзнкт Е!х!!т, мы разобьем рассмотрение кода на три основные части. Сначала мы определим, какие из красно-черных свойств нарушаются при вставке узла л и окраске его в красный цвет. Затем мы рассмотрим предназначение цикла чк!з!!е в строках 1-15. После этого мы изучим каждый из трех случаев', которые встречаются в этом цикле, и посмотрим, каким образом достигается цель в каждом случае. На рис. 13.4 показан пример выполнения процедуры КВ 1нзект Р!х!зР. Какие из красно-черных свойств могут быть нарушены перед вызовом КВ 1нзект Р!хор? свойство 1 определенно выполняется (как и свойство 3), так как оба дочерних узла вставляемого узла являются ограничителями тзз1[Т).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
