确保从根到树叶节点的每条路径都具有相同数量的黑色节点 (C)

Question

我正在为大学目的实现一棵红黑树，我坚持属性从根到叶的每条路径都应该有相同数量的黑色节点。我已经插入了所有需要的功能：fixup, rotation, insertion...但我不知道如何处理这个功能。我在想类似的东西：

void checkNuberBlackNodes(struct node* root) {
    if( numberBlackNodes(root->right) > numberBlackNodes(root->left) {
         leftRotate(root);
         colorize(root);
    }
    else if( numberBlackNodes(root->right) < numberBlackNodes(root->left) {
         rightRotate(root);
         colorize(root);
    }
    else return; //no violation, same number of black nodes
}

想法是 insert 一个节点，fix up 违规，然后 checkNumberBlackNodes 在插入的新节点上（或从根）。我不知道如何处理这个过程，所有以前的功能都很容易实现，这是......我不知道如何开始。编辑：我有一个新想法：

void checkNuberBlackNodes(struct node* root) {
  int diff = height(root->right) - height(root->left);
  if ( diff >=2 ) //if the tree is too deep
  {
     leftRotate(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
  else if ( diff <= -2 ) //specular case
  { 
     rightRotate(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
  else if( blackHeight(root->right) > blackHeight(root->left) {
     colorize(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
else if( blackHeight(root->right) < blackHeight(root->left) {
     colorize(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
else return; //No violation
}

blackHeight是从节点到叶子的路径中黑色节点的数量；

Answer 1

如果向Red-Black树中插入一个新节点，则该节点始终是末尾的叶节点。而且总是红色。

一般

(1) 插入一个节点可能会违反“没有连续的红色节点”规则，修正将在根的方向。最多需要 2 次旋转和 3 * O(h/2) 次重新着色，其中 h 是树的高度。如果插入节点的parent为黑色，则无需修正。

(2) 删除节点可能会违反“从根向下每条路径的黑色节点数相同”的规则。同样，修复发生在根目录下。最多需要 3 次旋转和 O(h) 次重新着色，其中 h 是树的高度。

如果要删除的节点是没有children的根节点，则删除它。

如果要删除的Node有两个children，找到直接后继（向右child然后一直向左），交换Node和后继Node（但PRESERVE原来的节点的颜色）。后继节点将始终是 0-children 或 1-child 节点。现在你需要删除原来的节点但是在继承者的位置。您转到接下来的两个案例。

如果删除的节点是叶子节点，并且是红色的，不需要修复，删除节点

如果要删除的节点有一个child，是黑色，child是红色，删除节点，将节点替换为child，重新着色child 为黑色。

那么这留下了什么？它留下一个黑色节点是叶子节点，没有children，困难的情况。删除它会违反“从根向下每条路径的黑色节点数都相同”的规则。

删除节点后，parent 节点现在在树的一侧有黑色路径计数错误。基本上删除是一个 two-prong 策略：

a) 您检查 parent 节点、兄弟节点和兄弟节点 children 的节点，看看是否有红色节点。如果是的话，你可以使用旋转和重新着色来改变它，所以删除边上的黑洞会被重新填充，修复树。 b) 如果所有节点（或 NULL 节点）都是黑色的，那么你将兄弟节点设为红色，parent 节点现在被认为是修复树的点。你已经使树的两边都变得同样糟糕，现在修复点高了 1 级。您返回到步骤 a)，因为有“parent”、“sibling”和“sibling children”的新定义。 c) 有可能有一棵 red-black 树完全是黑色的。如果到达根并且没有遇到红色节点，会发生什么情况？然后它现在是一棵 red-black 树。实际上，changing siblings 在每条树路径中引入了 1 个红色节点，将黑色树的高度统一降低 1。

确保从根到树叶节点的每条路径都具有相同数量的黑色节点 (C)

Ensure every path from root to a tree leaf node has the same number of black nodes ( C )

c

tree

red-black-tree