红黑树(未修改，检验)C++-白红宇

红黑树(未修改，检验)C++

阅读量：6786 次

发布时间：2019-06-26

本文共 9970 字，大约阅读时间需要 33 分钟。

 #include 
    
     #include 
     
      using namespace std;

enum Color:int{Black, Red};

template
    
     class TreeNode{ public: Color color; T key; TreeNode* parent; TreeNode* left; TreeNode* right;  TreeNode(Color c, const T& k, TreeNode* p, TreeNode* l, TreeNode* r); ~TreeNode(){}};template
     
      TreeNode
      
       ::TreeNode(Color c, const T& k, TreeNode* p, TreeNode* l, TreeNode* r)            :color(c),             key(k),             parent(p),             left(l),             right(r){ cout<<"success to create"<

template
    
     class RBTree{ private:  TreeNode
     
      * root;    TreeNode
      
       * getParent(TreeNode
       
        * node);  TreeNode
        
         * GParent(TreeNode
         
          * node);    void destroy(TreeNode
          
           * tree);    void insert(TreeNode
           
            * rt, TreeNode
            
             * node);  void leftRotate(TreeNode
             
              * rt, TreeNode
              
               * node);  void rightRotate(TreeNode
               
                * rt, TreeNode
                
                 * node);  void insertFixUp(TreeNode
                 
                  * rt, TreeNode
                  
                   * node);    void transPlant(TreeNode
                   
                    * rt, TreeNode
                    
                     * node, TreeNode
                     
                      * node2);  void remove(TreeNode
                      
                       * rt, TreeNode
                       
                        * node);    void deleteFixUp(TreeNode
                        
                         * rt, TreeNode
                         
                          * node);    TreeNode
                          
                           * search(TreeNode
                           
                            * node, const t& key)const;  public:   RBTree();   ~RBTree();   void destroy();   void insert(const t& key);   void remove(const t& key);   TreeNode
                            
                             * search(const t& key)const;   TreeNode
                             
                              * minimumNode(TreeNode
                              
                               * x);//搜索给定节点的最小值.    TreeNode
                               
                                * maximumNode(TreeNode
                                
                                 * x);};

template
    
     RBTree
     
      ::RBTree()       :root(nullptr){ cout<<"create a tree"<

template
    
     RBTree
     
      ::~RBTree(){ this->destroy();}

template
    
     TreeNode
     
      * RBTree
      
       ::getParent(TreeNode
       
        * node){ return node->parent;}

template
    
     TreeNode
     
      * RBTree
      
       ::GParent(TreeNode
       
        * node){ return (node->parent)->parent;}

template
    
     void RBTree
     
      ::destroy(){ destroy(root);}

template
    
     void RBTree
     
      ::destroy(TreeNode
      
       * tree)//递归销毁树. { if(tree == nullptr) return;  if(tree->left != nullptr) destroy(tree->left);  if(tree->right != nullptr) destroy(tree->right);  delete tree; tree=nullptr;}

template
    
     void RBTree
     
      ::insert(TreeNode
      
       * rt, TreeNode
       
        * node)//这里把 red-black-tree当作二叉搜索树来处理。 { TreeNode
        
         * y=nullptr; TreeNode
         
          * x=rt;  while(x != nullptr){  y=x;//此时另y作为下面两个支树的节点.     if(node->key < x->node){//此处判断给定节点(node)的key值与树的根节点的key值的大小。    x=x->left;//给点节点的key值确实小于根节点的key值那么另此时的根节点的左支树作为根节点(二叉搜索树的性质左支树总是小于该节点右支树总是大于等于该节点）.   }else{   x=x->right;  } }  node->parent=y; if(y != nullptr){//这里确定把数据插入到左支树还是右支树.    if(node->key < y->key){   y->left=node;  }else{   y->right=node;  } }  node->color=Red; node->left=nullptr; node->right=nullptr; insertFixUp(rt, node);}

template
    
     void RBTree
     
      ::insert(const t& key){ TreeNode
      
       * z=nullptr; if(z = new TreeNode
       
        (Black, key, nullptr, nullptr, nullptr) == nullptr){  return; } insert(root, z);}

template
    
     void RBTree
     
      ::insertFixUp(TreeNode
      
       * rt, TreeNode
       
        * node)//插入修正. { TreeNode
        
         * parent, gParent; TreeNode
         
          * y; parent=getParent(node); gParent=GParent(node);  while(parent->color == Red){//判断给定节点的父节点的颜色颜色是否等于Red;    if(parent == GParent->left){//判断给点节点的父节点的父节点是否等于给定节点的父节点.      y=GParent.right;//让临时节点等于 给点节点(node)的父节点的父节点右节点.       if(y != nullptr && y->color == Red){//case: 1;     parent->color=Black;    y->color=Black;    GParent->color=Red;    node=GParent;       }else if(node == parent->right){//case: 2;    node=parent;    leftRatote(rt, node);       }else{    parent->color=Black;       GParent->color=Red;       rightRotate(root, GParent);   }

  }else{//如果给定节点是GParent的右节点.      y=GParent->left;   if(y!= nullptr && y->color==Red){//case: 1;    y->color=Black;    parent->color=Black;    GParent->color=Red;    node=GParent;       }else if(node == parent->left){//case: 2;    node=parent;    rightRatote(rt, node);       }else{//case: 3;    parent->color=Black;    GParent->Red;    leftRatote(rt, GParent);       }  } }}

 /* * 对红黑树的节点(y)进行右旋转** 右旋示意图(对节点y进行左旋)：*            py                               py*           /                                /*          y                                x                  *         /  \      --(右旋)-->            /  \                     #*        x    ry                          lx   y  *       / \                                   / \                   #*      lx  rx                                rx  ry* */

template
    
     void RBTree
     
      ::rightRotate(TreeNode
      
       * rt, TreeNode
       
        * node){ TreeNode
        
         * x=node->left; node->left=x->left;  if(x->right == nullptr){  (x->right)->parent=node; }  x->parent=node->parent; if(node->parent==nullptr){  rt=x;   }else{    if(node == (node->parent)->right){//判断给定节点是其父节点的右节???    (node->parent)->right=x;     }else{   (node->parent)->left=x;  }   }  x->right=node; node->parent=x;}

template
    
     void RBTree
     
      ::leftRotate(TreeNode
      
       * rt, TreeNode
       
        * node){ TreeNode
        
         * y=node->right;//另临时节点等于给定节点的左节点.  node->right=y->left;//另给点节点的右节点等于 临时节点的左节点.   if(y->left != nullptr){  (y->left)->parent=node;  }  y->parent=node->parent; if(node->parent == nullptr){  rt=y;   }else if(node == (node->parent)->left){  (node->parent)->left=y;   }else{  (node->parent)->right=y; }  y->left=node; node->parent=y;}

template
    
     TreeNode
     
      * RBTree
      
       ::search(const t& key)const{ return search(root, key);}

template
    
     TreeNode
     
      * RBTree
      
       ::search(TreeNode
       
        * node, const t& key)const{ if(node != nullptr || node->key == key){  return node; }  if(node->key < key){  return search(node->right, key); }else{  return search(node->left, key); }}

template
    
     void RBTree
     
      ::remove(const t& key){ TreeNode
      
        * temNode;//临时节点.  if( (temNode=search(root, key)) != nullptr ){//搜索含有该key的节点.   remove(root, temNode); }}

template
    
     void RBTree
     
      ::remove(TreeNode
      
       * rt, TreeNode
       
        * node){ TreeNode
        
         * y=node; TreeNode
         
          * x; Color originalColor=y->color;  if(node->left == nullptr){//将要被移除的节点的左节点为空.   x=node->right;  transPlant(root, node, node->right);   }else if(node->right == nullptr){//当node的右节点为空.   x=node->left;  transPlant(root, node, node->left);   }else{  y=minimumNode(node->right);//node的左右节点都不为空.   originalColor=y->color;//记录node右边支树的最小(左支树)节点的颜色.   x=y->right;//领x等于node右节点中的最小节点的     if(y->parent == node){//如果上述最小节点的父节点等于node;    x->parent=y;//领node右节点中的最小节点的父节点 右节点等于 node右节点的最小节点.    /*            node    *            /  \    *           l1   r1(y)                     / \                    l2  r2(x)=null    */                    }else{//此时node右节点的最小节点父节点并不等于（！=）node.    transPlant(root, y, y->right);//对该节点进行移植.    y->right=node->right;   (y->right)->parent=y;   transPlant(root, node, y);//对需要删除的节点进行移植. 此处令y的父节点等于node的父节点,而且令y位于node的右侧.       y->left=node->left;   y->color=node->color;     } } if(originalColor == Black){  deleteFixUp(rt, x); } delete node;}

template
    
     void RBTree
     
      ::transPlant(TreeNode
      
       * rt, TreeNode
       
        * node, TreeNode
        
         * node2)//该函数把被删除节点的前后数据链接起来. { /*                p  *                |  *               node  *              /  \  *             l1   r1  *            / \  *             *  *  *  *  */ if(node->parent == nullptr){ //如果被删除节点是根节点那么把node2替换为根节点.   rt=node2;   }else if(node == (node->parent)->left){ //如果将要删除的节点是位于其父节点的左边，那么说明该节点小于父节点.   (node->parent)->left=node2;   }else{  (node->parent)->right=node2; }  node2->parent = node->parent;}

template
    
     TreeNode
     
      * RBTree
      
       ::minimumNode(TreeNode
       
        * x){ while(x->left != nullptr){  x=x->left; }  return x;}

template
    
     TreeNode
     
      * RBTree
      
       ::maximumNode(TreeNode
       
        * x){ while(x->right != nullptr){  x=x->right; }  return x;}

template
    
     void RBTree
     
      ::deleteFixUp(TreeNode
      
       * rt, TreeNode
       
        * node){ TreeNode
        
         * tempNode;  while(node != rt, node->color=Black){  if(node == (node->parent)->left){// 该节点位于父节点的left    tempNode=(node->parent)->right;//令临时节点等于给定节点的右节.       if(tempNode->color==Red){    tempNode->color=Black;    (tempNode->parent)->color=Red;        leftRotate(rt, node->parent);    tempNode=(node->parent)->right;       }      if((tempNode->left)->color == Black && (tempNode->right)->color==Black){//临时节点的左边节点的颜色是否等于Black, 临时节点右节点的颜色是否等于Black.     tempNode->color=Red;    node=node->parent;        }else if((tempNode->right)->color == Black){    (tempNode->left)->color=Black;    tempNode->color=Red;    rightRotate(rt, tempNode);       }      tempNode->color=(node->parent)->color;   (node->parent)->color=Black;   (tempNode->right)->color=Black;   leftRotate(rt, node->parent);   node=rt;     }else{   tempNode=(node->parent)->left;      if(tempNode->color == Red){    tempNode->color=Black;    (tempNode->parent)->color=Red;        rightRotate(rt, node->parent);    tempNode=(node->parent)->left;       }      if((tempNode->left)->color==Black && (tempNode->rifht)->color==Black){    tempNode->color=Red;    node=node->parent;       }else if((tempNode->left)->color == Black){    (tempNode->right)->color=Black;    tempNode->color=Red;    leftRotate(rt, tempNode);   }      tempNode->color=(node->parent)->color;   (node->parent)->color=Black;   (tempNode->left)->color=Black;   rightRotate(rt, node->parent);   node=rt;  } }}