在紅黑樹中的左旋轉

我一直在瀏覽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

在紅黑樹中的左旋轉

回答

相關問題