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