一、概念
红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（并不是像AVL树那样高度差一定不超过1）。
最长路径长度不超过最短路径长度的 2 倍。
如下图就是一棵红黑树：
注：树的路径是从根节点走到NIL节点才算一条路径。
二、红黑树的性质
1、 每个结点不是红色就是黑色。
2、根节点是黑色的。
3、如果一个节点是红色的，则它的两个孩子结点是黑色的。（没有连续的红色结点）
4、 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
5、每个叶子结点都是黑色的(此处的叶子结点指的是空结点）。
三、结点的实现
在结点的实现中，我们要需要一个变量来控制它的颜色，因此我们可以使用枚举来列出两种颜色，再在结点中定义颜色。
enum Colour { RED, BLACK }; template<class K,class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv, Colour col = RED) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(col) {} };
上面的代码我们在创建结点后，就直接将新节点的颜色默认设置成了红色，那么为什么要默认设置成红色，而不是黑色呢？
首先，如果我们插入黑色结点，将会违背性质4，因为某条路径上一定会多出一个黑色结点，这样就需要去调节所有路径的黑色结点，非常麻烦。
如果我们插入的是红色结点，那么我们就可能违背了性质3，因为如果新插入结点的父亲是黑色那么我们就不需要进行调整。
所以总的来说，新插入结点是红色，红黑树的结构维护起来更加方便。
四、红黑树的插入
一般步骤：
1、按照二叉搜索的树规则插入新节点（即：插入值与结点值比较，小于节点值就往左子树插入，反之往右子树插入）。
2、判断红黑树的结构是否被破坏：
因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何
性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连
在一起的红色节点，此时需要对红黑树分情况来讨论：（cur为当前结点，p为父亲结点，g为祖父结点，u为叔叔结点）。
* 情况一：cur为红，p为红，g为黑，u存在且为红
该情况的处理方式为：将P和U结点变黑，再将g变红。
如果g是根节点，调整完成后，要将g改为黑色，如果g是子树，那么如果g的双亲是红色，就需要然后把g当成cur，继续向上调整。
* 情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑，g/p/cur在同一侧
此时u的情况有两种：
1、如果u结点不存在，则cur一定是新增结点，因为如果cur不是新增结点：则cur和p一定有一个节点时黑色，就不满足每条路径都有相同的黑色结点的性质。
2、如果u结点存在，则其一定是黑色的，那么cur节点原来的颜色一定是黑色，在其子树调整过程中变为了红色。
p为g的左孩子，cur为p的左孩子，则进行右单旋；相反，p为g的右孩子，cur为p的右孩子，则进行左单旋。p变为黑色，g变为红色。
* 情况三：cur为红，p为红，g为黑，u不存在/u存在且为黑，g/p/cur不在同一侧
p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转 。旋转之后则转换成了情况二，再继续进行调整即可。
代码实现如下：
bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); cur->_col = RED; //将新插入结点置成红色 if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; assert(grandfather); assert(grandfather->_col == BLACK); if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } // uncle 不存在 + 存在且为黑 else { if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; }
五、完整代码
RBTree.h
#pragma once #include<iostream> #include<cassert> using namespace std; enum Colour { RED, BLACK }; template<class K,class V> struct RBTreeNode { RBTreeNode<K, V>* _left; RBTreeNode<K, V>* _right; RBTreeNode<K, V>* _parent; pair<K, V> _kv; Colour _col; RBTreeNode(const pair<K, V>& kv, Colour col = RED) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) , _col(col) {} }; template<class K, class V> struct RBTree { typedef RBTreeNode<K, V> Node; public: bool insert(const pair<K, V>& kv) { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else { return false; } } cur = new Node(kv); if (parent->_kv.first > kv.first) { parent->_left = cur; } else { parent->_right = cur; } cur->_parent = parent; while (parent && parent->_col == RED) { Node* grandfather = parent->_parent; assert(grandfather); assert(grandfather->_col == BLACK); if (parent == grandfather->_left) { Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } // uncle 不存在 + 存在且为黑 else { if (cur == parent->_left) { RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else { Node* uncle = grandfather->_left; if (uncle && uncle->_col == RED) { parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上处理 cur = grandfather; parent = cur->_parent; } else { if (cur == parent->_right) { RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else { RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } void InOrder() { _InOrder(_root); cout << endl; } private: void RotateL(Node* parent) //左单旋 { Node* subR = parent->_right; Node* subRL = subR->_left; Node* pparent = parent->_parent; subR->_left = parent; parent->_parent = subR; parent->_right = subRL; if (subRL) subRL->_parent = parent; if (parent == _root) { _root = subR; subR->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subR; else pparent->_right = subR; subR->_parent = pparent; } } void RotateR(Node* parent) //右单旋 { Node* subL = parent->_left; Node* subLR = subL->_right; Node* pparent = parent->_parent; parent->_parent = subL; subL->_right = parent; parent->_left = subLR; if (subLR) subLR->_parent = parent; if (parent == _root) { _root = subL; subL->_parent = nullptr; } else { if (pparent->_left == parent) pparent->_left = subL; else pparent->_right = subL; subL->_parent = pparent; } } void _InOrder(Node* root) { if (root == nullptr) return; _InOrder(root->_left); cout << root->_kv.first << ":" << root->_kv.second << endl; _InOrder(root->_right); } private: Node* _root = nullptr; }; void test() { int a[] = { 4,2,6,1,3,5,15,7,16,14 }; RBTree<int, int> t; for (auto e : a) { t.insert(make_pair(e, e)); } t.InOrder(); }
test.cpp
#include"RBTree.h" int main() { test(); return 0; }
运行结果：
