Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 73
Текст из файла (страница 73)
Структуры даннмт © (з)б. ~~ру з (:,;:4 , .Случай 1 (в) (в) Су ЯЗ (г) Рис. 13.4. Пример работы процедуры КВ-1няиит-Р(хцш (я) Узел я после вставки. Посюлььу и з. и его родитель я. р красные, нвблкыеется нарушение свойстве 4. Посяольку "дядя" з, узел у, красный, в коде процедуры срмТатышет случай 1. Мы перекрашиваем узлы и перемещаем указатель = вверх по дереву, получая результат, показанный в чести (б).
Вновь е и его родитель креснме, но теперь "дядя" е, узел р, черный. Поскольку я являезся правым дочерним узлом по опюшению к з.р. применйм случай 2. Мм выполняем левый поворот, и полученное в результате дерево показано в части (в). Теперь я является левым дочерним узлом своего родителя, твк что применйм случай 3 Перекрешивание и правый поворот веют покювиное в части (г) яоррекпюе кресло-черное дерево. Глава 33. Красно-черные деревья 331 а. Узел г красный.
б. Если з. р является корнем, то ж р черный. в. Если имеется нарушение красно-черных свойств, то это нарушение только одно — нарушение либо свойства 2, либо свойства 4. Если нарушено свойство 2, то это вызвано тем, что корнем дерева является красный узел з; если нарушено свойство 4, то в этом случае красными являются узлы гидр, Часп.
(в), в которой говорится о возможных нарушениях красно-черных свойств, наиболее важна для того, чтобы показать, что процедура КВ-1нзект-Е1х!3Р восстанавливает красно-черные свойства. Части (а) и (б) просто поясняют ситуацию. Поскольку мы сосредоточиваем свое рассмотрение только на узле з и узлах, находящихся в дереве вблизи него, полезно знать, что узел е — красный (часть (а)). Часть (б) используется для того, чтобы показать, что узел з.р.р, к которому мы обращаемся в строках 2, 3, 7, 8, 13 и !4, существует. Вспомним, что необходимо показать, что инвариант цикла выполняется перед первой итерацией цикла, что любая итерация цикла сохраняет инвариант и что инвариант цикла обеспечивает выполнение требуемого свойства по окончании работы цикла.
Начнем с рассмотрения инициализации и завершения работы цикла, а затем, подробнее рассмотрев работу цикла, докажем, что он сохраняет инвариант цикла. Попутно покажем, что есть только два возможных варианта действий в каждой итерации цикла — указатель з перемещается вверх по дереву или выполняются некоторые повороты и цикл завершается. Инициализации. Перед выполнением первой итерации цикла имеется красно- черное дерево без каких-либо нарушений красно-черных свойств, к которому мы добавляем красный узел ж Покажем, что все части инварианта цикла выполняются к моменту вызова процедуры КВ-1ызвкт-Е[х!3Р.
а. В момент вызова процедуры КВ-1нзект-Е!х!3Р узел г — вставленный в дерево красный узел. б. Если узел е.р является корнем, то он черный и не изменяется до вызова процедуры КВ-1хзект-Е!х!3Р. в. Мы уже убедились в том, что красно-черные свойства 1, 3 и 5 сохраняются к моменту вызова процедуры КВ-1!чэект-Е1х!3Р.
Если нарушается свойство 2, то красный корень должен быть добавленным в дерево узлом е, который при этом является единственным внутренним узлом дерева. Поскольку и родитель, и оба потомка з являются ограничителями, свойство 4 не нарушается. Таким образом, нарушение свойства 2— единственное нарушение красно-черных свойств во всем дереве. Если же нарушено свойство 4„то, поскольку дочерние по отношению к з узлы являются черными ограничителями, а до вставки з никаких нарушений красно-черных свойств в дереве не было, нарушение заключается в том, что и з, и г.р — красные. Кроме этого, других нарушений красно-черных свойств не имеется.
Часть Ш. Структрры данны* Завершение. Цикл завершает свою работу, югда г.р становится черным (если г — корневой узел, то г.р представляет собой черный ограничитель Т. ш1). Таким образом, свойство 4 при завершении цикла не нарушается, В соответствии с инвариантом цикла единственным нарушением красно-черных свойств может быть нарушение свойства 2. В строке 16 это свойство восстанавливается, так что по завершении работы процедуры КВ-1нзлкт-г1х~л' все красно- черные свойства дерева выполняются. Сохранение. В действительности во время работы цикла эгЬйе следует рассмотреть шесть разных случаев, однако три из них симметричны трем другим; разница лишь в том, является ли родитель г.р левым или правым дочерним узлом по отношению к своему родителю г.р.р, что и выясняется в строке 2 (мы привели юд только для ситуации, югда г.р является левым потомюм).
Узел г.р.р существует, поскольку, в соответствии с частью (б) инварианта цикла, если г. р — корень дерева, то он черный. Посюльку цикл начинает работу, толью если г, р — красный, то г. р не может быть корнем. Следовательно, г.р.р существует. Случай 1 отличается от случаев 2 и 3 цветом "брата" родительского по отношению к г узла, т.е. "дяди" узла г. После выполнения строки 3 указатель у указывает на дядю узла г — узел г.р.р. пдлг, а в строке 4 проверяется его цвет. Если у — красный, выполняется код для случая 1; в противном случае выполняется юд для случаев 2 н 3.
В любом случае узел г.р.р — черный, посюльку узел г. р — красный, а свойство 4 нарушается только между г и г.р. Случай 1. "Дядя" у узла г — красный На рис. 13.5 показана ситуация, возникающая в случае 1 (строки 5-8), югда и г. р, и у — красные узлы. Посюльку узел г.р. р — черный, мы можем исправить ситуацию, когда и г, и г.р оба красные, покрасив и г.р, и у в черный цвет. Мы можем также окрасить г.р.
р в красный цвет, тем самым поддержав свойство 5. После этого мы повторяем цикл зчЫ!е с узлом г.р.р в качестве нового узла г. Указатель г, таким образом, перемещается на два уровня вверх по дереву. Теперь покажем, что в случае 1 инвариант цикла сохраняется. Обозначим через г узел г в текущей итерации, а через г' = г.р.р — узел, юторый будет называться г в проверке в строке 1 в следующей итерации. а. Поскольку в данной итерации цвет узла г. р, р становится красным, в начале следующей итерации узел г' — красный.
б. Узел г', р в текущей итерации — г.р.р.р, и цвет данного узла в пределах данной итерации не изменяется. Если это корневой узел, то его цвет до начала данной итерации был черным и остается таковым в начале следующей итерации. в. Мы уже доказали, что в случае 1 свойство 5 сохраняется; кроме того, понятно, что при выполнении итерации ие возникает нарушения свойства 1 или 3. Глава 13. Красно-черлые деревья 353 (Р у ф (в) ',.Кя . )) в Навык :,'ьь у [6) ) зй г "А';: у и р вя' Б к а )5 Если узел г' в начале очередной итерации является корнем, то код, соответствующий случаю 1, корректирует единственное нарушение свойства 4. Поскольку узел л' — красный и корневой, единственным нарушенным становится свойство 2, причем это нарушение связано с узлом л'.
Если узел л' в начале следующей итерации является корнем, то код, соответствующий случаю 1, корректирует единственное нарушение свойства 4, имеющееся перед выполнением итерации. Поскольку л' — узел красный и корневой, свойство 2 становится единственным нарушенным, и зто нарушение вызнано узлом л'. Если узел г' в начале следующей итерации корнем не является, то код, соответствующий случаю 1, не вызывает нарушения свойства 2. Этот код корректирует единственное нарушение свойства 4, имеющееся перед выполнением итерации.
Коррекция выражается в том, что узел л' становится красным и оставляет узел л'.р нетронутым. Если узел л).р был черным, то свойство 4 не нарушается; если же зтот узел был красным, то окрашивание узла л' в красный цвет приводит к нарушению свойства 4 между узлами л' и л'.р. Случай 2. 'Дядям т) узла л черный, н л — праенй потомок Случай 3. "Дядя у узла л черный, и л — лееый потомок В случаях 2 и 3 цвет узла 1), являющегося "дядей*' узла г, черный.
Эти два случая отличаются один от другого тем, что г является левым или правым дочерним узлом по отношению к родительскому узлу л.р. Строки 10 и 11 12 звв. л)ж Рлс. 15.5. Случай ! процедуры НВ-1нькктдцхок Свойство 4 нарушено, поскольку и в, и его роапельский узел в.р красные. Мы предпринимаем одни и те же действия, югла (в) а является правым дочерним узлом и югда (6) в является левым дочерним узлом.
Каждое нз поддеревьев о, Д ), 6 и к имеет черный корень, и у кюкдого одна и та же черная высота. Код лля случая 1 изменяет цвета некоторых узлов, сохраняя свойство 5: все нисходяшие простые пути ст узла к листу сгиернаг одно и то яи количество черных узлов. Цикл майе прсдсллается с "дедом" в. р. р узла в в качестве нового узла в. Любое нарушение свойства 4 макет теперь произойтн только между новым в (окрашенным в красный цвет) и его родителем, если он тмске красный.
Часуль 111. Структуры даллыт /4 у б Случай 3 Рнс. 13.б. Случаи 2 н 3 процедуры КВ-1манкт-Гулок. Как н в случае 1, свойство 4 нарушается либо случаем 2, либо случаем 3, поскольку л н сто роллтельскнй узел «.р красные. Каждое нз поддеревьев о, р, .у н Б имеет черный япрень (о, р н у согласно свойству 4, а б — поскольку в противном случае мы получили бы случай 1), н каждое нз ннх имеет одну н ту же черную высоту.
Мы преобразуем случай 2 в случай 3 левым поворотом, который сохраняет свойство 5; все ннсходлшне простые путн от узла к листу содержат одно и то же калнчество черных узлов. Случай 3 прнвошп к определенному перекрашнванню н правому повороту, чта также сохраняет свойство 5. Затем цикл ьтййе завершается, поскольку свойство 4 удовлетворено: в одной строке больше нет двух красных узлов. псевдокода соответствуют случаю 2, который показан на рис. 13.6 вместе со случаем 3. В случае 2 узел «является правым потомком своего родительского узла.
Мы используем левый поворот для преобразования сложившейся ситуации в случай 3 (строки 12 — 14), когда «является левым потомком. Поскольку и «, и «.р — красные узлы, поворот не влияет ни на черную высоту узлов, ни на выполнение свойства 5. Когда мы приходим к случаю 3 (либо непосредственно, либо поворотом из случая 2), узел д, дядя узла «, имеет черный цвет (поскольку иначе мы бы получили случай 1). Кроме того, обязательно существует узел «.р.р, так как мы доказали, что этот узел существовал при выполнении строк 2 и 3, а также что после перемещения узла «на один узел вверх в строке 10 с последукнцим опусканием на один уровень в строке 11 узел «.р.р остается неизменным. В случае 3 мы выполняем ряд изменений цвета и правый поворот, которые сохраняют свойство 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
