Какой именно алгоритм у вставки элемента в красно-черное дерево?

Пытаюсь разобраться с добавлением элемента в красно-черное дерево.
Вот по этому видео, где пошагово все показано - https://www.youtube.com/watch?v=PhY56LpCtP4

Но я не совсем понимаю некоторых действий, которые там выполняются...
Т.е. алгоритм вроде такой(Брал отсюда)

1)Если отец нового элемента красный и его дядя красный - перекрашиваем отца и дядю в черный цвет, а деда - в красный. Если дед - корень, то оставляем его черным.
2)Если отец нового элемента красный и его дядя черный - выполняем поворот. (и почему то еще и выполняем перекрашивание, если корень стал черным, но про это ничего не написано)

Untitled-2.png
Ну т.е. вот тут например если выполнить правый поворот вокруг А - А станет красным корнем. И что делать в этом случае? Перекрашивать все дерево? Т.е. в данном случае были перекрашены A и B...

Потом по видео - такие же вопросы.

Например тут, когда мы в результате левого поворота получили красный корень.
fe92431db02f476d8bffc42457662963.png

Или тут, где после добавления 5, нужно сделать левый поворот вокруг 3, в результате чего получится красный потомок у красного папы.(красная 4 - отец, красная 5 - сын)
9d713991311e4311a8bdbc7099842da9.png
Т.е. я не совсем понимаю что нужно делать в такой ситуации, т.к. нарушение возникло после поворота, а не при добавлении нового элемента. И что нужно делать ? Для 5 например отец красный, а дядя - черный, значит вроде как нужно выполнять поворот, но в видео просто перекрашиваются 4 и 3..
  • Вопрос задан
  • 725 просмотров
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы