1632
правки
Изменения
м
<font color=green>// случай, когда нет "дяди" </font>
rollbackEdits.php mass rollback
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>$10$, $6$, $45$, $4$, $8</tex>$. На примере можно видеть, что после добавления вершины с ключом <tex>0</tex> и соответствующих перекрашиваний вершина с ключом <tex>6</tex> становится красной с красным родителем. Дальше добавим <tex>5</tex>. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого <tex>(-3)</tex>. Тогда вершина с ключом <tex>4</tex> станет красной (<tex>0</tex> и <tex>5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
===Альтернативные===
'''while''' "отец" красный <font color=green>// нарушается свойство <tex>3</tex> </font>
'''if''' "отец" {{---}} левый ребенок
'''if''' есть красный "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather
'''else'''
'''if''' t {{---}} правый сын
t = parent
rightRotate(grandfather)
'''else''' <font color=green>// "отец" {{---}} правый ребенок </font>
'''if''' есть красный "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather
'''else''' <font color=green>// нет "дяди" </font>
'''if''' t {{---}} левый ребенок
