一、概念
红黑树，是一种二叉搜索树。但在每个结点上增加一个存储位表示结点的颜色，可以是Red或
Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路
径会比其他路径长出两倍，因而是接近平衡的。
性质:
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 若一个节点是红色的，则它的两个孩子结点是黑色的(即树中没有连续的红色结点)
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点(即每条路径上黑色结点数量相等)
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NIF)
二、红黑树的插入操作
红黑树的插入操作大致可以分成两步:
第一步: 按照二叉搜索树的规则插入新节点
bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new TreeNode(kv); _root->_color = BLACK; return true; } TreeNode* parent = nullptr; TreeNode* cur = _root; while (cur != nullptr) { if (kv.first > cur->_data.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_data.first) { parent = cur; cur = cur->_left; } else return false; } cur = new TreeNode(kv); cur->_color = RED; if (kv.first > parent->_data.first) { parent->_right = cur; } else { //kv.first < parent->_data.first) parent->_left = cur; } cur->_parent = parent; //……………… }
第二步: 插入后检测性质是否造到破坏，若遭到破坏则进行调整
新节点的默认颜色是红色，若其双亲结点的颜色是黑色，没有违反红黑树任何性质，则不需要调整；但当新插入结点的双亲结点颜色为红色时，就出现了连续的红色结点，此时需要对红黑树分情况来讨论：
情况一: cur为红，parent为红，grandfather为黑，uncle存在且为红
if (uncle != nullptr && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = cur->_parent; }
情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑(单旋+变色)
uncle的情况有两种:
1.若uncle结点不存在时，cur结点一定是新增结点。若cur不是新增结点，则cur和parent之间一定有一个黑色结点。这不满足性质4:每条路径上黑色结点的个数相同。
2.若uncle存在且为黑色，那么cur原来的颜色一定为黑色。看到cur结点是红色，是因为cur的子树在调整的过程中将cur的颜色从黑色改变为红色。
//右单旋 + 变色 if (cur == parent->_left) { rotate_right(grandfather); grandfather->_color = RED; parent->_color = BLACK; } //左单旋 + 变色 if (cur == parent->_right) { rotate_left(grandfather); grandfather->_color = RED; parent->_color = BLACK; }
情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑(双旋+变色)
//左右双旋 + 变色 else {//cur == parent->_right rotate_left(parent); rotate_right(grandfather); cur->_color = BLACK; grandfather->_color = RED; } //右左双旋 + 变色 else {//cur == parent->_left rotate_right(parent); rotate_left(grandfather); cur->_color = BLACK; grandfather->_color = RED; }
三、红黑树的验证
红黑树的检测分为两步：
检测其是否满足二叉搜索树
使用中序遍历判断其是否有序即可，这里不做过多解释
检测其是否满足红黑树的性质
bool IsBalance() { //空树也是红黑树 if (_root == nullptr) return true; //根结点是黑色的 if (_root->_color != BLACK) return false; int benchmark = 0;//基准值 return _IsBalance(_root, 0, benchmark); } bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) { if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum;//将第一条路径的blackNum设为基准值 return true; } else { return blackNum == benchmark; } } if (root->_color == BLACK) ++blackNum; if (root->_color == RED && root->_parent->_color == RED) return false; //逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点 return _IsBalance(root->_left, blackNum, benchmark) && _IsBalance(root->_right, blackNum, benchmark); }
四、完整代码
#include<iostream> #include<cassert> using std::pair; using std::make_pair; using std::cout; using std::cout; using std::endl; enum Color { RED,BLACK }; template<class K,class V> struct RedBlackTreeNode { RedBlackTreeNode(const pair<K, V>& kv) : _parent(nullptr), _left(nullptr), _right(nullptr), _data(kv), _color(RED){} RedBlackTreeNode<K, V>* _parent; RedBlackTreeNode<K, V>* _left; RedBlackTreeNode<K, V>* _right; pair<K, V> _data; Color _color; }; template<class K,class V> class RedBlackTree { typedef RedBlackTreeNode<K, V> TreeNode; public: bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new TreeNode(kv); _root->_color = BLACK; return true; } TreeNode* parent = nullptr; TreeNode* cur = _root; while (cur != nullptr) { if (kv.first > cur->_data.first) { parent = cur; cur = cur->_right; } else if (kv.first < cur->_data.first) { parent = cur; cur = cur->_left; } else return false; } cur = new TreeNode(kv); cur->_color = RED; if (kv.first > parent->_data.first) { parent->_right = cur; } else { //kv.first < parent->_data.first) parent->_left = cur; } cur->_parent = parent; while (parent && parent->_color == RED) { TreeNode* grandfather = parent->_parent; assert(grandfather != nullptr); //当parent结点为红时，grandfather结点必不为空(根结点为黑) assert(grandfather->_color == BLACK); //当parent结点为红时，grandfather结点必为黑色(否则违反性质，出现连续的红色结点) if (parent == grandfather->_left) { TreeNode* uncle = grandfather->_right; if (uncle != nullptr && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = cur->_parent; } else {//uncle不存在或者为黑 //右单旋 + 变色 if (cur == parent->_left) { rotate_right(grandfather); grandfather->_color = RED; parent->_color = BLACK; } //左右双旋 + 变色 else {//cur == parent->_right rotate_left(parent); rotate_right(grandfather); cur->_color = BLACK; grandfather->_color = RED; } break; } } else {//parent == grandfather->_right TreeNode* uncle = grandfather->_left; if (uncle != nullptr && uncle->_color == RED) { parent->_color = uncle->_color = BLACK; grandfather->_color = RED; cur = grandfather; parent = cur->_parent; } else {//uncle不存在或者为黑 //左单旋 + 变色 if (cur == parent->_right) { rotate_left(grandfather); grandfather->_color = RED; parent->_color = BLACK; } //右左双旋 + 变色 else {//cur == parent->_left rotate_right(parent); rotate_left(grandfather); cur->_color = BLACK; grandfather->_color = RED; } break; } } } _root->_color = BLACK; return true; } void inorder() { _inorder(_root); } bool IsBalance() { //空树也是红黑树 if (_root == nullptr) return true; //根结点是黑色的 if (_root->_color != BLACK) return false; int benchmark = 0;//基准值 return _IsBalance(_root, 0, benchmark); } private: void _inorder(TreeNode* root) { if (root == nullptr) { return; } _inorder(root->_left); cout << root->_data.first << ":" << root->_data.second << " "; _inorder(root->_right); } bool _IsBalance(TreeNode* root, int blackNum, int& benchmark) { if (root == nullptr) { if (benchmark == 0) { benchmark = blackNum; return true; } else { return blackNum == benchmark; } } if (root->_color == BLACK) ++blackNum; if (root->_color == RED && root->_parent->_color == RED) return false; //逻辑短路，若root结点为红色，其就不可能为根结点，一定有parent结点 return _IsBalance(root->_left, blackNum, benchmark) && _IsBalance(root->_right, blackNum, benchmark); } void rotate_left(TreeNode* parent) { TreeNode* subR = parent->_right; TreeNode* subRL = subR->_left; TreeNode* pparent = parent->_parent; parent->_right = subRL; if (subRL != nullptr) subRL->_parent = parent; subR->_left = parent; parent->_parent = subR; //解决根结点变换带来的问题 if (_root == parent) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } } void rotate_right(TreeNode* parent) { TreeNode* subL = parent->_left; TreeNode* subLR = subL->_right; TreeNode* pparent = parent->_parent; parent->_left = subLR; if (subLR != nullptr) subLR->_parent = parent; subL->_right = parent; parent->_parent = subL; if (_root == parent) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } } private: TreeNode* _root = nullptr; }; void RBTreeTest() { size_t N = 10000; srand((unsigned)time(NULL)); RedBlackTree<int, int> t; for (size_t i = 0; i < N; ++i) { int x = rand(); //cout << "insert:" << x << ":" << i << endl; t.insert(make_pair(x, i)); } t.inorder(); cout << t.IsBalance() << endl; } int main() { RBTreeTest(); return 0; }
五、红黑树与AVL树的比较
与AVL树的平衡 (左右高度差不超过1) 相比，红黑树的平衡(没有一条路径会比其他路径长出两倍)并没有那么严格。所以两者在插入或删除相同数据时，红黑树需要旋转调整的次数更少，这使得红黑树的性能略高于AVL树。
可是AVL树更加平衡，查找数据所需的次数不是更加少吗？在AVL树与红黑树中进行数据的查找都十分快捷(譬如在查找100万数据中进行查找只需大概20次)，对于CPU从时间上来说并不会造成什么负担。
总的来说，AVL树更适用于插入删除不频繁，只对查找要求较高的场景; 红黑树相较于AVL树更适应对插入、删除、查找要求都较高的场景，红黑树在实际中运用更加广泛。
