前言

在了解完平衡搜索二叉树的优势和应用后，我们学习了AVL树这种方案来实现它，但在前人们的不断使用和开辟，另一种更优的方案横空出世——红黑树。

一、红黑树概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。

二、红黑树的性质

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

2. 根节点是黑色的

3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红节点）

4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。（核心）

5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？

答案：下面标黄处。

由红黑树的概念得知，红黑树方案和AVL树的方案对比，我们可以得知：

• AVL树是一颗宁折不弯的树：它容不下一点偏差，AVL树任何时候都是一颗绝对的平衡搜索二叉树；但是也由于这个特性，当我们面对频繁的修改时，它将会频繁的调整（旋转）自己以达到，标准平衡搜索二叉树的要求，这会导致效率的下降。

• 红黑树是一颗懂得卸力的树，我们通过红黑树性质的3、4点得知，2 * 最短路径的节点数 <= 最长路径的节点数（注：以极限的思想，最短路径全黑，最长路径一黑一红交替出现（性质3），2条路径黑节点数相同（性质4）），这就导致了虽然红黑树允许个别子树可能不平衡但是，由于该机制不会退化的很极端，而且每一次的修改都有可能将之前的不平衡抵消（AVL就不行），最后的结果就是，虽然红黑树不是一颗标准的平衡搜索二叉树，但是它将不平衡限制在了可控范围中，虽然搜索时可能会效率不及AVL树但是，由于不会频繁的调整，反而是提升了效率。

三、红黑树的实现

在把红黑树的逻辑了解完后，我们来实现一下吧。

3.1红黑树节点的定义

// 节点的颜色
enum Color{RED, BLACK};
// 红黑树节点的定义
template
struct RBTreeNode
{RBTreeNode(const ValueType& data = ValueType()，Color color = RED): _pLeft(nullptr),_pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNode* _pLeft; // 节点的左孩子RBTreeNode* _pRight; // 节点的右孩子RBTreeNode* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)ValueType _data; // 节点的值域Color _color; // 节点的颜色
};

在节点的定义中，为什么要将节点的默认颜色给成红色的？

我们会头看红黑树的性质4，知道每条路径的黑节点数是相同的，你如果插入的节点颜色默认为黑色可就有得写了。有同学会说那如果插入节点的父节点为红色，那不是与性质3不能有连续的红节点违背了吗？没错，所以这时候我们就要调整了（详情请看红黑树的插入）

3.2红黑树的头节点

为了后续实现关联式容器简单，红黑树的实现中增加一个头结点，因为跟节点必须为黑色，为了与根节点进行区分，将头结点给成黑色，并且让头结点的 pParent 域指向红黑树的根节点，pLeft域指向红黑树中最小的节点，_pRight域指向红黑树中最大的节点，如下：

3.3红黑树的插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

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

template
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;}// 获取红黑树中最小节点，即最左侧节点PNode LeftMost();// 获取红黑树中最大节点，即最右侧节点PNode RightMost();
private:PNode _pHead;
};

② 检测新节点插入后，红黑树的性质是否造到破坏（重点）

先看每种情况下如何处理，最后有总结帮助记忆

因为新节点的默认颜色是红色，因此：如果其双亲节点的颜色是黑色，没有违反红黑树任何

性质，则不需要调整；但当新插入节点的双亲节点颜色为红色时，就违反了性质三不能有连

在一起的红色节点，所以我们需要介入调整的情况双亲节点（父节点）和插入的节点都为红，

此时需要对红黑树分情况来讨论：

约定:cur为当前节点，p为父节点（parent），g为祖父节点（granparent），u为叔叔节点(uncle)

注：由于p节点和u节点不知道谁为g节点的左树或右树，由于左右2种情况的原理相同，仅仅是改变了指向而已，下文默认p为右节点，u为左节点方便解释

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

解析：在保证局部的每条路径的黑色节点数相同的前提，直接变色，由于修改了g节点颜色，有可能g节点的父节点为红，所以将g当作插入的红节点，向上循环调整直到g的父节点为黑色

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

//情况1：uncle为红色 -> 此时只有祖父节点为红色 + cur在parent2边插入都可以
if (uncle && uncle->_colour == RED)
{                //直接变色grandfather->_colour = RED;parent->_colour = BLACK;uncle->_colour = BLACK;
}

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

解析：从局部图发现插入前，p节点所在路径和u节点所在路径的黑色节点数不同，所以此时想直接通过变色就不行了（我知道有些同学有反骨，你可以试试看行不行），所以这里需要旋转 + 变色实现（啥？旋转是啥，你不知道，惩罚你去看这篇文章的前传——avl树篇有解释）。

解决方法（单旋 + 变色）：p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反，

p为g的右孩子，cur为p的右孩子，则进行左单旋转

p、g变色--p变黑，g变红

