Алгоритмы - построение и анализ (1021735), страница 67
Текст из файла (страница 67)
Свойство 2 оказывается нарушенным, если узел л становится корнем, а свойство 4 — если родительский по отношению к л узел является красным. На рис. 13.4а показано нарушение свойства 4 после вставки узла л. Цикл тли!1е в строках 1-15 сохраняет следующий инвариант, состоящий из трех частей. В начале каждой итерации цикла: а) узел л красный; б) если р [л[ — корень дерева, то р [л[ — черный узел; в) если имеется нарушение красно-черных свойств, то это нарушение только одно — либо нарушение свойства 2, либо свойства 4. Если нарушено свойство 2, то это вызвано тем, что корнем дерева является красный узел л; если нарушено свойство 4, то в этом случае красными являются узлы л и р [л].
Часть в, в юторой говорится о возможных нарушениях красно-черных свойств, наиболее важна для того, чтобы показать, что процедура КВ 1!чяект г!х~л' восстанавливает красно-черные свойства. Части а и б просто поясняют ситуацию. 348 Глава 13. Красно-черные деревья Спупзк ~ Ъ ф © .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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
