文档章节

红黑树(未修改,检验)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
博文 163
码字总数 137219
作品 0
武汉
程序员
私信 提问
STL vector+sort排序和multiset/multimap排序比较

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

小星星程序员
2014/11/05
0
0
利用红黑树自己编写 C++ MAP

搞定红黑树,就想着写来玩玩。于是,就配合C++的模板技术写了一个简单的Map。 看了一些博客,个人感觉还是Wiki上讲红黑树讲的清晰一些,我承认没完全看懂算法导论上删除结点的树调整,连他的二...

WangDylan
2013/09/09
0
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
从“成都-go-戒炸鸡”的面试题开始说起

版权声明:欢迎关注我的微信公众号:「easyserverdev」,中文名:『高性能服务器开发』。 https://blog.csdn.net/analogous_love/article/details/84207246 今天晚上“高性能服务器开发”QQ群...

analogous_love
昨天
0
0
大厂面试官:对于代码量、项目经验与操作系统、数据结构,我更注重哪一种!

一、以百度、爱奇艺等为代表的,以数据结构和算法为主,首先是简单地了解下你之前的工作经历和项目经验,然后就是算法和数据结构题目,具体涉及到以下内容: 1. 快速排序(包括算法步骤、平均...

茶轴的青春
08/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

DataFrames中的reindex用法

from pandas import DataFrame frame = DataFrame(np.arange(9).reshape((3,3)),index=['a','c','d'],columns=['Ohio','Texas','California'] states = ['Texas','Utah','California'] frame......

卖小孩的小火柴
4分钟前
0
0
拜托!面试请不要再问我Spring Cloud底层原理

毫无疑问,Spring Cloud是目前微服务架构领域的翘楚,无数的书籍博客都在讲解这个技术。不过大多数讲解还停留在对Spring Cloud功能使用的层面,其底层的很多原理,很多人可能并不知晓。因此本...

James-
5分钟前
0
0
Shiro框架

提供了认证,授权,加密,会话管理等功能 在spring配置文件中配置shiro,需要配置的有shiro的过滤器工厂,在里面我们可以配置什么页面需要认证,什么认证不需要认证,认证成功后跳转的路径,认证失败...

tinder_boy
8分钟前
0
0
有关定时任务的表达式--cron 详细解

Cron表达式是一个字符串,字符串以5或6个空格隔开,分为6或7个域,每一个域代表一个含义,Cron有如下两种语法格式: Seconds Minutes Hours DayofMonth Month DayofWeek Year或 Seconds Minu...

kuchawyz
9分钟前
1
0
下一代大数据处理引擎,阿里云实时计算独享模式重磅发布

11月14日,阿里云重磅发布了实时计算独享模式,即用户独享一部分物理资源,这部分资源在网络/磁盘/CPU/内存等资源上跟其他用户完全独立,是实时计算在原有共享模式基础上的重大升级。 (观看...

阿里云云栖社区
10分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部