在红黑树中旋转后重新着色时要遵循的规则
Rules to follow while recoloring after rotation in Red Black Tree
我只是 RB 树的新手。我刚刚在旋转后重新给树上色时被绞死了。
让我们考虑以下情况：-
插入顺序：34,32,56,30,31
34 (B)
32 (B) 56 (B)
30 (R)
31 (R)
上面的例子是31插入到30的parent中出现颜色冲突，并且高度不稳定
所以对于树 32、30、31，我们正在做左右旋转，这与在 AVL 树中做的一样。
直到这次轮换，我觉得还不错。
但是旋转之后，树会变成这样，
34 (B)
31 (R) 56 (B)
30 (R) 32 (B)
所以在这里，红红冲突发生在31和30。并且左子树的黑度也受到影响。
请问，formula/conditions 的步骤是什么，我必须申请才能纠正这个着色和黑度问题。
提前致谢。
在 RED BLACK 树中插入键时要记住的不变量是：
1.根永远黑.
2.两个红色节点不能连续.
3.从每个根到空路径访问的黑节点数必须相等
牢记以上几点，让我们进行插入：
插入(34)
34(B)
插入(32)
34(B)
/
32(R)
插入(56)
34(B)
/ \
32(R) 56(R)
插入(30)
34(B)
/ \
32(R) 56(R)
/
30(R)
违反不变量2。
为了处理这个问题，我们将节点 32 和 56 重新着色为黑色，并使它们的父节点为红色。
但是通过使它们的父级变为红色 不变量 1 发生冲突，所以我们将它们的父级保持为黑色并且我们有以下树。
34(B)
/ \
32(B) 56(B)
/
30(R)
上面的树满足所有不变量，我们继续插入。
插入(31)
34(B)
/ \
32(B) 56(B)
/
30(R)
\
31(R)
违反不变量2。
为了处理这种违规行为，我们在 node 32 and node 31 上执行 左旋转 （影响这 2 个节点的单个旋转）。
34(B)
/ \
32(B) 56(B)
/
31(R)
/
30(R)
现在我们在 node 31 and node 32
上执行 右旋
34(B)
/ \
31(R) 56(B)
/ \
30(R) 32(B)
现在我们在 node 31 and node 34
上执行 右旋
31(R)
/ \
30(R) 34(B)
/ \
32(B) 56(B)
现在我们将 node 31 和 node 30 重新着色为黑色，将 node 32 和 node 56 重新着色为红色。我们得到以下树：
31(B)
/ \
30(B) 34(B)
/ \
32(R) 56(R)
我们最终的树满足红黑树的所有性质，也是平衡的.
我已经教授算法和数据结构几年了，我对 red/black 树的诚实建议如下：
Know where the rotation rules and color flips come from, but don't memorize them.
实际需要手动跟踪 red/black 树旋转或必须对其进行编码的情况极为罕见。在这些情况下，我建议做大多数人所做的事情，即打开 CLRS 的副本并复制其中包含的任何伪代码。
在我看来，更有价值的是首先了解这些规则从何而来，以及人们如何设法推导出这些规则。虽然这并不经常被教导，但 red/black 树的原始规则是通过使用 red/black 树和称为 2-3-4 tree. 2-3-4 trees are significantly easier to understand than red/black trees, and once you've seen the connection between them you can actually rederive all the rotations and color flips you'll need to fix up a red/black tree on-the-fly and without too much difficulty. I've put together a set of lecture slides outlining the connection between these data structures and how to use it 的相关数据结构之间的连接导出的，如果您有兴趣，这可能是了解 red/black 树如何工作的好方法。
我只是 RB 树的新手。我刚刚在旋转后重新给树上色时被绞死了。
让我们考虑以下情况：-
插入顺序：34,32,56,30,31
34 (B)
32 (B) 56 (B)
30 (R)
31 (R)
上面的例子是31插入到30的parent中出现颜色冲突，并且高度不稳定
所以对于树 32、30、31，我们正在做左右旋转，这与在 AVL 树中做的一样。
直到这次轮换，我觉得还不错。
但是旋转之后，树会变成这样，
34 (B)
31 (R) 56 (B)
30 (R) 32 (B)
所以在这里，红红冲突发生在31和30。并且左子树的黑度也受到影响。
请问，formula/conditions 的步骤是什么，我必须申请才能纠正这个着色和黑度问题。
提前致谢。
在 RED BLACK 树中插入键时要记住的不变量是：
1.根永远黑.
2.两个红色节点不能连续.
3.从每个根到空路径访问的黑节点数必须相等
牢记以上几点，让我们进行插入：
插入(34)
34(B)
插入(32)
34(B)
/
32(R)
插入(56)
34(B)
/ \
32(R) 56(R)
插入(30)
34(B)
/ \
32(R) 56(R)
/
30(R)
违反不变量2。
为了处理这个问题，我们将节点 32 和 56 重新着色为黑色，并使它们的父节点为红色。
但是通过使它们的父级变为红色 不变量 1 发生冲突，所以我们将它们的父级保持为黑色并且我们有以下树。
34(B)
/ \
32(B) 56(B)
/
30(R)
上面的树满足所有不变量，我们继续插入。
插入(31)
34(B)
/ \
32(B) 56(B)
/
30(R)
\
31(R)
违反不变量2。
为了处理这种违规行为，我们在 node 32 and node 31 上执行 左旋转 （影响这 2 个节点的单个旋转）。
34(B)
/ \
32(B) 56(B)
/
31(R)
/
30(R)
现在我们在 node 31 and node 32
34(B)
/ \
31(R) 56(B)
/ \
30(R) 32(B)
现在我们在 node 31 and node 34
31(R)
/ \
30(R) 34(B)
/ \
32(B) 56(B)
现在我们将 node 31 和 node 30 重新着色为黑色，将 node 32 和 node 56 重新着色为红色。我们得到以下树：
31(B)
/ \
30(B) 34(B)
/ \
32(R) 56(R)
我们最终的树满足红黑树的所有性质，也是平衡的.
我已经教授算法和数据结构几年了，我对 red/black 树的诚实建议如下：
Know where the rotation rules and color flips come from, but don't memorize them.
实际需要手动跟踪 red/black 树旋转或必须对其进行编码的情况极为罕见。在这些情况下，我建议做大多数人所做的事情，即打开 CLRS 的副本并复制其中包含的任何伪代码。
在我看来，更有价值的是首先了解这些规则从何而来，以及人们如何设法推导出这些规则。虽然这并不经常被教导，但 red/black 树的原始规则是通过使用 red/black 树和称为 2-3-4 tree. 2-3-4 trees are significantly easier to understand than red/black trees, and once you've seen the connection between them you can actually rederive all the rotations and color flips you'll need to fix up a red/black tree on-the-fly and without too much difficulty. I've put together a set of lecture slides outlining the connection between these data structures and how to use it 的相关数据结构之间的连接导出的，如果您有兴趣，这可能是了解 red/black 树如何工作的好方法。