近期在看STL源码，然后看到了关联性容器map和set的底层实现—红黑树，之前只是知道有这个名字的存在，近期花了两天的时间专门的研究了一下，有了一些初步的认识和了解。
本博客主要内容参考红黑树详细介绍
红黑树
红黑树定义
其或者是一颗空树，或者是具有以下性质的对称平衡二叉查找树：
- 节点非红即黑；
- 根节点是黑色；
- 所有NULL节点称为叶子节点，且其颜色为黑；
- 所有红色节点的子节点都为黑色；
- 从任一节点到其叶子节点的所有路径上都包含相同数目的黑色节点；
通过对任何一条从根到叶子的路径上的各个节点着色的限制，红黑树确保没有一条路径会比其他路径长出两倍，因为是接近平衡的？？
红黑树最大路径长度不可能大于两倍最短路径，为什么？
因为第一条该树上的节点非红即黑，由于第四条该树上不允许存在连续的红节点，那么对于从第一个节点到其叶子节点的一条最长路径一定是红黑交错的，那么最短路径一定是纯黑色的节点；而第五条从任一节点到其叶子节点的所有路径上都包含相同数目的黑色节点，这么说来最长路径上的黑节点的数目和最短路径上的黑节点的数目相等！而第二条根节点为黑，第三条叶子结点为黑色，那么可知：最长路径 ≤ 2 * 最短路径。
一颗二叉树的平衡性能越好，那么它的效率越高！
红黑树放松了对平衡的限制，可以不再是严格意义上的平衡二叉树，但在每个节点上增加一个存储位表示节点的颜色，可以是Red 或者 Block。
【解释】：红黑树属于平衡二叉树，说它不严格是因为它不是严格控制左、右子树高度或者节点数之差小于等于1，但是红黑树的高度依然是平均log(n)，且最坏情况下高度不会超过2log(n)，这个可以数学证明。所以它算平衡树，只是不严格，不过严格与否并不影响数据结构的复杂度，红黑树多用于系统底层；
红黑树与AVL树的相同点和区别
红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找。自从红黑树出来后，AVL树就被放到了博物馆里，据说是红黑树有更好的效率，更高的统计性能。
红黑树与AVL树的区别在于它使用颜色来标识节点的高度，它所追求的是局部平衡而不是AVL树中的非常严格的平衡。AVL树的复杂比起红黑树来说简直是小巫见大巫。红黑树是真正的变态级数据结构。
红黑树的时间复杂度
在一棵二分查找树上，执行查找、插入、删除等操作的最好情况时间复杂度为O(lgn)，因为一颗由n个节点，随机构造的二叉查找树的高度为lgn，一般操作的执行时间为O(lgn)。
但若是一颗具有n个节点的线性链，则这些操作最坏情况运行时间为O(n)。
而红黑树可以保证在最坏情况下，基本的动态几何操作的时间均为O(lgn)。
红黑树的插入：
1. 如果插入的是空树，则直接把此节点涂为黑色；
2. 如果插入的节点的父节点是黑色，什么也不做；
3. 三种情况4. 如果当前节点的父节点是红色，且祖父节点的另一节点（叔叔节点）是红色；5. 如果当前节点的父节点是红色，叔叔节点为黑色，当前节点是父节点的右孩子；6. 如果当前节点的父节点是红色，叔叔节点为黑色，当前节点是父节点的左孩子；
RBTree.h
RB-INSERT-FIXUP(T, z)
while z.p.color == RED do if z.p == z.p.p.left then y ← z.p.p.right if y.color == RED then z.p.color ← BLACK ▹ Case 1 y.color ← BLACK ▹ Case 1 z.p.p.color ← RED ▹ Case 1 z ← z.p.p ▹ Case 1 else if z == z.p.right then z ← z.p ▹ Case 2 LEFT-ROTATE(T, z) ▹ Case 2 z.p.color ← BLACK ▹ Case 3 z.p.p.color ← RED ▹ Case 3 RIGHT-ROTATE(T, z.p.p) ▹ Case 3 else (same as then clause with "right" and "left" exchanged)
T.root.color ← BLACK 红黑树的删除操作
1. 当前节点是红色，则把当前节点设成黑色
2. 当前节点是黑色，且未根节点，则什么都不做；
3. 四种情况4. 当前节点是黑色，兄弟节点为红色（此时父节点和兄弟节点的子节点分别为黑）；5. 当前节点为黑色，兄弟节点为黑色，且兄弟节点的两个子结点全是黑色；6. 当前节点为黑色，兄弟节点为黑色，兄弟节点的左孩子为红色，右孩子为黑色；7. 当前节点为黑色，兄弟节点为黑色，兄弟节点的右孩子为红色；
RBTree.h
#ifndef _RB_TREE_H_
#define _RB_TREE_H_ #include<iostream>
#include<string>
#include<sstream>
#include<fstream>template<class KEY,class U> //KEY 对应键值，U对应相应的value
class RB_Tree{
private:RB_Tree(const RB_Tree& input){}const RB_Tree& operator=(const RB_Tree& input){}
private:enum COLOR{ RED, BLACK }; //红黑树的两种颜色class RB_Node{ //红黑树的树节点public:RB_Node(){left = NULL;right = NULL;parent = NULL;}COLOR RB_COLOR; //树节点的颜色RB_Node *left; //树节点的左指针RB_Node *right; //树节点的右指针RB_Node *parent; //树节点的父亲指针，指向父节点KEY key; //关键字U data; //所对应的value};
private:RB_Node* m_nullNode; //空指针RB_Node* m_root; //根节点public:RB_Tree(){this->m_nullNode = new RB_Node();this->m_root = m_nullNode;this->m_nullNode->right = this->m_root;this->m_nullNode->left = this->m_root;this->m_nullNode->parent = this->m_root;this->m_nullNode->RB_COLOR = BLACK;}bool empty(){if (this->m_nullNode == this->m_root){return true;}else return false;}//查找keyRB_Node* find(KEY key){RB_Node *index = m_root;while (index != m_nullNode){if (key < index->key){index = index->left;}else if (key > index->key){index = index->right;}else break;}return index;}//--------------------------插入结点总操作---------------------------------- //全部的工作，都在下述伪代码中： /*RB-INSERT(T, z)1 y ← nil[T] // y 始终指向 x 的父结点。2 x ← root[T] // x 指向当前树的根结点，3 while x ≠ nil[T]4 do y ← x5 if key[z] < key[x] //向左，向右..6 then x ← left[x]7 else x ← right[x] //为了找到合适的插入点，x探路跟踪路径，直到x成为NIL 为止。8 p[z] ← y //y置为 插入结点z 的父结点。9 if y = nil[T]10 then root[T] ← z11 else if key[z] < key[y]12 then left[y] ← z13 else right[y] ← z //此 8-13行，置z 相关的指针。14 left[z] ← nil[T]15 right[z] ← nil[T] //设为空，16 color[z] ← RED //将新插入的结点z作为红色17 RB-INSERT-FIXUP(T, z)*///因为将z着色为红色，可能会违反某一红黑性质，所以需要下面的调整策略保证红黑树的性质bool Insert(KEY key, U data){RB_Node *insert_point = m_nullNode; RB_Node *index = m_root;while (index != m_nullNode){insert_point = index;if (key < index->key){index = index->left;}else if (key > index->key){index = index->right;}else return false;}RB_Node *insert_node = new RB_Node();insert_node->key = key;insert_node->data = data;insert_node->RB_COLOR = RED;insert_node->left = m_nullNode;insert_node->right = m_nullNode;if (insert_point == m_nullNode){m_root = insert_node;m_root->parent = m_nullNode;m_nullNode->left = m_root;m_nullNode->right = m_root;m_nullNode->parent = m_root;}else{if (key < insert_point->key){insert_point->left = insert_node;}else{insert_point->right = insert_node;}insert_node->parent = insert_point;}InsertFixUp(insert_node);//调用InsertFixUp修复红黑树性质}//---------------------插入结点性质修复-------------------------------- //3种插入情况，都在下面的伪代码中(未涉及到所有全部的插入情况)。 /*RB-INSERT-FIXUP(T, z)1 while color[p[z]] = RED2 do if p[z] = left[p[p[z]]]3 then y ← right[p[p[z]]]4 if color[y] = RED5 then color[p[z]] ← BLACK ? Case 16 color[y] ← BLACK ? Case 17 color[p[p[z]]] ← RED ? Case 18 z ← p[p[z]] ? Case 19 else if z = right[p[z]]10 then z ← p[z] ? Case 211 LEFT-ROTATE(T, z) ? Case 212 color[p[z]] ← BLACK ? Case 313 color[p[p[z]]] ← RED ? Case 314 RIGHT-ROTATE(T, p[p[z]]) ? Case 315 else (same as then clause with "right" and "left" exchanged)16 color[root[T]] ← BLACK*///然后的工作，就非常简单了，即把上述伪代码改写为下述的c++代码： void InsertFixUp(RB_Node* node){while (node->parent->RB_COLOR == RED){if (node->parent == node->parent->parent->left){RB_Node *uncle = node->parent->parent->right;if (uncle->RB_COLOR == RED){ //插入情况1：叔叔节点为红色node->parent->RB_COLOR = BLACK; //父节点设为黑色uncle->RB_COLOR = BLACK; //叔叔节点设为黑色node->parent->parent->RB_COLOR = RED; //祖父节点设为红色node = node->parent->parent; //将节点设为祖父节点，重新进入算法}else if (uncle->RB_COLOR == BLACK){ //插入情况2：叔叔节点为黑色if (node == node->parent->right){ //且node为父节点的右孩子node = node->parent; //将节点设为父节点RotateLeft(node); //对父节点左旋}node->parent->RB_COLOR = BLACK; //插入情况3：叔叔节点为黑色，且node为父节点的左孩子node->parent->parent->RB_COLOR = RED; //设当前节点父节点为黑色，祖父节点为红色RotateRight(node->parent->parent); //对祖父节点右旋}}else{ //这部分是针对插入情况1中，z的父亲作为祖父节点的右孩子的情况RB_Node* uncle = node->parent->parent->left;if (uncle->RB_COLOR == RED){node->parent->RB_COLOR = BLACK;uncle->RB_COLOR = BLACK;node->parent->RB_COLOR = RED;node = node->parent->parent;}else if (uncle->RB_COLOR == BLACK){if (node == node->parent->left){node = node->parent;RotateRight(node);}node->parent->RB_COLOR = BLACK;node->parent->parent->RB_COLOR = RED;RotateLeft(node->parent->parent);}}}m_root->RB_COLOR = BLACK; //最后把根节点设为黑色}bool RotateLeft(RB_Node *node){ //左旋操作if (node == m_nullNode || node->right == m_nullNode){return false; //不能旋转}RB_Node *lower_right = node->right;lower_right->parent = node->parent;node->right = lower_right->left;if (lower_right->left != m_nullNode){lower_right->left->parent = node;}if (node->parent == m_nullNode){m_root = lower_right;m_nullNode->left = m_root;m_nullNode->right = m_root;}else {if (node == node->parent->left){node->parent->left = lower_right;}else{node->parent->right = lower_right;}}node->parent = lower_right;lower_right->left = node;}bool RotateRight(RB_Node *node){ //右旋操作if (node == m_nullNode || node->left == m_nullNode){return false;}RB_Node *lower_left = node->left;lower_left->parent = node->parent;node->left = lower_left->right;if (lower_left->right != m_nullNode){lower_left->right->parent = node;}if (node->parent == m_nullNode){m_root = lower_left;m_nullNode->left = m_root;m_nullNode->right = m_root;}else{if (node == node->parent->right){node->parent->right = lower_left;}else {node->parent->left = lower_left;}}node->parent = lower_left;lower_left->right = node;}/*//--------------------------删除结点总操作----------------------------------TREE - DELETE(T, z)1 if left[z] = NIL or right[z] = NIL2 then y ← z3 else y ← TREE - SUCCESSOR(z)4 if left[y] ≠ NIL5 then x ← left[y]6 else x ← right[y]7 if x ≠ NIL8 then p[x] ← p[y]9 if p[y] = NIL10 then root[T] ← x11 else if y = left[p[y]]12 then left[p[y]] ← x13 else right[p[y]] ← x14 if y ≠ z15 then key[z] ← key[y]16 copy y's satellite data into z17 return y*/bool Delete(KEY key){ //根据关键字的值删除一个节点RB_Node *delete_point = find(key);if (delete_point == m_nullNode){return false;}if (delete_point->left != m_nullNode && delete_point->right != m_nullNode){RB_Node *successor = InOrderSuccessor(delete_point);delete_point->data = successor->data;delete_point->key = successor->key;//将delete_point指向替换后的节点，即要删除节点右子树的最小节点delete_point = successor;}RB_Node *delete_point_child;if (delete_point->right != m_nullNode){delete_point_child = delete_point->right;}else if (delete_point->left != m_nullNode){delete_point_child = delete_point->left;}else delete_point_child = m_nullNode;delete_point_child->parent = delete_point->parent;if (delete_point->parent == m_nullNode){m_root = delete_point_child;m_nullNode->left = m_root;m_nullNode->right = m_root;m_nullNode->parent = m_root;}else if (delete_point == delete_point->parent->right){delete_point->parent->right = delete_point_child;}else {delete_point->parent->left = delete_point_child;}//修复红黑树的结构if (delete_point->RB_COLOR == BLACK && !(delete_point_child == m_nullNode && delete_point_child->parent == m_nullNode)){DeleteFixUp(delete_point_child);}delete delete_point;return true;}//---------------------删除结点性质修复----------------------------------- //所有的工作，都在下述23行伪代码中： /*RB-DELETE-FIXUP(T, x)1 while x ≠ root[T] and color[x] = BLACK2 do if x = left[p[x]]3 then w ← right[p[x]]4 if color[w] = RED5 then color[w] ← BLACK ? Case 16 color[p[x]] ← RED ? Case 17 LEFT-ROTATE(T, p[x]) ? Case 18 w ← right[p[x]] ? Case 19 if color[left[w]] = BLACK and color[right[w]] = BLACK10 then color[w] ← RED ? Case 211 x p[x] ? Case 212 else if color[right[w]] = BLACK13 then color[left[w]] ← BLACK ? Case 314 color[w] ← RED ? Case 315 RIGHT-ROTATE(T, w) ? Case 316 w ← right[p[x]] ? Case 317 color[w] ← color[p[x]] ? Case 418 color[p[x]] ← BLACK ? Case 419 color[right[w]] ← BLACK ? Case 420 LEFT-ROTATE(T, p[x]) ? Case 421 x ← root[T] ? Case 422 else (same as then clause with "right" and "left" exchanged)23 color[x] ← BLACK*///接下来的工作，很简单，即把上述伪代码改写成c++代码即可。 void DeleteFixUp(RB_Node *node){while (node != m_root && node->RB_COLOR == BLACK){if (node == node->parent->left){RB_Node *brother = node->parent->right;if (brother->RB_COLOR == RED){ //情况1：x的兄弟为红色的brother->RB_COLOR = BLACK; //将兄弟节点设为黑色node->parent->RB_COLOR = RED; //将父节点设为红色RotateLeft(node->parent); //父节点左旋}else{if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK){//兄弟节点和其两个孩子节点都为黑色brother->RB_COLOR = RED; //将兄弟节点设为红色node = node->parent; //当前节点设为父节点}else if (brother->right->RB_COLOR == BLACK){//兄弟节点为黑色，左孩子节点为红色brother->RB_COLOR = RED; //将兄弟节点设为红色，其左孩子设为黑色brother->left->RB_COLOR = BLACK; RotateRight(brother); //对兄弟节点右转}//情况4：兄弟节点为黑色，兄弟节点的右孩子为红色brother->RB_COLOR = node->parent->RB_COLOR;node->parent->RB_COLOR = BLACK; //将兄弟节点设为父节点的颜色，父节点设为黑色brother->right->RB_COLOR = BLACK; //将兄弟节点的右孩子节点设为黑色RotateLeft(node->parent); //对当前节点父节点左转node = m_root; //将当前节点设为根节点}}else{RB_Node* brother = node->parent->left;if (brother->RB_COLOR == RED){brother->RB_COLOR = BLACK;node->parent->RB_COLOR = RED;RotateRight(node->parent);}else{if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK){brother->RB_COLOR = RED;node = node->parent;}else if (brother->left->RB_COLOR == BLACK){brother->RB_COLOR = RED;brother->right->RB_COLOR = BLACK;RotateLeft(brother);}brother->RB_COLOR = node->parent->RB_COLOR;node->parent->RB_COLOR = BLACK;brother->left->RB_COLOR = BLACK;RotateRight(node->parent);node = m_root;}}}m_nullNode->parent = m_root; //最后将node置为根节点node->RB_COLOR = BLACK; //并改为黑色}inline RB_Node* InOrderPredecessor(RB_Node* node){if (node == m_nullNode){return m_nullNode;}RB_Node *result = node->left; //获得节点的左孩子while (result != m_nullNode){if (result->right != m_nullNode){result = result->right;}else break;}if (result == m_nullNode){RB_Node *index = node->parent;result = index;while (index != m_nullNode && result == index->left){result = index;index = index->parent;}result = index;}return result;}inline RB_Node* InOrderSuccessor(RB_Node* node){if (node == m_nullNode){return false;}RB_Node *result = node->right;while (result != m_nullNode){if (result->left != m_nullNode){result = result->left;}else break;}if (result == m_nullNode){RB_Node *index = node->parent;result = node;while (index != m_nullNode && result == index->right){result = index;index = index->parent;}result = index;}return result;}//debug void InOrderTraverse(){InOrderTraverse(m_root);}//void CreateGraph(string filename)//{// //delete //}//void InOrderCreate(ofstream& file, RB_Node* node)//{// //delete //}void InOrderTraverse(RB_Node* node){if (node == m_nullNode){return;}else{InOrderTraverse(node->left);cout << node->key << endl;InOrderTraverse(node->right);}}~RB_Tree(){clear(m_root);delete m_nullNode;}
private:void clear(RB_Node* node){if (node == m_nullNode)return;else{clear(node->left);clear(node->right);delete node;}}
};#endif
RB_Tree.cpp
#include<iostream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<sstream>
#include"RBTree.h" //如果.h文件，和cpp文件放在一个文件里，此句去掉
using namespace std;int main(){RB_Tree<int, int> tree;vector<int> res;for (int i = 0; i < 10; i++){res.push_back(i);}random_shuffle(res.begin(), res.end());copy(res.begin(), res.end(), ostream_iterator<int>(cout, " "));cout << endl;stringstream sstr;for (int i = 0; i < res.size(); i++){tree.Insert(res[i], i);cout << "insert: " << res[i] << endl;}for (int i = 0; i < res.size(); i++){cout << "Delete: " << res[i] << endl;tree.Delete(res[i]);tree.InOrderTraverse();}cout << endl;tree.InOrderTraverse();system("pause");return 0;
}