理解红黑树（2）

830阅读　0评论2013-10-27　embeddedlwp
分类：C/C++

上篇地址：http://blog.chinaunix.net/uid-27767798-id-3339483.html

继续上篇红黑树的分析，这次是树节点删除的分析

普通二叉树节点删除过程：

普通二叉数节点删除过程分为2种情况（删除target节点）：

case1这种情况就是target节点只有一个孩子，无论只有左孩子，还是只有右孩子，在这种情况下删除target节点，这种情况比较简单，就是直接删除target节点，然后重新把parent节点和child节点的父子关系设置好即可

case2中，需要删除的节点target，即有左孩子，又有右孩子，所以按照case1的做法不可取，两个节点不能同时作为parent节点的子节点，所以这时需要寻找一个节点代替target节点，显而易见，这个节点要比parent节点要大，所以结果应该在parent的右子树数中，也就是target节点的左右子树中，同时还有满足两个条件中的任意一个：

1.这个节点的值要要等于c2节点子树的最小值

2.这个节点的值要要等于c1节点子树的最大值

所以这时候可以选择c2子树中最小的replace节点，或者为c1右孩子中最大的那个节点。

这时找到了这个节点，同时这个节点肯定只有一个孩子，如果是target节点的右孩子中的最小值，那么这个最小值节点肯定是没有左孩子的;如果这个节点是target节点中的左孩子中的最大值，那么这个最大值节点是肯定没有右孩子的。找到了这个代替的节点replace节点之后，需要把这个节点删除掉，同时把replace节点的值和target节点的值做个交换，这样target节点就这样间接的删除了

红黑树删除节点后的影响：

第一种情况删除target节点之后，没有任何影响，直接删除，因为target节点是红色的删除不会影响节点到叶子节点黑色节点的数量，同时parent节点和child节点肯定都是黑色的，也不会影响到parent节点和child节点连接导致红色节点相邻。

第二种情况parent节点的颜色任意，但是target节点为黑色，同时child节点为红色，这种情况下删除target节点后，只需要将child节点染为黑色，就可弥补target节点的删除导致的parent左孩子黑色节点少1的情况，同时child的变黑也不影响parent节点的颜色（parent节点颜色可以为红色也可以为黑色）。

第三种情况target节点为黑色，child节点为黑色，这时删除了target节点，很明显parent左子树少了一个黑色节点，不满足红黑树的性质（到任何叶子节点黑色节点数量相同），这时需要协调一下parent右子树和左子树结构，使得黑色节点数量重新平衡一致，而且不出现相邻的红色节点。

节点删除code：

  1. delete(node *target){
  2.   node *delete;
  3.   if(target->left==NULL||target->right==NULL){
  4.       delete=target; //case1
  5.   }else{
  6.       delete=successor(target); //case2
  7.   }
  8.   node *x;
  9.   if(delete->left!=NULL)
  10.       x=delete->left; //设置父子节点关系
  11.   else
  12.       x=delete->right;
  13.   if(delete->parent==NULL)
  14.       root=x;
  15.   x->parent=delete->parent;
  16.   if(delete->parent->left==delete)
  17.       delete->parent->left=x;
  18.   else
  19.       delete->parent->right=x;
  20.   if(target!=delete){
  21.       target->value=delete->value; //更新颜色和值
  22.       target->color=delete->color;
  23.    }
  24.    if(delete->color==1)
  25.       deleteAdjust(x); //协调parent节点左右子树的颜色和位置，重新满足红黑树性质
  26.  }

红黑树节点调整分为4种情况，情况如图case1中，在A节点和B节点中间原来存在被删除的节点，这个节点颜色是黑色的，删除这个节点会导致B节点的左子树黑色节点数量少1,同时单单调整B的左子树的节点颜色是不能保持红黑树性质。这时需要整体调整一下B节点左右子树的结构，B节点左子树黑色节点数量少1,可以采取的方法不外乎两种：

1.在B左子树黑色节点数量不变的情况下，调整B右子树黑色节点数量少1，这种方法需要递归B节点的父节点及其以上的数据结构

2.我们会发现在B左子树的结构中，让左子树的黑色节点数量增加一个已经是不可能，所以可以通过左旋转B节点，让左子树的节点多一个，这样就有机会将这个节点置为黑色，重新保持红黑色性质

节点调整会分为4种情况


case1这种情况，当前的情况是B节点的左子树黑色节点数量少1,右子树有红色节点，如果采用方法1不可能，D节点已经为红色，无论更改C，E节点的颜色都会破坏红黑树性质（无相邻红色节点），只能采取第二种做法，左旋B节点，同时将D节点（叔父节点）变为黑色，B节点变为红色，这样保持红黑树的性质，D节点的右子树黑色节点数目2个，同时左子树中DBC分支中黑色节点数目也是2个，现在问题变为了B节点的左子树黑色节点的数目和右子树黑色节点数目相同,然后进入case2


