將AVL樹轉換爲紅色黑樹

我在某處讀取此語句時，可以將任何AVL樹T的節點着色爲「紅色」和「黑色」，以便T變成紅黑樹。將AVL樹轉換爲紅色黑樹

這個說法似乎很有說服力，但我不明白如何正式證明這一說法。

根據維基，A紅黑樹應該滿足這五個屬性：

A.A節點是紅色或黑色。 b。根部是黑色的。這條規則有時會被忽略。由於根始終可以從紅色變爲黑色，但不一定相反，

c。所有葉子（NIL）都是黑色的。

d。如果一個節點是紅色的，那麼它的兩個孩子都是黑色的。

e。從給定節點到其任何後代NIL節點的每條路徑都包含相同數量的黑色節點。

四個條件很簡單，我被困5

來源

2015-12-12 Geek_To_Learn

首先，定義一個樹的高度（如用於AVL樹）：

height(leaf) = 1 
height(node) = 1 + max(height(node.left), height(node.right))

此外，定義路徑的深度（如用於紅黑樹，一個路徑是從給定節點到某些葉子的後代鏈）是路徑上黑色節點的數量。

正如你指出，關於着色AVL樹作爲紅黑樹的棘手位是確保每個路徑具有相同的深度。您將需要使用AVL不變量：任何給定節點的子樹可以在高度上相差最多一個。

直觀地說，訣竅是使用一種着色算法，其深度對於給定的高度是可預測的，這樣就不需要做任何進一步的全局協調。然後，您可以在本地調整顏色，以確保每個節點的孩子具有相同的深度;這僅僅是因爲AVL條件對其高度差造成嚴格的限制。

此樹着色算法的伎倆：

color_black(x): 
    x.color = black; 
    if x is a node: 
    color_children(x.left, x.right) 

color_red(x): // height(x) must be even 
    x.color = red 
    color_children(x.left, x.right) // x will always be a node 

color_children(a,b): 
    if height(a) < height(b) or height(a) is odd: 
    color_black(a) 
    else: 
    color_red(a) 
    if height(b) < height(a) or height(b) is odd: 
    color_black(b) 
    else: 
    color_red(b)

對於AVL樹的根，呼叫color_black(root)確保灣請注意，該樹以深度優先順序遍歷，也確保了。

請注意，紅色節點都有高度。樹葉高度爲1，所以它們會被染成黑色，確保c。紅色節點的孩子要麼有奇數的高度，要麼會比他們的兄弟姐妹短，並且將被標記爲黑色，確保d。

最後，顯示e。（即從根的所有路徑具有相同的深度），使用感應上n>=1證明：

對於奇數height = 2*n-1，
- COLOR_BLACK（）創建一個紅黑樹，具有深度n
甚至height = 2*n，
- COLOR_RED（）將所有的路徑深度n
- COLOR_BLACK（）創建一個紅 - 黑樹深度n+1

基地情況下，用於n = 1：

對於奇數height = 1，樹是葉;
- color_black（）將葉子設置爲黑色;唯一的路徑有深度1
對於偶數height = 2，根是一個節點，並且兩個孩子都是樹葉，如上所示標記爲黑色;
- color_red（）將節點設置爲紅色;兩個路徑都具有深度1
- color_black（）將節點設置爲黑色;兩個路徑具有深度2

的感應步驟是在這裏我們使用的AVL不變：同級樹可以通過至多1的高度不同。對於具有給定height一個節點：

子情形答：兩個子樹是(height-1)
子情形B：一個子樹是(height-1)，並且另一個是(height-2)

感應步驟：給定的假說是對於n爲真，表明它適用於n+1：

奇數height = 2*(n+1)-1 = 2*n+1,

子情形答：兩個子樹甚至已經高度2*n
- color_children（）調用COLOR_RED（）爲兒童，通過歸納假設
- ，兩個孩子有深入n
- 父，COLOR_BLACK（）添加黑節點，深度爲n+1
子情況B：子樹有高度2*n和2*n-1
- color_children（）調用color_red（）和color_black（），resp;
- 甚至高度2*n，COLOR_RED（）產生深度n（感應HYP。）
- 對於奇數高度2*n-1，COLOR_BLACK（）產生深度n（感應HYP。）
- 父，COLOR_BLACK（）增加了一個黑色節點，用於深度n+1

即使height = 2*(n+1) = 2*n + 2

子情形答：兩個子樹具有奇數高度2*n+1 = 2*(n+1)-1
- color_children（）爲兩個孩子調用color_black（），深度爲n+1
- 從奇數高度情況下的上方，兩個孩子具有深度n+1
- 父，COLOR_RED（）增加了一個紅色節點，對於不變深度n+1
- 父，COLOR_BLACK（）增加了一個黑色節點，用於深度n+2
子情形B：子樹有高度2*n+1 = 2*(n+1)-1和2*n
- color_children（）調用COLOR_BLACK（）爲兒童，深度n+1
- 對於奇數高度2*n+1，COLOR_BLACK（）產生深度n+1（見上文）
- 甚至高度2*n，COLOR_BLACK（）產生深度n+1（感應HYP。）
- 父，COLOR_RED（）增加了一個紅色節點，深度n+1
- 父，COLOR_BLACK（）增加了一個黑色節點，深度n+2 = (n+1)+1

來源

2015-12-12 20:36:09 comingstorm

嘛聲明如何證明，對＃5個簡單的例子是一個單一的後代，這是葉，這爲黑色＃3。

否則，後代節點是紅色的，它需要＃4有2個黑色後代。

然後這兩種情況遞歸地應用在每個節點上，所以每個路徑中總是有相同數量的黑色節點。

來源

2015-12-12 06:09:20

你在哪裏使用AVL不變？ – comingstorm

@comingstorm - OP不需要知道*如何*轉換 –

將AVL樹轉換爲紅色黑樹

回答

相關問題