Пытаюсь разобраться с добавлением элемента в красно-черное дерево.
Вот по этому видео, где пошагово все показано -
https://www.youtube.com/watch?v=PhY56LpCtP4
Но я не совсем понимаю некоторых действий, которые там выполняются...
Т.е. алгоритм вроде такой(
Брал отсюда)
1)Если отец нового элемента красный и его дядя красный - перекрашиваем отца и дядю в черный цвет, а деда - в красный. Если дед - корень, то оставляем его черным.
2)Если отец нового элемента красный и его дядя черный - выполняем поворот. (и почему то еще и выполняем перекрашивание, если корень стал черным, но про это ничего не написано)
Ну т.е. вот тут например если выполнить правый поворот вокруг А - А станет красным корнем. И что делать в этом случае? Перекрашивать все дерево? Т.е. в данном случае были перекрашены A и B...
Потом по видео - такие же вопросы.
Например тут, когда мы в результате левого поворота получили красный корень.
Или тут, где после добавления 5, нужно сделать левый поворот вокруг 3, в результате чего получится красный потомок у красного папы.(красная 4 - отец, красная 5 - сын)
Т.е. я не совсем понимаю что нужно делать в такой ситуации, т.к. нарушение возникло после поворота, а не при добавлении нового элемента. И что нужно делать ? Для 5 например отец красный, а дядя - черный, значит вроде как нужно выполнять поворот, но в видео просто перекрашиваются 4 и 3..
Сложный
Простой
