Красно-чёрное дерево: различия между версиями

'''Случай 4:''' Родитель '''P''' является красным, но дядя '''U''' — чёрный. Также, текущий узел '''N''' — правый потомок '''P''', а '''P''' в свою очередь — левый потомок своего предка '''G'''. В этом случае может быть произведен поворот дерева, который меняет роли текущего узла '''N''' и его предка '''P'''. Тогда, бывший родительский узел '''P''' рассматривается, используя случай 53 (перенумеровывающий '''N''' и '''P'''), потому что Свойство 4 (Оба потомка любого красного узла — черные) все ещё нарушено. Вращение приводит к тому, что некоторые пути (в поддереве, обозначенном «1» на схеме) проходят через узел '''N''', чего не было до этого. Это также приводит к тому, что некоторые пути (в поддереве, обозначенном «3») не проходят через узел '''P'''. Однако, оба из этих узлов являются красными, так что Свойство 5 (Все пути от любого данного узла до листовых узлов содержат одинаковое число черных узлов) не нарушается при вращении. Однако Свойство 4 всё ещё нарушается, но теперь задача сводится к Случаю 5.