//情况2：左边插入 -> 右旋 + 变色
if (cur == parent->_left)
{RoateR(grandfather);parent->_colour = BLACK;grandfather->_colour = RED;
}

左旋

右旋

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

解析：这种情况其实就是情况二的变异版，我们先通过旋转p,cur节点（看清楚了不是旋转g节点）变回情况二就可以借助情况二的方法解决了（啥？反骨又来了，觉得变情况二麻烦，想直接旋转 + 变色解决，你试试如果直接旋转的话，能不能把g、p、cur这三个节点的树形状捋直）

解决方法（双旋 + 变色）：

p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，

p为g的右孩子，cur为p的左孩子，则针对p做右单旋转

则转换成了情况2

//情况3：右边插入 -> 左旋 变为情况2 -> 右旋（双旋）+ 变色
else
{RoateL(parent);RoateR(grandfather);cur->_colour = BLACK;grandfather->_colour = RED;
}

插入小结：

bool Insert(const T& kv){//根if (_data == nullptr){_data = new node(kv);_data->_colour = BLACK;return true;}//寻找合适的插入位置node* parent = nullptr;node* cur = _data;while (cur){if (cur->_data < kv){parent = cur;cur = cur->_right;}else if (cur->_kv > kv){parent = cur;cur = cur->_left;}else//相等return false;}//插入cur = new node(kv);cur->_parent = parent;if (parent->_kv.frist < kv)parent->_right = cur;elseparent->_left = cur;//如果插入的cur的父节点为黑则不用调整//调整（父节点为红 -> 祖父结点为“黑”）//-> 新插入节点（cur）、父节点（parent）、祖父节点（grandfather）都确定且都为红//只有2个条件不确定：//1:cur插入的是父节点的左右子树//2：uncle(叔叔)节点的颜色/是否存在while (parent && parent->_colour == RED){node* grandfather = parent->_parent;if (grandfather->_left == parent){node* uncle = grandfather->_right;//情况1：uncle为红色 -> 此时只有祖父节点为红色 + cur在parent2边插入都可以if (uncle && uncle->_colour == RED){                //直接变色grandfather->_colour = RED;parent->_colour = BLACK;uncle->_colour = BLACK;}//情况2、3：uncle为黑色/或不存在 + cur在parent左/右边插入 else{//情况2：左边插入 -> 右旋 + 变色if (cur == parent->_left){RoateR(grandfather);parent->_colour = BLACK;grandfather->_colour = RED;}//情况3：右边插入 -> 左旋 变为情况2 -> 右旋（双旋）+ 变色else{RoateL(parent);RoateR(grandfather);cur->_colour = BLACK;grandfather->_colour = RED;}break;}}else//右{node* uncle = grandfather->_left;if (uncle && uncle->_colour == RED){//直接变色grandfather->_colour = RED;parent->_colour = BLACK;uncle->_colour = BLACK;}else{if (cur == parent->_left){RoateL(grandfather);parent->_colour = BLACK;grandfather->_colour = RED;}//情况3：右边插入 -> 左旋 变为情况2 -> 右旋（双旋）+ 变色else{RoateR(parent);RoateL(grandfather);cur->_colour = BLACK;grandfather->_colour = RED;}break;}}}_data->_colour = BLACK;return true;}

降序插入

升序插入

随机插入

3.4红黑树的验证

红黑树的检测分为两步：

1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列)

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

bool IsValidRBTree()
{PNode pRoot = GetRoot();// 空树也是红黑树if (nullptr == pRoot)return true;// 检测根节点是否满足情况if (BLACK != pRoot->_color){cout << "违反红黑树性质二：根节点必须为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackCount = 0;PNode pCur = pRoot;while (pCur){if (BLACK == pCur->_color)blackCount++;pCur = pCur->_pLeft;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsValidRBTree(pRoot, k, blackCount);
}
bool _IsValidRBTree(PNode pRoot, size_t k, const size_t blackCount)
{//走到null之后，判断k和black是否相等if (nullptr == pRoot){if (k != blackCount){cout << "违反性质四：每条路径中黑色节点的个数必须相同" << endl;return false;}return true;}// 统计黑色节点的个数if (BLACK == pRoot->_color)k++;// 检测当前节点与其双亲是否都为红色PNode pParent = pRoot->_pParent;if (pParent && RED == pParent->_color && RED == pRoot->_color){cout << "违反性质三：没有连在一起的红色节点" << endl;return false;}return _IsValidRBTree(pRoot->_pLeft, k, blackCount) &&_IsValidRBTree(pRoot->_pRight, k, blackCount);
}

3.5红黑树的删除

这个引用一篇文章

http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html

四、红黑树的应用

1. C++ STL库 -- map/set、mutil_map/mutil_set

2. Java 库

3. linux内核

4. 其他一些库