case2中，A节点和B节点之间删除了黑色节点，使得A节点的左子树黑色节点数量少1,A节点的颜色可以任意，这时盲目改变A节点的颜色不可取。这时可以采用方法1,就是使得A节点右子树黑色节点数量少一个，可以改变C节点（叔父节点）的颜色，变为红色，不可将DE节点全都变为红色，这样会影响DE的子节点，如果他们的子节点中右红色的，这样会违反红黑树性质（不能有相邻的红色节点）。这样A节点变为黑色，C节点变为红色，这样A节点左右子树黑色节点数目相同了，但是对于A节点的父节点，认为A这一子树整体黑色节点数目少了一个，所以这种情况需要递归A的父节点结构。

case3中，这种情况下，如果用解决方法1,就是让A节点右子树中黑色节点数量少一个，这样只能更新C节点的颜色为红色，这样D节点也为红色，CD节点为相邻的红色节点，违反了红黑树的性质。如果用解决方法2,让A节点的左子树黑色节点数量增加1个，如果不管A节点颜色，强行将A节点的颜色变为黑色，不但没有平衡，A的右子树黑色节点也会加1.所以只能左旋节点A，然后在根据情况重新对节点着色，试想，目标就是让A节点位置的节点的左子树黑色节点数量增加1个，左子树黑色节点数量不变，可以肯定的是A节点肯定要变为黑色，所以不用管D节点的颜色，这时如果E节点为黑色，这样导致了旋转过后C节点右子树的黑色节点数量加1,强行更新E节点的颜色为红色，又会导致它的子节点破坏红黑树性质，如果C节点的右子树为红色，就好办了，所以这时需要先右旋C，使得D位置节点的右孩子为红色。右旋C节点，C节点变为红色，D节点变为黑色，这样旋转完毕后，D节点的左右孩子继续保持红黑树性质，然后进入case4

case4中在A节点颜色任意，B节点为黑色，AB节点之间删除了一个黑色节点后，需要调整下数据结构，只需要A节点和C节点交换颜色即可，如图C节点的右子树的黑色节点数量不变，同时左子树结构多了一个黑色节点，弥补了删除的黑色节点。其中D节点颜色我们是不关心的，因为在A节点左旋后，D节点会成为A节点的右孩子，A节点会变为黑色，所以D节点颜色任意。

节点颜色调整的代码：


  1. void deleteAdjust(node * target){
  2.    while(target!=root&&target->color==1){
  3.       node* parent=target->parent;
  4.       if(target==parent->left){
  5.          node* uncle=parent->right;
  6.          if(uncle!=NULL&&uncle->color==0){
  7.             uncle->color=1;                                 //case1
  8.             parent->color=0;
  9.             rotateLeft(parent);
  10.             uncle=uncle->left;
  11.           }
  12.          if(uncle!=NULL&&uncle->left->color==1&&uncle->right->color==1){
  13.             uncle->color=0;                            //case2
  14.             target=target->parent;
  15.          }
  16.          else{
  17.              if (uncle!=NULL&&uncle->left->color==0){
  18.                   uncle->left->color=1;
  19.                   uncle->color=0;
  20.                   rotateRight(uncle);                  //case3
  21.                   uncle=target->parent->right;
  22.               }
  23.             uncle->color=target->parent->color;        //case4
  24.             parent->color=1;
  25.             uncle->right->color=1;
  26.             rotateLeft(parent);
  27.             target=root;
  28.          }
  29.       }else{
  30.          node* uncle=parent->left;
  31.          if(uncle!=NULL&&uncle->color==0){
  32.            uncle->color=1;
  33.            parent->color=0;
  34.            rotateRight(parent);
  35.            uncle=uncle->right;
  36.          }
  37.          if(uncle!=NULL&&uncle->right->color==1&&uncle->left->color==1){
  38.            uncle->color=0;
  39.            target=target->parent;
  40.          }
  41.          else{
  42.              if(uncle!=NULL&&uncle->right->color==0){
  43.                   uncle->right->color=1;
  44.                  uncle->color=0;
  45.                   rotateLeft(uncle);
  46.                   uncle=target->parent->left;
  47.              }
  48.              uncle->color=target->parent->color;
  49.              parent->color=1;
  50.              uncle->left->color=1;
  51.              rotateRight(parent);
  52.              target=root;
  53.          }
  54.       }
  55.      root->color=1;
  56.    }
  57.  }






上一篇：理解红黑树（1）
下一篇：二叉树的实现