Вращение в красном черном дереве

Question

Я пытаюсь выяснить вращение в красно-черном дереве, пока его балансировка не завершена. Я понимаю, почему происходит вращение, но я не понимаю, как это делается. Кроме того, какие промежуточные повороты, такие как LL, RR, LR и RL, выполняются для достижения результата, и я также был бы признателен, если бы кто-нибудь сказал мне какое-либо практическое правило относительно того, когда выполнять любое из этих вращений. Вот вращение:

Rr(2) is the case when black node deficiency is in right child of "py" i.e. 
"y" and grandchild of "v" are 2 red nodes i.e. "b" and "x"

Answer 1

Вы можете попытаться лучше понять повороты в красных черных деревьях, разбив операцию на разные повороты. Есть только 3 основных операции для левого наклоняющегося красного черного BST. Операции выполняются в порядке, указанном на этом слайде.

Более того, красное черное дерево, которое вы показали, не является правильным, поскольку оно нарушает условие для красного черного дерева. то есть. Каждый путь от корня до листа должен иметь одинаковое количество черных ребер. Но в вашем конечном дереве путь от x до c имеет 2 черных ребра, в то время как путь от x до a имеет 1 черное ребро. Я рекомендую вам прочитать больше о самобалансирующихся BST и красно-черных BST здесь.

PS. Мне не принадлежит слайд. Это было взято из курса Роберта Седжвика по Алгоритмам из coursera.