Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 72
Текст из файла (страница 72)
Другими словами, корень 345 Глава 13. Красна-черные деревьв может быть как черным, так и красным. Рассмотрите ослабленное красно-черное дерево Т, корень которого красный. Если мы перекрасим корень дерева Т из красного цвета в черный, будет ли полученное в результате дерево красно-черным? 13.1.4 Предположим, что каждый красный узел в красно-черном дереве "поглощается" его черным родительским узлом, так что дочерний узел красного узла становится дочерним узлом его черного родителя (мы не обращаем внимания на то, что при этом происходит с ключами в узлах).
Чему равен возможный порядок черного узла после того, как будут поглощены все его красные потомки? Что вы можете сказать о глубине листьев полученного дерева? Покажите, что самый длинный простой нисходящий путь от вершины х к листу красно-черного дерева имеет длину, не более чем в два раза превышающую кратчайший нисходящий путь от х к листу-потомку. !3. 1еб Чему равно наибольшее возможное количество внутренних узлов в красно-черном дереве с черной высотой й? А наименьшее возможное количество? 13.1. 7 Опишите красно-черное дерево с и ключами с наибольшим возможным отношением количества красных внутренних узлов к количеству черных внутренних узлов.
Чему равно зто отношение? Какое дерево имеет наименьшее указанное отношение, и чему равна его величина? 13.2. Повороты Операции над деревом поиска Ткее-1хзект и Ткее-Оееете, будучи применены к красно-черному дереву с и ключами, выполняются за время 0(1б и). Поскольку они изменяют дерево, в результате их работы могут нарушаться красно- черные свойства, перечисленные в разделе 13.1. Для восстановления этих свойств необходимо изменить цвета некоторых узлов дерева, а также структуру его указателей. Изменения в структуре указателей будут выполняться с помошью ловоровмов (голапопз), которые представляют собой локальные операции в дереве поиска, сохраняющие свойство бинарного дерева поиска.
На рис. 13.2 показаны два типа поворотов — левый и правый. При выполнении левого поворота в узле х предполагается, что его правый дочерний узел у не является листом Т. М; х может быть любым узлом дерева, правый дочерний узел которого — не Т. пй. Левый поворот выполняется "вокруг" связи между х и у, делая у новым корнем поддерева, левым дочерним узлом которого становится х, а бывший левый потомок узла у— правым потомком х.
Чааль Ш. Структуры данныи 1дгт-Кат ~Т, х) (одн'' Кюнт-котята(Т, у) ,>-:-' р а )з В псевдошще процедуры 1.ерт-КОтАте предполагается, что х.гздЫ уь Т.из( и что родитель корневого узла — Т. из). ЬЕРТ-КОТАТЕ (Т, х) 1 у = х.г(дЫ 2 х.гздЫ = у.1е/г // Установка у // Превращение левого поддерева у // в правое поддерево х 3 11 у.1е/1 ф Т.и11 4 у.1е/1.р = х 5 у.р = х.р 6 11х.р == Т. из( 7 Т.гоог = у 8 еЬе11 х == х.р. 1е/1 9 х.р.1е/г = у 10 еЬех.р.пдЫ = у 11 у.1е/( = х // Передача родителя х узлу у // размещение х в качестве левого // дочернего узла у 12 х.р = у На рис. 13.3 показан конкретный пример изменения бинарного дерева поиска про- цедурой ЬЕРТ-КОТАТЕ.
Код процедурьз К1ОНТ-КОТАТЕ симметричен кОду Ьерт- КОтАте. Обе эти процедуры выполняются за время 0(1). При повороте изменя- ются только указатели; все прочие атрибуты сохраняют свое значение. Упражнении 13.2.1 Напишите псевдокод процедуры К1ОНТ-КОТАТЕ. 13.22 Покажите, что в каждом бинарном дереве поиска с и узлами имеется ровно и — 1 возможных поворотов. Рис. 1эрд Операция поворота в бинарном дереве поиска.
Операциа Ьнг~-йотлтл(т,х) преобразует конфигурацию нз двух узлов справа в конфигурацию, показанную слева, пугем изменения юнсгантного количества уююателей. Обратная операциа Кзонт-котята(Т, р) преобразует конфигурацию, показанную слева, в конфигурацию в правой части рисунка. Буквы а, р и т представляют произвольные поддеревзя. Операция поворота сохраняет свойспю бинарнога дерева поиска: ключи в а предшествуют ключу х. лер, который предшествует ключам в 11, которые предшествуют ключу у.
нер, илюрый предшествует ключам в у. 347 Глава 73. Красно-черные деревья лез ( М„.з ".: 1Р'; :1Л".:: 1:.1?.-':; (:.чу) 1лвт-нотяте(Т, яу Рис. 13З. Пример изменения бинарнаго дерева поиска процедурой 1 кгт-нотата(Т, к). Центрирсяанные с%еды исходного н модифицированного деревьев дают одинаковые списки значений 15.2.5 Пусть о, Ь и с представляют собой произвольные узлы в поддеревьях а, р и у соответственно в правом дереве на рис.
13.2. Как изменятся глубины узлов а, Ь и с при левом повороте в узле х? 15.2.4 Покажите, что произвольное бинарное дерево поиска с и узлами может быть преобразовано в любое другое бинарное дерево поиска с и узлами с использованием 0(п) поворотов. (3гказаииег сначала покажите, что и — 1 правых поворотов достаточно для преобразования дерева в правую цепочку.) 15.2.5 * Назовем бинарное дерево поиска Тг иравоиреобрегзуеягеьм в бинарное дерево поиска Тз, если можно получить Тз из Тг путем выполнения последовательности вызовов процедуры В~опт-НОтдтп.
Приведите пример двух деревьев Тг и Тз, таких, что Тг не является правопреобразуемым в Тз. Затем покажите, что если дерево Тг является правопреобразуемым в Тз, то зто преобразование можно выполнить с помощью 0(пз) вызовов процедуры Нзпнт-йотлти. Часть И!. Структуры даннык 348 13.3. Вставка Вставка узла в красно-черное дерево с и узлами может быть выполнена за время 0(18 п). Для вставки узла з в дерево Т мы используем немного модифицированную версию процедуры Ткее-1нзект (см.
раздел 12.3), которая вставляет узел в дерево, как если бы зто было обычное бинарное дерево поиска, а затем окрашивает его в красный цвет. (В упр. 13.3.1 нужно ответить, почему выбран именно красный, а не черный цвет.) Для того чтобы вставка сохраняла красно-черные свойства дерева, после нее вызывается вспомогательная процедура КВ-1нзект-Г!Хир, которая перекрашивает узлы и выполняет повороты.
Вызов КВ-!нзект(Т, г) вставляет в красно-черное дерево Т узел з с уже заполненным атрибутом Ьеу. КВ-1нзект(Т, з) 1 у = Т.п11 2 х = Т.то01 3 згй!!е х ф Т. ти1 4 у =х 5 !1жйеу < х.йеу 6 х = х.1еф 7 еВе х = х.пдЬ! 8 г.р=у 9 1Г у == Т. пз1 10 Т.гоо! = г 11 е!зеИ' ж Ьеу ( у.
Ьеу 12 у.1е7г = г 13 е1ае у.пдЬг = з 14 ж1етс = Т.п11 15 жпдЬ! = Т.п11 16 х.со1ог = кеп 17 ВВ-1нзект-р!хпР(Т, з) Есть четыре отличия между процедурами Ткее-1нзект н КВ-1нзект. Во-первых, все нп. в Ткее-1нзект заменены на Т. п11. Во-вторых, для поддержки корректности структуры дерева в строках 14 и 15 процедуры КВ-1нзект выполняется присвоение Т.
п11 атрибутам ж 1етг и з. пдЬ1. В третьих, в строке 16 мы назначаем узлу з красный цвет. И наконец, в-четвертых, поскольку красный цвет = может вызвать нарушение одного из красно-черных свойств, в строке 17 вызывается вспомогательная процедура КВ-!нзект-Е!Хпр(Т, з), назначение которой— восстановить красно-черные свойства дерева. Гяаеа /3.
Красно-черные деревни 349 КВ-(МБЕКТ-Г!ХОР(Т, е) 1 чеЬПе г.р. со1ог == КЕО 2 !Т г. р == г.р.р. 1е/1 3 д = жр.р,г1д61 4 !1 Д. со10г == КЕП 5 жр.со)ог = В1.АСК 6 д. с01ог = ВЬАСК 7 з.р. р, со!от = КЕП 8 г = г.р.р 9 е!зе !Т л == я.р. лдпя 10 л.р 1! 1,ЕРТ-КОТАТЕ (Т, л) 12 ж1а. со1ог = В1.АСК 13 з.р.р.
со1ог = КЕО !4 К10НТ-КОТАТЕ (Т, л. р. р) 15 еЬе (то же, что и в части 1Ьеп, но с заменой "правого" (пйЬ1) левым" ((ей) и наоборот) 16 Т. гоо1. со1ог = В1,АСК // Случай 1 // Случай 1 // Случай 1 // Случай 1 // Случай 2 // Случай 2 // Случай 3 // Случай 3 // Случай 3 'Случаи 2 и 3 ие являлися вааимоисалючаююими Для того чтобы понять, как работает процедура КВ-!нзект-р1Х13Р, разобьем изучение кода на три части.
Сначала определим, какие из красно-черных свойств нарушаются при вставке узла г и его окраске в красный цвет. Затем рассмотрим назначение цикла угййе в строках 1-!5. После этого изучим каждый из трех случаев', которые встречаются в этом цикле, и посмотрим, каким образом достигается цель в каждом из них. На рис. 13.4 показан пример работы процедуры КВ-!ВЯект-г1х13Р. Какие из красно-черных свойств могут быть нарушены перед вызовом К.В!Нзект-Г1Х13Р? Свойство 1, определенно, выполняется (как и свойство 3), так как оба дочерних узла вставляемого узла являются ограничителями Т. пй. Свойство 5, согласно которому для каждого узла все пути от него до листьев, являющихся потомками данного узла, содержат одно и то же количество черных узлов, также остается в силе, поскольку узел я замещает (черный) ограничитель, будучи при зтои красным и имея черные дочерние узлы.
Таким образом, может нарушаться только свойство 2, которое требует, чтобы корень красно-черного дерева был черным, и свойство 4, согласно которому красный узел не может иметь красного потомка. Оба нарушения возможны в силу того, что узел г после вставки окрашивается в красный цвет. Свойство 2 оказывается нарушенным, если узел л становится корнем, а свойство 4 — если родительский по отношению к з узел является красным. На рис. 13.4, (а) показано нарушение свойства 4 после вставки узла г. Цикл е'Ьйе в строках 1 — 15 сохраняет в начале каждой итерации цикла следующий инвариант, состоящий из трех частей. зуб Часть!П.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
