在红黑树上旋转

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

您可以尝试打破操作成不同的旋转，以了解红黑树旋转以更好的方式。左倾红黑BST只有3种基本操作。操作按照本幻灯片中列出的顺序执行。

此外，红黑树，你已经证明是不正确的，因为它违反了一个红黑树的条件。即。从根到叶的每条路径必须具有相同数量的黑色边缘。但是在最终的树中，从x到c的路径有2个黑色边，而从x到a的路径有1个黑色边。我建议您从here了解更多关于自我平衡BST和红黑BST的信息。

PS。我不拥有幻灯片。它已经从Robert Sedgewick的coursera课程中学习。