左倾红黑树及其不变量的删除
Deletion of the left-leaning Red Black tree and its invariant
我很难理解this paper
的说法
To do so, we maintain the in-variant that the current node or its
left child is red. We can do so by moving to the left unless the current
node is red and its left child and left grandchild are both black. In
that case, we can do a color flip, which restores the invariant but
may introduce successive reds on the right
我了解到从叶子节点到根节点的每条路径必须有相同数量的黑色links/nodes，并且本文的策略是将我们要删除的那个涂上红色并修复树此后。但是我还有以下问题：
为什么不变量是当前节点是红色或者current.left是红色？
更具体一点，对于moveRedLeft这个辅助函数，为什么它非常关注current.left的颜色。对，如果这个节点是红色的，我们要做2次旋转和1次翻转.(移动函数的条件语句)
Why the invariant is the current node is red or the current.left is red?
这是一个选择并且描述了算法。当然，如果您只是盲目地向下移动树，则不能保证此不变量为真，因为您冒着到达当前节点及其左侧 child 均为黑色的位置的风险。但是这个算法设定了一个目标来保持这个不变量，因为它有助于在仍然操纵它的同时保持在有效 black-red 树的规则内。
Why can't we move to the left if the current = red, current.left = black, current.left.left = black?
如果我们向左移动，那么我们将到达当前节点及其左侧 child 均为黑色的状态，这将违反不变量。
Why a color flip would maintain this invariant?
当算法到达上述“阻塞”状态时，颜色翻转会将当前红色节点变为黑色，而其 children 变为红色。所以保持不变量（左边的 child 现在是红色），我们现在可以在保持不变的情况下向左移动：向左移动后我们得到一个状态 current节点是红色的。
请注意，这种颜色翻转可能会使树处于无效状态，因为（在向下移动之前）current.left.right 节点可能是红色的，因为它是 child 节点的 child被翻转变成红色，这现在违反了红色节点可能没有红色的规则child。文章继续解释算法将如何解决该无效状态...
我很难理解this paper
的说法To do so, we maintain the in-variant that the current node or its left child is red. We can do so by moving to the left unless the current node is red and its left child and left grandchild are both black. In that case, we can do a color flip, which restores the invariant but may introduce successive reds on the right
我了解到从叶子节点到根节点的每条路径必须有相同数量的黑色links/nodes，并且本文的策略是将我们要删除的那个涂上红色并修复树此后。但是我还有以下问题：
为什么不变量是当前节点是红色或者current.left是红色？
更具体一点，对于moveRedLeft这个辅助函数，为什么它非常关注current.left的颜色。对，如果这个节点是红色的，我们要做2次旋转和1次翻转.(移动函数的条件语句)
Why the invariant is the current node is red or the current.left is red?
这是一个选择并且描述了算法。当然，如果您只是盲目地向下移动树，则不能保证此不变量为真，因为您冒着到达当前节点及其左侧 child 均为黑色的位置的风险。但是这个算法设定了一个目标来保持这个不变量，因为它有助于在仍然操纵它的同时保持在有效 black-red 树的规则内。
Why can't we move to the left if the current = red, current.left = black, current.left.left = black?
如果我们向左移动，那么我们将到达当前节点及其左侧 child 均为黑色的状态，这将违反不变量。
Why a color flip would maintain this invariant?
当算法到达上述“阻塞”状态时，颜色翻转会将当前红色节点变为黑色，而其 children 变为红色。所以保持不变量（左边的 child 现在是红色），我们现在可以在保持不变的情况下向左移动：向左移动后我们得到一个状态 current节点是红色的。
请注意，这种颜色翻转可能会使树处于无效状态，因为（在向下移动之前）current.left.right 节点可能是红色的，因为它是 child 节点的 child被翻转变成红色，这现在违反了红色节点可能没有红色的规则child。文章继续解释算法将如何解决该无效状态...