1 /*
  2  * rbtree.h
  3  * 1. 每个节点是红色或者黑色
  4  * 2. 根节点是黑色
  5  * 3. 每个叶子节点是黑色（该叶子节点就空的节点）
  6  * 4. 如果一个节点是红色，则它的两个子节点是黑色的
  7  * 5.对每个节点，从该节点道其他所有后代的叶子节点的简单路径上，均包含相同数目的黑色节点
  8  *
  9  */
 10 
 11 #ifndef SRC_RBTREE_H_
 12 #define SRC_RBTREE_H_
 13 #include<iostream>
 14 #include<queue>
 15 
 16 using namespace std;
 17 enum colors{ RED,BLACK};
 18 typedef int color_type;
 19  namespace red_black_tree{
 20      struct rb_tree_base{
 21         struct rb_tree_base * parent;
 22         struct rb_tree_base * left;
 23         struct rb_tree_base * right;
 24         color_type color;
 25     };
 26 
 27     template<class T>
 28     struct rb_tree_node:public rb_tree_base{
 29         T data;
 30         typedef rb_tree_node<T>* link_type;
 31      };
 32    template<class Value>
 33     class rb_tree{
 34     public:
 35        typedef rb_tree_base* rb_ptr;
 36        typedef typename rb_tree_node<Value>::link_type link_type;
 37        typedef rb_tree_node<Value>  tree_node;
 38     private:
 39        rb_ptr head;
 40     private:
 41         bool _right_rotate(rb_ptr root);
 42         bool _left_rotate(rb_ptr root);
 43         rb_ptr _get_node(const Value& e) const;
 44         bool _insert_fix_up(rb_ptr current_ptr);
 45 
 46         bool _erase_fix_up(rb_ptr current_ptr,rb_ptr parent_ptr);
 47 
 48         void _preOrder(rb_ptr root) const;
 49 
 50         rb_ptr _successor(rb_ptr current_ptr) const;
 51     public:
 52         rb_tree();
 53         ~rb_tree();
 54         bool insert(const Value &e);
 55         bool empty() const;
 56         bool erase(const Value &e);
 57         rb_ptr find(const Value &e);
 58         void levelOrder() const;
 59         void preOrder() const;
 60     };
 61    template<class Value>
 62     rb_tree<Value>::rb_tree() {
 63         head = new  tree_node();
 64         head->left=head;
 65         head->right=head;
 66         head->parent=head;
 67 
 68         head->color=BLACK;
 69     }
 70 
 71     template<class Value>
 72     rb_tree<Value>::~rb_tree() {
 73     }
 74 
 75    template<class Value>
 76     bool rb_tree<Value>::insert(const Value& e) {
 77         rb_ptr insert_ptr =_get_node(e);
 78         if(head->parent ==head){
 79             head->parent=insert_ptr;
 80             insert_ptr->parent=head;
 81             insert_ptr->color=BLACK;
 82             return true;
 83         }
 84         rb_ptr root_ptr=head->parent;
 85         rb_ptr root_remember=nullptr;
 86         while(root_ptr){
 87             root_remember=root_ptr;
 88             if(link_type(insert_ptr)->data<=link_type(root_ptr)->data)
 89                 root_ptr=root_ptr->left;
 90             else
 91                 root_ptr=root_ptr->right;
 92         }
 93         insert_ptr->parent=root_remember;
 94         if(link_type(insert_ptr)->data <= link_type(root_remember)->data )
 95             root_remember->left=insert_ptr;
 96         else if(link_type(insert_ptr)->data >link_type( root_remember)->data)
 97             root_remember->right=insert_ptr;
 98         bool ret =_insert_fix_up(insert_ptr);
 99         return ret;
100     }
101     template<class Value>
102     bool rb_tree<Value>::empty() const {
103 
104         return head->parent==head;
105     }
106 
107     template<class Value>
108     bool rb_tree<Value>::erase(const Value& e) {
109 
110         rb_ptr erase_ptr = find(e);
111 
112         if(!erase_ptr)
113 
114             return false;
115 
116         int erase_color =erase_ptr->color;
117 
118         rb_ptr fix_up_ptr=nullptr;
119 
120         rb_ptr fix_up_parent_ptr=nullptr;
121 
122         if(erase_ptr){
123 
124             if(!erase_ptr->left&&!erase_ptr->right){//叶子节点
125 
126                 if(erase_ptr==erase_ptr->parent->left){
127 
128                     erase_ptr->parent->left=nullptr;
129 
130                     fix_up_parent_ptr= erase_ptr->parent;
131 
132                 }
133 
134                 if(erase_ptr==erase_ptr->parent->right){
135 
136                     erase_ptr->parent->right=nullptr;
137 
138                     fix_up_parent_ptr= erase_ptr->parent;
139 
140                 }
141 
142                 if(erase_ptr==head->parent){
143 
144                     head->parent=head;
145 
146                     fix_up_parent_ptr=head;
147 
148                 }
149 
150                 erase_color =erase_ptr->color;
151 
152                 delete erase_ptr;
153 
154             }else if(erase_ptr->right){
155 
156                 rb_ptr successor_ptr =_successor(erase_ptr);//left一定为空
157 
158                 link_type(erase_ptr)->data=http://www.mamicode.com/link_type(successor_ptr)->data;"data: "<<link_type(visit_ptr)->data<<"  color: "<<((visit_ptr->color==0)?"RED":"BLACK")<<endl;
559                 if(visit_ptr->left)
560                     q.push(visit_ptr->left);
561                 if(visit_ptr->right)
562                     q.push(visit_ptr->right);
563                 q.pop();
564             }
565         }
566     }
567     template<class Value>
568     void rb_tree<Value>:: _preOrder(rb_ptr root) const{
569         if(root){
570            cout<<"data: "<<link_type(root)->data<<"  color: "
571 
572             <<((root->color==0)?"RED":"BLACK")<<endl;
573             _preOrder(root->left);
574             _preOrder(root->right);
575         }
576     }
577     template<class Value>
578     void rb_tree<Value>:: preOrder() const{
579         _preOrder(head->parent);
580     }
581 }
582 
583 
584 //#include "rbtree.cpp"
585 #endif /* SRC_RBTREE_H_ */

红黑树C++实现