文档章节

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

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

小星星程序员
2014/11/05
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
利用红黑树自己编写 C++ MAP

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

WangDylan
2013/09/09
0
0
大神告诉你学好这几点,你就学会了C语言

很多小伙伴在初学C语言的时候完全没有什么概念,完全不知道怎么去学怎样才能掌握这门语言的重要知识点。 今天小编就来总结一下学习C语言过程中四大重点吧 ! (一)C语言要学到什么程度才算差...

诸葛玥
05/25
0
0
C语言编程学习开发的俄罗斯方块小游戏

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【mpvue】三

使用了快1个月,陆续整理发现的坑 1、pageA-pageB-pageA-pageC 如果以这种顺序,大概理解成,列表进详情B, 返回列表进入详情C,那么进入详情C的时候,会因为缓存,先展现详情B的内容。解决方...

登天的感觉
4分钟前
0
0
在EXCEL指定SHEET页,指定文字位置,插入批注

Java操作EXCEL文件,利用POI,在EXCEL指定SHEET页中指定文字位置处插入批注 package excel; import java.io.FileInputStream; import java.io.FileOutputStream; import org.apache.poi.hssf......

zhaochaochao
6分钟前
0
0
一些网站。

UI schema,可以用json定义UI表单:https://jsonforms.io/examples/array

王坤charlie
12分钟前
0
0
百万连接,百亿吞吐量服务的JVM性能调优实战

转载占小狼博客 应用:shark-新美大移动端网络优化(每日接受移动端请求约150亿) 应用特点 : qps比较高,新生代增长飞快 用户的连接需要维持一段时间 单机需要维持海量连接,几十万的级别 以...

BakerZhu
15分钟前
0
0
iOS涂色涂鸦效果、Swift仿喜马拉雅FM、抽屉转场动画、拖拽头像、标签选择器等源码

iOS精选源码 LeeTagView 标签选择控件 为您的用户显示界面添加美观的加载视图 Swift4: 可拖动头像,增加物理属性 Swift版抽屉效果,自定义转场动画管理器 Swift 仿写喜马拉雅FM 可能是最好用...

sunnyaigd
16分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部