将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树转换为红色黑树

回答

相关问题