deleteMin左倾斜红黑树需要更多说明 [英] deleteMin Left Leaning Red Black Tree needs more explanation

问题描述

我正在阅读Robert Sedgewick编写的算法第4版中的左斜红黑树".我花了几天的时间来尝试理解deleteMin，以此作为对delete的热身，这是我最后一个关于deleteMin的问题.

I'm reading Left Leaning Red Black Tree in algorithms 4th edition, by Robert Sedgewick. I spent several days trying to understand the deleteMin as a warmup to understanding delete and this is my final question in my head about deleteMin.

    public void deleteMin()
    {
        root = deleteMin(root);
        root.color = BLACK;
    }
    private Node deleteMin(Node h)
    {
        if (h.left == null) return null;
        if (!isRed(h.left) && !isRed(h.left.left))
            h = moveRedLeft(h);
        h.left = deleteMin(h.left);
        return fixUp(h);
    }

当h.left和h.left.left均为黑色时，调用h = moveRedLeft(h);
问题是，如何确定如图所示，节点b是红色?

when h.left and h.left.left are both black, call h=moveRedLeft(h);
The question is, how can we assert that the node b is red, as the picture shows?

推荐答案

问题是我们如何断言节点b是红色的?

答案很简单，我们不.在 moveRedLeft 中，我们只需检查条件即可.

The answer is simply we don't. In moveRedLeft, we simply check for the condition.

请参阅第7页，此处.我们有以下代码:

Referring to the paper here, on page 7, we have the following code:

private Node moveRedLeft(Node h)
{
  colorFlip(h);
  if (isRed(h.right.left))
  {
    h.right = rotateRight(h.right);
    h = rotateLeft(h);
    colorFlip(h);
  }
  return h;
}

很明显，第四行检查 b 是否为红色.

Obviously, the 4th line checks if b is red.

这篇关于deleteMin左倾斜红黑树需要更多说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！