我试图在完成重新平衡时找出红黑树中的旋转。我理解为什么会发生轮换，但我不明白它是如何完成的。此外，像 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"
您可以尝试通过将操作分解为不同的旋转来更好地理解红黑树中的旋转。左倾红黑 BST 只有 3 个基本操作。这些操作按本幻灯片中列出的顺序执行。
此外，您展示的红黑树是不正确的，因为它违反了红黑树的条件。IE。从根到叶的每条路径都必须有相同数量的黑边。但是在你的最后一棵树中，从 x 到 c 的路径有 2 个黑边，而从 x 到 a 的路径有 1 个黑边。我建议您从这里阅读更多关于自平衡 BST 和红黑 BST 的信息。
PS。我不拥有幻灯片。它取自 Robert Sedgewick 的 coursera 算法课程。