文档章节

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

SHIHUAMarryMe
 SHIHUAMarryMe
发布于 2016/02/01 23:09
字数 1759
阅读 100
收藏 1
 #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;
  }
 }
}

© 著作权归作者所有

共有 人打赏支持
SHIHUAMarryMe
粉丝 13
博文 164
码字总数 138212
作品 0
武汉
程序员
私信 提问
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
0
0
数据结构备忘录:Trie树基本操作

Trie树是一种可以实现字符串多模匹配的数据结构,在字符串处理中有很重要的作用,本文Trie树实现参考了殷人昆数据结构与算法C++语言描述第二版中的内容。不同的是分支节点的分支结构用C++标准...

Kukucao
01/04
0
0
STL vector+sort排序和multiset/multimap排序比较

本文由 www.169it.com 搜集整理 在C++的STL库中,要实现排序可以通过将所有元素保存到vector中,然后通过sort算法来排序,也可以通过multimap实现在插入元素的时候进行排序。在通过vector+so...

小星星程序员
2014/11/05
0
0
STL系列之六 set与hash_set

STL系列之六 set与hash_set set和hash_set是STL中比较重要的容器,有必要对其进行深入了解。在STL中,set是以红黑树(RB-tree)作为底层数据结构的,hash_set是以Hash table(哈希表)作为底...

长平狐
2012/12/10
41
0
C++代码问题(segment fault)

#include <iostream> include <string> include <vector> include <set> include <map> using namespace std; /*int main(){int a;a = 10;cout<<" "<<a<<endl;return 0;} */typedef struct c......

SibylY
2013/11/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

cnetos7+docker+rancher构建基于DevOps的全自动CI【01】

来自DevOps实践分享,分享从开发代码到生产环境部署的一条龙操作的实践及经验, 包含工具技术的选型及考量、私有代码库与私有镜像库的应用等。 1、环境选择 安装Rancher环境,一定要在干净的...

Elson
23分钟前
1
0
21分钟教会你分析MaxCompute账单

背景 阿里云大计算服务MaxCompute是一款商业化的大数据分析平台,其计算资源有预付费和后付费两种计费方式。并且产品每天按照project为维度进行计量计费(账单基本情况下会第二天6点前产出)...

zhaowei121
26分钟前
0
0
CTO职场解惑指南系列(一)

基于科技能够改变世界的事实,几乎每个公司的程序员都自带闪光灯。程序员的手和普通人的手自然是有区别的,“我们可是用双手改变了世界” 。(码农真的是靠双手吃饭,呵呵) 这个世界上但凡靠...

阿里云云栖社区
31分钟前
2
0
css实现图片自适应容器宽高

css实现图片自适应容器宽高的做法一般如下所示 <style>div{width: 200px; height: 200px}div img{width: 100%; height: 100%}</style><div><img src="xxxx.png" /></div> 当外层容......

小草先森
31分钟前
3
0
PlatON在CentOS上编译部署

本文作者为万向区块链CTO罗荣阁。 目录 PlatON在CentOS上编译部署 1. CentOS 环境准备 1.1. 使用rpm 安装devtoolset-7 1.2. 使用rpm 安装dos2unix 1.3. 准备PlatON代码 1.4. 确保build脚本正...

万向区块链
39分钟前
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部