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