目录

一、红黑树的概念

二、红黑树的性质

三、红黑树节点的定义

四、红黑树的插入

1. 按照二叉搜索的树规则插入新节点

2. 检测新节点插入后，红黑树的性质是否造到破坏

情况一: cur为红，p为红，g为黑，u存在且为红

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

五、红黑树的验证

六、红黑树和AVL树的比较

---

一、红黑树的概念

        红黑树，是一种二叉搜索树，但是在每个节点上增加了一个存储位表示节点的颜色，可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个节点颜色的某种限制，红黑树保证了没有一条路径会比最短路径长出两倍，所以红黑树是一种接近平衡的搜索二叉树。

二、红黑树的性质

1.每个节点不是红色就是黑色

2.根节点是黑色的

3.如果一个节点是红色的，那么他的两个孩子节点是黑色的（即不能有连续的红色节点）

4.对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含一样数量的黑色节点

5.每个叶子节点都是黑色的（这里的叶子节点指的是空节点，也叫NIL节点）

三、红黑树节点的定义

	enum Color{RED,BLACK};template<class K,class V>struct RBTreeNode{typedef RBTreeNode<K, V> Node;Node* _left;Node* _right;Node* _parent;pair<K, V> _kv;Color _col;//构造函数RBTreeNode(const pair<K,V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}};

        为什么红黑树的节点默认是红色呢？因为如果插入黑色节点，会违反规则4，但是插入红色节点，只有可能影响规则3（不能有连续的红色节点），调整起来比较方便。

四、红黑树的插入

1. 按照二叉搜索的树规则插入新节点

template<class ValueType>
class RBTree
{//……
bool Insert(const ValueType& data)
{
PNode& pRoot = GetRoot();
if (nullptr == pRoot)
{
pRoot = new Node(data, BLACK);
// 根的双亲为头节点
pRoot->_pParent = _pHead;_pHead->_pParent = pRoot;
}
else
{
// 1. 按照二叉搜索的树方式插入新节点// 2. 检测新节点插入后，红黑树的性质是否造到破坏，
//  若满足直接退出，否则对红黑树进行旋转着色处理
}
// 根节点的颜色可能被修改，将其改回黑色
pRoot->_color = BLACK;
_pHead->_pLeft = LeftMost();
_pHead->_pRight = RightMost();
return true;
}
private:
PNode& GetRoot(){ return _pHead->_pParent;}private:
PNode _pHead;

2. 检测新节点插入后，红黑树的性质是否造到破坏

        因为新节点的默认颜色是红色，因此，：如果其父亲节点是黑色，就没有违反红黑树的性质，则不需要调整，可以直接插入。但是当父亲节点为红色的时候，则违反了性质三（不能有连续的红色节点），此时需要对红黑树进行分类讨论。

        约定：cur为当前节点，p为父节点，g为祖父节点，uncle为叔叔节点

情况一: cur为红，p为红，g为黑，u存在且为红

解决方式：将p,u改为黑，g改为红，然后把g当成cur，继续向上调整。

情况二: cur为红，p为红，g为黑，u不存在/u存在且为黑

        但是对于情况二：我们需要分类讨论，因为cur在parent的左边和右边/parent在祖父的左边和右边所产生的旋转是不同的，一共需要分成4类来讨论

template<class K,class V>class RBTree{typedef RBTreeNode<K, V> Node;public:bool insert(const pair<K,V>& kv){//先按照普通搜索二叉树的规则插入节点if (_root==nullptr){_root = new Node(kv);return true;}else{//找到要插入的位置Node* cur = _root;Node* parent = cur->_parent;while (cur!=nullptr){if (kv.first<cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first>cur->_kv.first){parent = cur;cur = cur->_right;}else if (kv.first==cur->_kv.first){return false;}}//cur是连接到parent的左边还是右边呢cur = new Node(kv);if (cur->_kv.first<parent->_kv.first){parent->_left = cur;cur->_parent = parent;}else if (cur->_kv.first>parent->_kv.first){parent->_right = cur;cur->_parent = parent;}//根据红黑树的规则进行变色+旋转//只有当父亲是红色且存在，才需要处理，因为父亲是黑色对上面没有影响可以直接插入while (parent!=nullptr&&parent->_col==RED){Node* grandparent = parent->_parent;//parent==grandparent->_leftif (parent==grandparent->_left){Node* uncle = grandparent->_right;//叔叔存在且为红色if (uncle!=nullptr&&uncle->_col==RED){//变色parent->_col = uncle->_col = BLACK;grandparent->_col = RED;//grandparent给cur继续向上调整cur = grandparent;parent = grandparent->_parent;}//叔叔不存在或者存在且为黑色else{if (cur==parent->_left){//右单旋_RotateR(grandparent);//变色grandparent->_col = RED;parent->_col = BLACK;}else{//双旋_RotateL(parent);_RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}//因为走到else结束后，parent右一种情况是是黑色，有一种情况是红色，但是都以及调整好了，//不需要再往上调整，所以直接breakbreak;}}//parent==grandparent->_rightelse{Node* uncle = grandparent->_left;if (uncle!=nullptr&&uncle->_col==RED){//变色uncle->_col = parent->_col = BLACK;grandparent->_col = RED;//继续往上处理cur = grandparent;parent = grandparent->_parent;}else{if (cur==parent->_right){//左旋_RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{//双旋_RotateR(parent);_RotateL(grandparent);//变色cur->_col = BLACK;grandparent->_col = RED;}break;}}}}//根必须要是黑色_root->_col = BLACK;return true;}//右单旋void _RotateR(Node* parent){//记录两个重要节点Node* subL = parent->_left;Node* subLR = subL->_right;//连接parent->_left = subLR;//如果subL的右边为空，空不能解引用，需要注意一下if (subLR->_right != nullptr){subLR->_parent = parent;}subL->_right = parent;//处理根的问题Node* grandparent = parent->_parent;parent->_parent = subL;subL->_parent = grandparent;//如果原本parent是根，则让_root=subLif (parent == _root){_root = subL;subL->_parent = nullpptr;}//如果parent是子树，则连接subL和grandparentelse{if (grandparent->_right == parent){grandparent->_right = subL;}else if (grandparent->_left == parent){grandparent->_left = subL;}}}//左单旋void _RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* grandparent = parent->_parent;parent->_parent = subR;if (subRL != nullptr){subRL->_parent = parent;}//处理根的问题if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (parent == grandparent->_right){grandparent->_right = subR;}else if (parent == grandparent->_left){grandparent->_left = subR;}}}private:Node* _root = nullptr;};
}

五、红黑树的验证

        红黑树的验证检测分为两步：

（1）检测其是非满足二叉搜索树的规则（中序是否为有序）

（2）检测其是否满足红黑树的性质

bool isBalance(){if (_root==nullptr){return true;}if (_root->_col==RED){return false;}//求参考值int refval = 0;Node* cur = _root;while (cur!=nullptr){if (cur->_col==BLACK){refval++;}cur = cur->_left;}return Check(_root, 0, refval);}//检查颜色是否符合规则和黑色节点的数量是否相同//blacknum是根节点到当前节点路径上的黑色节点数量bool Check(Node* root,int blacknum,const int refVal){//走到空的时候说明该路径已经走完了，比对balcknum的值if (root==nullptr){if (blacknum!=refVal){cout << "存在不同路径的黑色节点数量不相等" << endl;return false;}return true;}//因为检测孩子不好检测，有多种情况，所以我们反过来从孩子检测父亲的颜色if (root->_col==RED&& root->_parent->_col == RED){cout << "有连续的红色节点" << endl;return false;}if (root->_col==BLACK){blacknum++;}return Check(root->_left,blacknum,refVal)&& Check(root->_right,blacknum,refVal);}

六、红黑树和AVL树的比较

        红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是O($log_2 N$)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，（不过像词典这种增删的比较少的项目，AVL由于其追求绝对平衡，所以查找的效率更高）而且红黑树实现比较简单，所以实际运用中红黑树更多。

        红黑树常常因为其高效的性能，而被用到map/set等数据结构中。