红黑树学习笔记

从上学期就一直打算写出红黑树，但是由于能力太水，插入操作始终无法看明白，最近学习数据结构重新将红黑树的插入操作看了一遍，结合《算法导论》，《data structures and programing design in C++》和侯捷的《STL源码》，终于弄清楚插入操作中保持树结构的几种情况，虽然这三本书在分类上有些许的差别，但本质的方法还是一样的。

我还是根据算法导论将其分为3种情况（STL是分为4种情况）：

首先必须明白的情况是：每次插入节点的都设为红条件，如果需要保持红黑树结构时，则必然是新增节点的父亲节点也是红色，而且祖父节点必须是黑色（因为未插入前是一棵符合要求的红黑树）

1.叔父节点为红色---处理：将父亲节点和叔父节点同时设为黑色，祖父节点设为红色，此时必须考虑祖父节

点的父亲节点是否为黑色，所以将指针然后向上移动两层，继续往上判断是否满足红黑树性质。

2. 叔父节点为黑色且是外侧插入----处理：进行单旋转操作，单旋转操作与AVL树类似，但是在细节处理上

需要格外注意，因为RB_Node有指向父节点的parent指针；

3. 叔父节点为黑色且是内测插入----处理：进行双旋转操作，旋转后更改两个节点颜色即可，双旋转操作

其实可以分解为左右两次单旋转操作，所以算法导论中这种情况

是只进行单旋转操作转化为情况2，我这里将其合并。

删除操作比较复杂，，有时间再看。。贴上自己写的插入代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 using namespace std;
  5 enum Color {red, black};
  6 template<class Record>
  7 //树节点
  8 struct RB_Node{
  9   Color color;
 10   Record data;
 11   RB_Node *left, *right, *parent;
 12   RB_Node() {left = right = parent = NULL; color = red;}
 13   RB_Node(RB_Node*subroot, Record& data_) {
 14     left = right = NULL;
 15     parent = subroot;
 16     color = red; data = data_;
 17   } 
 18 };
 19 
 20 template<class Record>
 21 class RB_Tree {
 22  public:
 23    RB_Tree() {root == NULL;}
 24    bool insert(Record& data_);
 25    void Inorder();
 26  private:
 27    void fix_up(RB_Node<Record>* &T, RB_Node<Record>* &z);
 28    void Left_Rotate(RB_Node<Record>* &T, RB_Node<Record>* &x);
 29    void Right_Rotate(RB_Node<Record>* &T, RB_Node<Record>* &x);
 30    void recursive_inorder(RB_Node<Record>* subroot);
 31    RB_Node<Record>* root;
 32 };
 33 
 34 template<class Record>
 35 bool RB_Tree<Record>::insert(Record& data_) {
 36   //插入新元素
 37   RB_Node<Record> *x = root, *y = NULL;
 38   while (x) {
 39     y = x;
 40     if ((x->data) > data_)  x = x->left;
 41     else                     x = x->right;
 42   }
 43   RB_Node<Record>* z = new RB_Node<Record>(y, data_);
 44   if (y == NULL) {
 45     root = z; root->color = black; return true;
 46   } else if (data_ < y->data) {
 47     y->left = z;
 48   } else {
 49     y->right = z;
 50   }
 51   fix_up(root, z); //保持树结构
 52   return true;
 53 }
 54 template<class Record>
 55 void RB_Tree<Record>::fix_up(RB_Node<Record>* &T, RB_Node<Record>* &z) {
 56   while (z->parent && (z->parent)->color == red) {
 57     if ((z->parent)->parent->left == z->parent) { //父亲节点位于祖父节点的左侧
 58       RB_Node<Record>* y = (z->parent)->parent->right;
 59       if (y && y->color == red) {   //case 1: 叔父节点为红色节点（注意若为nil是黑色节点）
 60         y->color = black;
 61         z->parent->color = black;
 62         (z->parent)->parent->color = red;
 63         z = (z->parent)->parent;
 64       } else  {                    
 65         if (z == z->parent->right) {   //case 2: 叔父节点为黑色且节点为内侧插入
 66           z = z->parent;
 67           Left_Rotate(T, z);
 68         }
 69         (z->parent)->color = black;   //case 3:叔父节点为黑色且节点为外侧插入
 70         (z->parent)->parent->color = red;
 71         z = (z->parent)->parent;
 72         Right_Rotate(T, z);
 73       }
 74     } else {                                 //父亲节点位于祖父节点右侧，与上面类似
 75       RB_Node<Record>* y = (z->parent)->parent->left;
 76       if (y && y->color == red) {
 77         y->color = black;
 78         z->parent->color = black;
 79         (z->parent)->parent->color = red;
 80         z = (z->parent)->parent;
 81       } else {
 82         if (z == (z->parent)->left) {
 83           z = z->parent;
 84           Right_Rotate(T, z);
 85         }
 86         (z->parent)->color = black;
 87         ((z->parent)->parent)->color = red;
 88         z = (z->parent)->parent;
 89         Left_Rotate(T, z);
 90       }
 91     }
 92   }
 93   if (z->parent == NULL) z->color = black;
 94 }
 95 template<class Record>  //旋转操作时应特别注意NULL的情况，需要考虑三对关系：1.x与y->left 2.x->parent 与y 3. x与y
 96 void RB_Tree<Record>::Left_Rotate(RB_Node<Record>* &T, RB_Node<Record>* &x) {
 97   RB_Node<Record>* y = x->right;
 98   x->right = y->left;
 99   if (y->left != NULL) (y->left)->parent = x;
100   y->parent = x->parent;
101   if (x->parent == NULL) {
102     T = y;
103   } else if ((x->parent)->right == x){
104     (x->parent)->right = y;
105   } else {
106     (x->parent)->left = y;
107   }
108   y->left = x;
109   x->parent = y;
110 }
111 template<class Record> //The same as Left_rotate
112 void RB_Tree<Record>::Right_Rotate(RB_Node<Record>* &T, RB_Node<Record>* &x) {
113   RB_Node<Record>* y = x->left;
114   x->left = y->right;
115   if (y->right != NULL) (y->right)->parent = x;
116   y->parent = x->parent;
117   if (x->parent == NULL) {
118     T = y;
119   } else if ((x->parent)->right == x) {
120     (x->parent)->right = y;
121   } else {
122     (x->parent)->left = y;
123   }
124   y->right = x;
125   x->parent = y;
126 }
127 
128 //test inorder_traversal
129 template<class Record>
130 void RB_Tree<Record>::Inorder() {
131   recursive_inorder(root);
132 }
133 template<class Record>
134 void RB_Tree<Record>::recursive_inorder(RB_Node<Record>* subroot) {
135   if (subroot != NULL) {
136     recursive_inorder(subroot->left);
137     cout << subroot->data << endl;
138     recursive_inorder(subroot->right);
139   }
140 }
141 
142 int main() {
143   RB_Tree<int> rb;
144   for (int i = 0; i < 10; i++) {
145       int u;
146     cin >> u;
147     rb.insert(u);
148     rb.Inorder();
149     cout << endl;
150   }
151  // rb.Inorder();
152   return 0;
153 }