算法11---红黑树的实现

1 #include 
     
        2 using namespace std;  3 #define BLACK 0  4 #define RED 1  5 #define Nil -1  6 #define LEN sizeof(struct Tree)  7 struct Tree  8 {  9    struct Tree*left; 10    struct Tree*right; 11    struct Tree*parent; 12    int key; 13    int color; 14 }; 15  16 struct Tree *root=NULL; 17 struct Tree *nil=NULL; 18 void LEFT_ROTATE(struct Tree*x) 19 {
   //左旋转：分三个步骤①②③来叙述旋转代码的。 20   struct Tree*y=x->right;//设置y结点。 21   x->right=y->left;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。① 22   if(y->left!=nil) 23   { 24        y->left->parent=x; 25   } 26   y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。② 27   if(x->parent==nil) 28   { 29        root=y; 30   } 31   else if(x==x->parent->left) 32   { 33        x->parent->left=y; 34   } 35   else x->parent->right=y; 36   y->left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③ 37   x->parent=y; 38 } 39 void RIGHT_ROTATE(struct Tree*x) 40 {
   //右旋转：分三个步骤①②③来叙述旋转代码的。 41   struct Tree*y=x->left;//设置y结点。 42   x->left=y->right;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。① 43   if(y->right!=nil) 44   { 45     y->right->parent=x; 46   } 47   y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。② 48   if(x->parent==nil) 49   { 50     root=y; 51   } 52   else if(x==x->parent->right) 53   { 54     x->parent->right=y; 55   } 56   else x->parent->left=y; 57   y->right=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③ 58   x->parent=y; 59 } 60 void RB_INSERT_INSERT_FIXUP(struct Tree*z) 61 { 62    while (z->parent->color==RED) 63    { 64      if (z->parent==z->parent->parent->left) 65      { 66        struct Tree*y=z->parent->parent->right;//叔结点 67        if (y->color==RED)//情况一：叔结点为红色 68        {
   //给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题 69          z->parent->color=BLACK; 70          y->color=BLACK; 71          z->parent->parent->color=RED; 72          z=z->parent->parent;//把z的祖父结点当成新结点z进入下一次循环 73        } 74        else 75        { 76          if (z==z->parent->right)//情况二：检查z是否是一个右孩子且叔结点为黑色，前提是p1结点不是叶子结点 77          {
   //使用一个左旋让情况2转变为情况3 78            z=z->parent; 79            LEFT_ROTATE(z);//由于进入if语句后可知旋转结点不可能是叶子结点，这样就不用判断z是否是叶子结点了。 80          } 81                z->parent->color=BLACK;//情况三：是z是一个左孩子且叔结点为黑色，改变z的父和祖父结点颜色并做一次右旋，以保持性质5 82          z->parent->parent->color=RED; 83          RIGHT_ROTATE(z->parent->parent);//由于p2可能是叶子结点，所以最好还是用一个if判断 84        } 85      } 86      else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。 87      { 88        struct Tree*y=z->parent->parent->left; 89        if (y->color==RED) 90        { 91          z->parent->color=BLACK; 92          y->color=BLACK; 93          z->parent->parent->color=RED; 94          z=z->parent->parent; 95        } 96        else 97        { 98          if (z==z->parent->left) 99          {100            z=z->parent;101            RIGHT_ROTATE(z);102          }103                z->parent->color=BLACK;104          z->parent->parent->color=RED;105          LEFT_ROTATE(z->parent->parent);106        }107      }108    }109    root->color=BLACK;//最后给根结点着为黑色。110 }111 void RB_INSERT(struct Tree*z)112 {113   struct Tree*y=nil;114   struct Tree*x=root;115   while (x!=nil)116   {117     y=x;118     if (z->key
      
       key)119     {120       x=x->left;121     }122     else x=x->right;123   }124   z->parent=y;125   if (y==nil)126   {127     root=z;128   }129   else if(z->key
       
        key)130   {131     y->left=z;132   }133   else y->right=z;134   z->left=nil;//给插入结点左右孩子赋值为空。135   z->right=nil;136   z->color=RED;//给插入结点着为红色。137   RB_INSERT_INSERT_FIXUP(z);138 }139 void RB_TRANSPLANT(struct Tree*u,struct Tree*v)140 {141   if (u->parent==nil)142     root=v;143   else if(u==u->parent->left)144     u->parent->left=v;145   else u->parent->right=v;146   v->parent=u->parent;147 }148 //非递归版本的查找二叉查找树的最小值149 struct Tree*ITERATIVE_TREE_MINIMUM(struct Tree*x)150 {151   while (x->left!=nil)152   {153     x=x->left;154   }155   return x;156 }157 //非递归版本的二叉查找树查找函数158 struct Tree*ITERATIVE_TREE_SEARCH(struct Tree*x,int k)159 {160   while (x!=nil&&k!=x->key)161   {162     if (k
        
         key)163     {164       x=x->left;165     }166     else x=x->right;167   }168   return x;169 }170 void RB_DELETE_FIXUP(struct Tree*x)171 {172    struct Tree*w=NULL;//w是x的兄弟结点173      while (x!=root&&x->color==BLACK)//如果x是黑色并且不是根结点，才进行循环。174      {
   //x是一个具有双重颜色的结点，调整的目的是把x的黑色属性向上移动。175      if (x==x->parent->left)176      {177        w=x->parent->right;178        if (w->color==RED)//情况一：x的兄弟结点w是红色的。179        {
   //改变w和x.p的颜色+一次旋转使其变为情况二，三，四。180          w->color=BLACK;181          x->parent->color=RED;182          LEFT_ROTATE(x->parent);183          w=x->parent->right;184        }185        if (w->left->color==BLACK&&w->right->color==BLACK)//情况二：x的兄弟结点w是黑色的，而且w的两个子节点都是黑色。186        {187          w->color=RED;//从x和w上去掉一重黑色。x还是黑色，而w变为红色。188          x=x->parent;//x结点向上移动成为新的待调整结点。189        }190        else191        {192          if (w->right->color==BLACK)//情况三：x的兄弟结点w是黑色的，w的左孩子是红色的，w的右孩子是黑色的。193          {
   //交换w和w.left的颜色+旋转使其转变为情况四。194            w->left->color=BLACK;195            w->color=RED;196            RIGHT_ROTATE(w);197            w=x->parent->right;198          }199          w->color=x->parent->color;//以下是情况四：x的兄弟结点w是黑色的，且w的右孩子是红色的。200          x->parent->color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。201          w->right->color=BLACK;202          LEFT_ROTATE(x->parent);203          x=root;//x成为根结点，结束循环。204        }205      }206      else//以下和上面的if分支类似，不做累述。207      {208              w=x->parent->left;209        if (w->color==RED)210        {211          w->color=BLACK;212          x->parent->color=RED;213          RIGHT_ROTATE(x->parent);214          w=x->parent->left;215        }216        if (w->left->color==BLACK&&w->right->color==BLACK)217        {218          w->color=RED;219          x=x->parent;220        }221        else222        {223          if (w->left->color==BLACK)224          {225            w->right->color=BLACK;226            w->color=RED;227            LEFT_ROTATE(w);228            w=x->parent->left;229          }230          w->color=x->parent->color;231          x->parent->color=BLACK;232          w->left->color=BLACK;233          RIGHT_ROTATE(x->parent);234          x=root;235        }236      }237      }x->color=BLACK;238 }239 void RB_DELETE(struct Tree*z)240 {241     struct Tree*y=z,*x;//y为待删除或待移动结点242   int y_original_color=y->color;//保存y的原始颜色，为做最后的调整做准备。243   if (z->left==nil)244   {245     x=z->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上246     RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。247   }248   else if (z->right==nil)249   {250     x=z->left;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上251     RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。252   }253   else254   {255     y=ITERATIVE_TREE_MINIMUM(z->right);//找到z.right的后继。256         y_original_color=y->color;//y的新的原始结点被重置。257     x=y->right;//x指向y的唯一子结点或者是叶子结点，保存x的踪迹使其移动到y的原始位置上258     if (y->parent==z)259     {260       x->parent=y;//由于z的父结点是要删除的结点，所以不能指向它，于是指向y261     }262     else263     {264       RB_TRANSPLANT(y,y->right);//把以y.right为根的子树替换以y为根的子树。265       y->right=z->right;266       y->right->parent=y;267     }268     RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。269     y->left=z->left;270     y->left->parent=y;271     y->color=z->color;//把已经删除的结点颜色赋值给y，保证了y以上的树结构红黑性质不变。272   }273   if(y_original_color==BLACK) //y的原始颜色为黑色，说明需要调整红黑颜色。274     RB_DELETE_FIXUP(x);275 }276 //中序遍历277 void InOderTraverse(struct Tree *p)278 {279     if (p!=nil)280   {   281     InOderTraverse(p->left);282     cout<
         
          key<<" "<
          
           color<<" "<
           
            right);284 }285 }286 void main()287 {288 int array1[6] = { 41, 38, 31, 12, 19, 8}; 289 nil=new struct Tree[LEN];290 nil->key=Nil;nil->color=BLACK;291 root=nil;292 int i=0;293 struct Tree*ROOT=new struct Tree[LEN];294 ROOT->key=array1[i++];295 RB_INSERT(ROOT);296 root=ROOT;297 while (i!=6)298 {299 struct Tree*z=new struct Tree[LEN];300 z->key=array1[i];301 RB_INSERT(z);302 i++;303 }304 InOderTraverse(root);305 cout<