弄了很久，学习过程中觉得很难，但学完了，其实感觉也就那样，就是情况多了些。

首先是插入，插入的时候其实也就3种情况，因为只有当插入的节点的父亲是红色的时候，此时红黑树的性质遭到破坏，需要旋转，再分1.叔父节点为红，此时只要改变颜色，但祖父节点颜色的改变可能会破坏红黑树的性质，所以要node = grandparent，继续向上，叔父为黑，这时需要旋转，所以得判断，自身的位置，也就是自己和父亲分别是左孩子还是右孩子，2.如果自身是右，父亲是左，的先把自己也旋转到左，再和自己是左，父亲也是左的情况一起处理，即再进行一次旋转，旋转其实只要是为了满足根节点到叶子节点的黑色节点数这一性质（其实是在减小树的深度），颜色的改变一是配合旋转，二是满足些别的性质，3.自身是左，而父亲是右也就是差不多的了。

另外就是删除，删除就很麻烦一些了，首先是要找到要删除节点的右孩子的最左儿子（左右儿子都存在的情况下）来替代，左儿子不存在直接用右儿子替代，右儿子不存在直接用左儿子替代，都不存在则用空节点替代，另外记录下替代节点的孩子和替代节点的父亲（如果删除节点只有一个孩子，替代节点的孩子就是替代节点），然后把孩子指向父亲，只记一个node是不行的，因为node可能为空，当替代点的颜色是黑色的话，需要另外平衡，平衡中如果替代节点的孩子是红色，直接改成黑色就OK了（因为之前只是少了个黑色节点，而红改黑除了改变黑色节点的个数外是不改变别的性质的），当替代节点孩子是黑色时，再分其兄弟节点的颜色1.兄弟节点是红色，此时改变颜色，单步旋转（因为兄弟节点所在的枝黑色节点只比另一边多一）；然后如果兄弟节点是黑色2.兄弟节点的两个孩子也是黑色或者是空，此时只需改变颜色，但父亲颜色的改变可能会破坏树的性质则node = grandparent，向上继续传，来平衡3.兄弟节点有一个红，此时又得确定位置，父亲是左孩子，而自己是右孩子黑色或空，又得先把黑色的旋转到和父亲相同的相对位置，4然后转到父亲和自己都是左孩子情况，一步旋转。父亲是右孩子的情况也一样。

 

自己写上面的删除和插入的时候自己都感觉晕晕的，感觉了解的还不是很彻底，改天得再写一遍。。。

