О.В. Сенюкова - Сбалансированные деревья поиска (1113408), страница 6
Текст из файла (страница 6)
Нарисовать АВЛдеревья, которые получаются после добавления каждого из этихключей.364. Красно-черные деревьяАВЛ-деревья исторически были первым примером использованиясбалансированных деревьев поиска. В настоящее время более популярны красно-черные деревья (КЧ-деревья). Изобретателемкрасно-черного дерева считается немецкий ученый Рудольф Байер.Название эта структура данных получила в статье Леонидаса Гимпаса и Роберта Седжвика 1978 года.КЧ-деревья – это двоичные деревья поиска, каждый узел которыххранит дополнительное поле color, обозначающее цвет: красныйили черный, и для которых выполнены приведенные ниже свойства.Cstruct RBNode{key_type key;struct RBNode *left;struct RBNode *right;struct RBNode *parent;char color; // цвет};PascaltypeRBTree = ^RBNode;RBNode = recordkey: key_type;left: RBTree;right: RBTree;parent: RBTree;color: boolean;end;Будем считать, что если left или right равны NULL, то это «указатели» на фиктивные листья.
Таким образом, все узлы – внутренние(нелистовые).Свойства КЧ-деревьев:1. каждый узел либо красный, либо черный;2. каждый лист (фиктивный) – черный;3. если узел красный, то оба его сына – черные;4. все пути, идущие от корня к любому фиктивному листу, содержат одинаковое количество черных узлов;5. корень – черный.37Определение 4: Черной высотой узла называется количествочерных узлов на пути от этого узла к узлу, у которого оба сына –фиктивные листья.Сам узел не включается в это число.
Например, у дерева, приведенного на Рис. 15, черная высота корня равна 2.Определение 5: Черная высота дерева – черная высота его корня.26171410721191241302347383539Рис. 15. Пример красно-черного дерева4.1 Вставка узла в КЧ-деревоСначала узел добавляется в дерево с помощью стандартного алгоритма вставки узла в двоичное дерево поиска. Вновь добавленныйузел красится в красный цвет. Если это первый узел в дереве, то онстановится корнем и перекрашивается в черный цвет. Далее производится проверка, не нарушились ли свойства КЧ-дерева.
Еслидобавленный узел не первый, то он красный, поэтому свойство 4об одинаковом количестве черных узлов на любом пути от корня клисту, не нарушается. Если родитель нового узла черный, то свойство 3 о том, что если узел красный, то оба его сына черные, такжене нарушается.
Но если родитель нового узла красный, то этосвойство будет нарушено – возникнет так называемое краснокрасное нарушение. Тогда потребуется перекраска и, возможно,перестройка дерева. Обозначим добавленный узел за X, его отца заF, его деда за G, а второго сына деда – дядю – за U. Поддеревья Tiобозначены просто буквами, в отличие от иллюстраций в разделе38про АВЛ-деревья, потому что их высота в случае КЧ-деревьев неиграет роли, а существенна только черная высота.
Будем считать,что узел X находится в левом поддереве своего деда (G), иначе всеприведенные ниже изображения будут симметричны относительновертикальной оси, проходящей через деда. Рассматривается случай, когда узел X и его отец – красные, поэтому дед G узла X –черный, иначе красно-красное нарушение было бы еще до добавления узла X. Только дядя U узла X может иметь в данном случаекак черный, так и красный цвет.
При этом цепочка узлов X-F-Gможет образовывать как прямую линию, так и угол. Поэтому можно выделить 3 случая, которые проиллюстрированы на Рис. 16–18.GFXT1T2GUT3T4FT5XT1UT3T4T5T2Рис. 16. Дядя U добавляемого узла X тоже красный: перекраска Fи U в черный цвет, а G в красный1. Дядя U добавляемого узла X красный.В этом случае достаточно выполнить только перекраску: отца идядю (F и U) – в черный цвет, деда (G) – в красный цвет.
Тогдасвойство, что у красного узла оба сына черные, будет выполнено.Свойство, что все пути, идущие от корня к листу, содержат одинаковое количество черных узлов, также не будет нарушено, потомучто в каждом из путей два узла просто поменялись цветами (G и Fслева, G и U справа).
Количество черных узлов в путях при этомне изменилось. Если G – корень, то он просто перекрашивается вчерный цвет. При этом все 5 свойств КЧ-деревьев оказываютсявыполненными. Если отец узла G тоже красный, то появится новоекрасно-красное нарушение, и понадобится дальнейшее восстановление свойств КЧ-дерева, только в роли узла X теперь будет выступать узел G. Может иметь место один из случаев 1–3.392. Дядя U добавляемого узла X черный и при этом цепочка узлов X-F-G образует прямую линию.Только перекраски отца F узла X в черный цвет, а деда G в красный будет недостаточно для восстановления свойств КЧ-дерева,потому что количество черных узлов в путях, проходящих через Gнаправо, сократится на 1. Поэтому потребуется одинарный поворот деда (G) относительно отца, в данном случае направо.
Тогдаколичество черных узлов в путях, идущих от F, который теперьстал корнем поддерева, налево и направо, вновь станет одинаковым и будет равно первоначальному количеству. Действительно,количество черных узлов в поддеревьях Ti не изменилось. Приэтом слева от корня в комбинации X-F-G-U не было черных узлов,а справа был только один черный узел U. В результирующем дереве, изображенном на Рис. 17, в комбинации X-F-G-U слева от корня также отсутствуют черные узлы, а справа – также только одинчерный узел.GFXT1FUT3T4XT5T1T2GT2T3UT4T5Рис. 17.
Дядя U добавляемого узла X черный и X-F-G образуютпрямую линию: перекраска F и G и одинарный поворот3. Дядя U добавляемого узла X черный и при этом цепочка узлов X-F-G образует угол.Перекрасив узел X в черный цвет, а его деда G – в красный, получим новое красно-красное нарушение F-G между отцом и дедом X.Ситуацию разрешает двойной поворот комбинации X-F-G, знакомый нам из раздела про АВЛ-деревья, когда нижний узел (X) оказывается наверху комбинации.
Из Рис. 18 видно, что количествочерных узлов, идущих от корня поддерева налево и направо, не40изменилось относительно первоначальной конфигурации, но приэтом красно-красное нарушение ликвидировалось. Изменилосьтолько количество красных узлов – слева уменьшилось на 1, асправа увеличилось на 1. А количество красных узлов в путях нина что не влияет.GFT1UT4XT2XFT5T1T3GT2T3UT4T5Рис.
18. Дядя U добавляемого узла X черный и X-F-G образуютугол: перекраска X и G и двойной поворотТаким образом, получается, что после вставки в КЧ-дерево длявосстановления свойств дерева требуется не более 2 поворотов.Действительно, повороты требуются только в случаях 2 и 3, а вслучае 1 достаточно только перекраски. При этом случаи 2 и 3 являются терминальными, а рекурсивно продолжиться наверх можеттолько процедура в случае 1, а она не требует поворотов.Можно заметить, что повороты при балансировке как АВЛдеревьев, так и КЧ-деревьев, делают одно и то же – поднимаютподдеревья, содержащие более глубокие узлы, и опускают поддеревья, содержащие менее глубокие узлы. Различие заключаетсялишь в определении высоты. Для АВЛ-деревьев это высота вобычном понимании, а для КЧ-деревьев это черная высота.RB-INSERT(T, x)/* На вход подается дерево T и узел x, который надо добавить вдерево.
*/1 TREE-INSERT(T, x)2 color[x] ← RED3 while x ≠ root[T] и color[parent[x]] = RED do5if parent[x] = left[parent[parent[x]]] then416y ← right[parent[parent[x]]] /* y – дядя x */7if color[y] = RED then /* случай 1 */8color[parent[x]] ← BLACK9color[y] ← BLACK10color[parent[parent[x]]] ← RED11x ← parent[parent[x]] /* при следующем заходе в цикл начнем проверку с деда x */12else13if x = right[parent[x]] then /* случай 3 *//* сводим к случаю 2 */14x ← parent[x]15TREE-ROTATE-L(T, x)16color[parent[x]] ← BLACK /* случай 2 */17color[parent[parent[x]]] ← RED18TREE-ROTATE-R(T, parent[parent[x]])19else (аналогичный текст с заменой left ↔ right)20 color[root[T]] ← BLACK4.2 Удаление узла из КЧ-дереваУдаление узла из КЧ-дерева, так же, как и удаление узла из АВЛдерева производится в два этапа: собственно удаление с помощьюалгоритма из Раздела 2.3, и восстановление свойств дерева, еслиони были нарушены.
Напомним, алгоритм удаления узла из двоичного дерева поиска зависит от того, сколько сыновей у удаляемого узла – 0, 1 или 2. Если у узла два сына, то удаляемым узломстановится его последователь – самый левый элемент правогоподдерева. В этом случае у удаляемого узла уже будет максимумодин сын (правый). Поэтому, в дальнейшем предполагается, что уудаляемого узла не более одного сына.Если удаляемый узел является красным, то после его удалениясвойства КЧ-дерева не будут нарушены.
Свойство 4 сохранится:все пути будут по-прежнему содержать одинаковое количествочерных узлов, так как при удалении красного узла оно не изменится. Свойство 3 – если узел красный, то оба его сына черные – также сохранится. Удаляемый узел красный, значит, как его отец, так42и его сын могут быть только черными. После удаления узла егосын присоединится к его отцу, а остальные связи останутся безизменения.Таким образом, восстановление свойств дерева может понадобиться только в том случае, если удаляемый узел – черный.
Еслипри этом сын удаляемого узла красный, то после удаления достаточно будет перекрасить сына удаленного узла в черный цвет,чтобы восстановить количество черных узлов на этом пути.Остальные свойства КЧ-деревьев не будут нарушены. Подобнаяситуация может возникнуть и в том случае, если удаляемый узелявляется корнем.
В этом случае дерево может состоять только издвух узлов – корня, который всегда черный, и его красного сына.Любые другие конфигурации в этом случае не отвечают свойствамКЧ-дерева. После удаления корня его сын станет единственнымузлом в дереве.Рассмотрим 5 случаев конфигурации дерева после удаления черного узла, у которого сын – черный. Обозначим сына удаленногоузла за N, а отца удаленного узла за F. После удаления F стал новым отцом N. Обозначим за B нового брата N, а за CL и CR – левого и правого сыновей B, соответственно.
На то, какой именнобудет процедура восстановления, влияет только комбинация изэтих 5 узлов. Будем считать, что N – левый сын F. В противномслучае, все изображения будут симметричными относительно вертикальной оси, проходящей через F. Если узел обозначен белымцветом, это означает, что его цвет в данной комбинации можетбыть как черным, так и красным. По условию, во всех рассмотренных ниже случаях количество черных узлов в путях, идущих от Fналево (через N) после удаления стало на один меньше, чем количество черных узлов в путях, идущих от F направо (через B), поэтому свойство 4 оказалось нарушено. Если хотя бы один из пятиузлов в рассматриваемой комбинации красный (случаи 1–4), томожно восстановить это свойство за O(1) операций перекраски илиповорота.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
