红黑树(未修改,检验)C++
红黑树(未修改,检验)C++
SHIHUAMarryMe 发表于2年前
红黑树(未修改,检验)C++
  • 发表于 2年前
  • 阅读 98
  • 收藏 1
  • 点赞 1
  • 评论 0

腾讯云 技术升级10大核心产品年终让利>>>   

摘要: 在家放假了下了几天雪,冻死我了,都不想摸键盘. 翻了翻好像是以前写的丢上来算了。。
 #include <iostream>
#include <string>
using namespace std;
enum Color:int{Black, Red};
template<typename T>
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<typename T>
TreeNode<T>::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"<<endl;
}
template<typename t>
class RBTree{
 private:
  TreeNode<t>* root;
  
  TreeNode<t>* getParent(TreeNode<t>* node);
  TreeNode<t>* GParent(TreeNode<t>* node);
  
  void destroy(TreeNode<t>* tree);
  
  void insert(TreeNode<t>* rt, TreeNode<t>* node);
  void leftRotate(TreeNode<t>* rt, TreeNode<t>* node);
  void rightRotate(TreeNode<t>* rt, TreeNode<t>* node);
  void insertFixUp(TreeNode<t>* rt, TreeNode<t>* node);
  
  void transPlant(TreeNode<t>* rt, TreeNode<t>* node, TreeNode<t>* node2);
  void remove(TreeNode<t>* rt, TreeNode<t>* node);
  
  void deleteFixUp(TreeNode<t>* rt, TreeNode<t>* node);
  
  TreeNode<t>* search(TreeNode<t>* node, const t& key)const;
  public:
   RBTree();
   ~RBTree();
   void destroy();
   void insert(const t& key);
   void remove(const t& key);
   TreeNode<t>* search(const t& key)const;
   TreeNode<t>* minimumNode(TreeNode<t>* x);//搜索给定节点的最小值. 
   TreeNode<t>* maximumNode(TreeNode<t>* x);
};
template<typename t>
RBTree<t>::RBTree()
       :root(nullptr)
{
 cout<<"create a tree"<<endl;
}
template<typename t>
RBTree<t>::~RBTree()
{
 this->destroy();
}
template<typename t>
TreeNode<t>* RBTree<t>::getParent(TreeNode<t>* node)
{
 return node->parent;
}
template<typename t>
TreeNode<t>* RBTree<t>::GParent(TreeNode<t>* node)
{
 return (node->parent)->parent;
}
template<typename t>
void RBTree<t>::destroy()
{
 destroy(root);
}
template<typename t>
void RBTree<t>::destroy(TreeNode<t>* tree)//递归销毁树. 
{
 if(tree == nullptr) return;
 
 if(tree->left != nullptr) destroy(tree->left);
 
 if(tree->right != nullptr) destroy(tree->right);
 
 delete tree;
 tree=nullptr;
}
template<typename t>
void RBTree<t>::insert(TreeNode<t>* rt, TreeNode<t>* node)//这里把 red-black-tree当作二叉搜索树来处理。 
{
 TreeNode<t>* y=nullptr;
 TreeNode<t>* 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<typename t>
void RBTree<t>::insert(const t& key)
{
 TreeNode<t>* z=nullptr;
 if(z = new TreeNode<t>(Black, key, nullptr, nullptr, nullptr) == nullptr){
  return;
 }
 insert(root, z);
}
template<typename t>
void RBTree<t>::insertFixUp(TreeNode<t>* rt, TreeNode<t>* node)//插入修正. 
{
 TreeNode<t>* parent, gParent;
 TreeNode<t>* 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<typename t>
void RBTree<t>::rightRotate(TreeNode<t>* rt, TreeNode<t>* node)
{
 TreeNode<t>* 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<typename t>
void RBTree<t>::leftRotate(TreeNode<t>* rt, TreeNode<t>* node)
{
 TreeNode<t>* 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<typename t>
TreeNode<t>* RBTree<t>::search(const t& key)const
{
 return search(root, key);
}
template<typename t>
TreeNode<t>* RBTree<t>::search(TreeNode<t>* 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<typename t>
void RBTree<t>::remove(const t& key)
{
 TreeNode<t> * temNode;//临时节点.
 
 if( (temNode=search(root, key)) != nullptr ){//搜索含有该key的节点. 
  remove(root, temNode);
 }
}
template<typename t>
void RBTree<t>::remove(TreeNode<t>* rt, TreeNode<t>* node)
{
 TreeNode<t>* y=node;
 TreeNode<t>* 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<typename t>
void RBTree<t>::transPlant(TreeNode<t>* rt, TreeNode<t>* node, TreeNode<t>* 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<typename t>
TreeNode<t>* RBTree<t>::minimumNode(TreeNode<t>* x)
{
 while(x->left != nullptr){
  x=x->left;
 }
 
 return x;
}
template<typename t>
TreeNode<t>* RBTree<t>::maximumNode(TreeNode<t>* x)
{
 while(x->right != nullptr){
  x=x->right;
 }
 
 return x;
}
template<typename t>
void RBTree<t>::deleteFixUp(TreeNode<t>* rt, TreeNode<t>* node)
{
 TreeNode<t>* 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;
  }
 }
}
共有 人打赏支持
粉丝 12
博文 165
码字总数 138247
×
SHIHUAMarryMe
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: