在红黑树中的左旋转

我一直在浏览Robert Sedgewick算法中描述的红黑树。这里是插入红黑树的代码。在红黑树中的左旋转

public void put(Key key, Value val) { 
    root = put(root, key, val); 
    root.color = BLACK; 
    assert check(); 
} 

// insert the key-value pair in the subtree rooted at h 
private Node put(Node h, Key key, Value val) { 
    if (h == null) return new Node(key, val, RED, 1); 

    int cmp = key.compareTo(h.key); 
    if  (cmp < 0) h.left = put(h.left, key, val); 
    else if (cmp > 0) h.right = put(h.right, key, val); 
    else    h.val = val; 

    // fix-up any right-leaning links 
    if (isRed(h.right) && !isRed(h.left))  h = rotateLeft(h); 
    if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); 
    if (isRed(h.left) && isRed(h.right))  flipColors(h); 
    h.N = size(h.left) + size(h.right) + 1; 

    return h; 
}

这是一张图像，用于可视化红色黑色修正。 redblackvisualization 考虑这种情况，当要插入的项目位于顶部3节点的中间时。我们必须执行三个操作，分别为h=rotateLeft(h),h=rotateRight(h)和flipcolors(h)。问题是，当我们分配h = rotateLeft(h)。返回的节点是指向两个连续的左侧红色链接的三个节点中的中间节点的指针。但算法假定返回的节点是3个节点中具有2个连续左侧红色链接的最高节点。所以，当我们再次rotateRight(h)时，我们最终以同样的立场开始。可能是我没有理解这个算法。

这里是rotateLeft(h)

private Node rotateLeft(Node h) { 
    assert (h != null) && isRed(h.right); 
    Node x = h.right; 
    h.right = x.left; 
    x.left = h; 
    x.color = x.left.color; 
    x.left.color = RED; 
    x.N = h.N; 
    h.N = size(h.left) + size(h.right) + 1; 
    return x; 
}

代码请帮助我了解如何h=rotateLeft(h)给出了顶级节点，而不是在三个节点有两个连续的红色左链接的中间节点。

来源

2013-10-31 Shikhar Subedi

您可能会将图像裁剪为*只显示可视化效果，除非文字显着。 – Dukeling

文字不重要。我会裁剪图像。 –

我终于明白算法是如何工作的。在h=rotateLeft(h)之后，第二个和第三个if statements评估为false。并返回h。一级递归，我们得到h.left =h其中h在等号的左边，是三个节点中的顶级节点，连续两个红色的左边链接。然后，第一个if语句的计算结果为false，第二个if语句的计算结果为true，我们执行右旋转操作，然后执行翻转色。

如果我错了，请纠正我。

来源

2013-10-31 09:52:58

在红黑树中的左旋转

回答

相关问题