#include 
      
       #include 
       
        using namespace std;#define red 0#define black 1template 
        
         class  red_black_node{    public:    red_black_node* left;    red_black_node* right;    red_black_node* parent;    T key;    int color;    red_black_node(T value):left(NULL),right(NULL),parent(NULL),color(red),key(value){};    red_black_node(T value,red_black_node* l,red_black_node* r,red_black_node* p):        left(l),right(r),parent(p),T(value),color(red){};};template 
         
          class red_black_tree{public:   red_black_node
          
           * mRoot;//根节点public:    red_black_tree();    ~red_black_tree();    void Destory(red_black_node
           
            * Pnode); red_black_node
            
             * RotateLeft(red_black_node
             
              * p,red_black_node
              
               * r); red_black_node
               
                * RotateRight(red_black_node
                
                 * p,red_black_node
                 
                  * r); red_black_node
                  
                   * Insert_into(T k,red_black_node
                   
                    * root); void Insert(T k); red_black_node
                    
                     * Search(T k,red_black_node
                     
                      * root); red_black_node
                      
                       * Insert_balance(red_black_node
                       
                        * node,red_black_node
                        
                         * root); void Travel_it(red_black_node
                         
                           *root); void Trave(); red_black_node
                          
                           * Delete_Replace(T k,red_black_node
                           
                            * root); void Delete(T k); red_black_node
                            
                             * Delete_balance(red_black_node
                             
                              * child,red_black_node
                              
                               * parent,red_black_node
                               
                                * root);};//左旋函数，并未改变颜色template 
                                
                                 red_black_node
                                 
                                  * red_black_tree
                                  
                                   ::RotateLeft(red_black_node
                                   
                                    * node,red_black_node
                                    
                                     * root){ red_black_node
                                     
                                      * tem = node->left; node->left = tem->right; tem->right = node; tem->parent = node->parent; node->parent = tem; if(node->left!=NULL) node->left->parent = node; if(tem->parent==NULL) { root = tem; } else { if(tem->key > tem->parent->key) { tem->parent->right = tem; } else { tem->parent->left = tem; } } return root;}//构造函数template 
                                      
                                       red_black_tree
                                       
                                        ::red_black_tree(){ mRoot = NULL;}//析构函数template 
                                        
                                         red_black_tree
                                         
                                          ::~red_black_tree(){ Destory(mRoot);}//单步右旋template 
                                          
                                           red_black_node
                                           
                                            * red_black_tree
                                            
                                             ::RotateRight(red_black_node
                                             
                                              * node,red_black_node
                                              
                                               * root){ red_black_node
                                               
                                                * tem = node->right; node->right = tem->left; tem->left = node; tem->parent = node->parent; node->parent = tem; if(node->right!=NULL) node->right->parent = node; if(tem->parent==NULL) { root = tem; } else { if(tem->parent->key > tem->key) { tem->parent->left = tem; //red_black_tree
                                                
                                                 ::Travel_it(root); } else { tem->parent->right = tem; } } return root;}//销毁红黑树template 
                                                 
                                                  void red_black_tree
                                                  
                                                   ::Destory(red_black_node
                                                   
                                                    * PnodeHeader){ if(PnodeHeader==NULL) return ; if(PnodeHeader->left!=NULL) Destory(PnodeHeader->left); if(PnodeHeader->right!=NULL) Destory(PnodeHeader->right); delete PnodeHeader;}template 
                                                    
                                                     void red_black_tree
                                                     
                                                      ::Insert(T k){ mRoot = Insert_into(k,mRoot);}template 
                                                      
                                                       //返回的是自己或者是自己的父亲red_black_node
                                                       
                                                        * red_black_tree
                                                        
                                                         ::Search(T k,red_black_node
                                                         
                                                          * root){ red_black_node
                                                          
                                                           * tem = root; if(tem==NULL)return NULL; while(true) { if(k
                                                           
                                                            key) { if(tem->left==NULL)return tem; else tem = tem->left; } else if(k>tem->key) { if(tem->right==NULL)return tem; else tem = tem->right; } else return tem; }}template 
                                                            
                                                             red_black_node
                                                             
                                                              * red_black_tree
                                                              
                                                               ::Insert_into(T k,red_black_node
                                                               
                                                                * root){ red_black_node
                                                                
                                                                 * node; red_black_node
                                                                 
                                                                  * tem = Search(k,root); //if(tem->key==k)return root;//重复直接退出 node = new red_black_node
                                                                  
                                                                   (k); node->parent = tem; if(tem) { if(tem->key > k) { tem->left = node; } else { tem->right = node; } } else { root = node; } //red_black_tree
                                                                   
                                                                    ::Trave(); return Insert_balance(node,root);}template
                                                                    
                                                                     red_black_node
                                                                     
                                                                      * red_black_tree
                                                                      
                                                                       ::Insert_balance(red_black_node
                                                                       
                                                                        * node,red_black_node
                                                                        
                                                                          *root){ red_black_node
                                                                         
                                                                           *p,*gp,*uncle,*tem; while((p=node->parent)&&p->color==red) { gp = p->parent; if(p==gp->left) { uncle = gp->right; if(uncle&&uncle->color==red)//1.父亲节点和叔父节点都为红 { uncle->color = black;// p->color = black; gp->color = red; node = gp; } else { if(p->right==node)//2.叔父节点为黑，或者不存在，自己是右孩子，父亲是左孩子 { root = RotateRight(p,root); tem = p; p = node; node = tem; } p->color = black; gp->color = red; root = RotateLeft(gp,root); } } else { uncle = gp->left; if(uncle&&uncle->color==red) { uncle->color = black; p->color = black; gp->color = red; node = gp; } else { if(p->left==node) { root = RotateLeft(p,root); tem = p; p = node; node = tem; } p->color = black; gp->color = red; root = RotateRight(gp,root); } } } root->color = black; return root;}//打印函数template 
                                                                          
                                                                           void red_black_tree
                                                                           
                                                                            ::Travel_it(red_black_node
                                                                            
                                                                              *root){ if(root==NULL)return; printf("father is:%d",root->key); if(root->color==red)printf("(red)"); else printf("(black)"); printf(" left:"); if(root->left==NULL)printf("NULL"); else { printf("%d",root->left->key); if(root->left->color==red)printf("(red)"); else printf("(black)"); } printf(" right:"); if(root->right==NULL)printf("NULL\n"); else { printf("%d",root->right->key); if(root->right->color==red)printf("(red)\n"); else printf("(black)\n"); } Travel_it(root->left); Travel_it(root->right);}template 
                                                                             
                                                                              void red_black_tree
                                                                              
                                                                               ::Trave(){ Travel_it(mRoot);}template 
                                                                               
                                                                                //左右子树都不空时用右孩子的最左子树来替代，左子树为空，直接用右孩子替代，右子树为空直接用左孩子替代red_black_node
                                                                                
                                                                                 * red_black_tree
                                                                                 
                                                                                  ::Delete_Replace(T k,red_black_node
                                                                                  
                                                                                   * root){ red_black_node
                                                                                   
                                                                                     *tem; tem = red_black_tree
                                                                                    
                                                                                     ::Search(k,mRoot); if(tem==NULL)return mRoot; if(tem->key!=k) { printf("The Key Is Wrong\r\n"); return mRoot; } red_black_node
                                                                                     
                                                                                      * aim = tem; red_black_node
                                                                                      
                                                                                       * replace_parent; red_black_node
                                                                                       
                                                                                        * replace_child; int color; if(tem->left&&tem->right) { tem = tem->right; while(tem->left!=NULL) { tem = tem->left; } replace_parent = tem->parent; replace_child = tem->right; color = tem->color; if(replace_child) { replace_child->parent = replace_parent; } if(replace_parent) { if(tem->key < replace_parent->key) { replace_parent->left = replace_child; } else { replace_parent->right = replace_child; } } else//?? { root = replace_child; } //?? if (tem->parent == aim) { replace_parent = tem; } tem->parent = aim->parent; tem->left = aim->left; tem->right = aim->right; tem->color = aim->color; if(aim->parent) { if(tem->key < aim->parent->key) { tem->parent->left = tem; } else { tem->parent->right = tem; } } else { root = tem; } aim->left->parent = tem; if(aim->right) { aim->right->parent = tem; } } else { if(!tem->left) { replace_child = tem->right; } else if(!tem->right) { replace_child = tem->left; } replace_parent = tem->parent; color = tem->color; if(replace_child) { replace_child->parent = replace_parent; } if(replace_parent) { if(replace_parent->left==tem) { replace_parent->left = replace_child; } else { replace_parent->right = replace_child; } } else { root = replace_child; } } delete aim; if(color==black) { root = Delete_balance(replace_child,replace_parent,root); } return root;}template 
                                                                                        
                                                                                         void red_black_tree
                                                                                         
                                                                                          ::Delete(T k){ mRoot = Delete_Replace(k,mRoot);}template 
                                                                                          
                                                                                           //替代的节点是黑色时的旋转平衡red_black_node
                                                                                           
                                                                                            * red_black_tree
                                                                                            
                                                                                             ::Delete_balance(red_black_node
                                                                                             
                                                                                              * child,red_black_node
                                                                                              
                                                                                               * parent,red_black_node
                                                                                               
                                                                                                * root){ red_black_node
                                                                                                
                                                                                                  *other, *o_left, *o_right; while((!child||child->color==black)&&child!=root) { if(parent->left==child)//是左孩子，只能是，之前用删除节点的左孩子替代 { other = parent->right; if(other->color==red) { other->color = black;//兄弟节点是红色 parent->color = red; root = RotateRight(parent,root);//旋转下即可 other = parent->right; } //x的兄弟是黑色的，且两个孩子也是黑色的 if ((!other->left || other->left->color == black) && (!other->right || other->right->color == black)) { other->color = red; child = parent; parent = child->parent; } else { if(!other->right||other->right->color==black) { if(o_left = other->left) { o_left->color = black; } other->color = black; root = RotateLeft(other,root); other = parent->right; } //x的兄弟是黑色的 other->color = parent->color; parent->color = black; if(other->right) { other->right->color = black; } root = RotateRight(parent,root); child = root; break; } } else { other = parent->left; if(other->color==red) { other->color = black; parent->color = red; root = RotateLeft(parent,root); other = parent->left; } if((!other->left||other->left->color==black)&&(!other->right||other->right->color==black)) { other->color = red; child = parent; parent = child->parent; } else { if(!other->left||other->left->color==black) { if(o_right = other->right) { o_right->color = black; } other->color = red; root = RotateRight(other,root); other = parent->left; } other->color = parent->color; parent->color = black; if(other->left) { other->left->color = black; } root = RotateLeft(parent,root); child = root; break; } } } if(child) { child->color = black; } return root;}int main(){ int a[] = { 15,7,10,9,4,5,8,20,1,6}; red_black_tree
                                                                                                 
                                                                                                  * tree = new red_black_tree
                                                                                                  
                                                                                                   (); red_black_node
                                                                                                   
                                                                                                     *root = NULL; for(int i=0;i
                                                                                                    
                                                                                                     Insert(a[i]); //tree->Find_parent(); // tree->Trave(); // getchar(); } tree->Trave(); printf("\n"); for(int i=0;i
                                                                                                     
                                                                                                      Delete(a[i]); tree->Trave(); getchar(); } return 0;}