红黑树是如何实现的？

一、红黑树的概念

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

二、红黑树的性质

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点必须是黑色的（即任何路径没有连续的红色结点）
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点（每条路径上的黑色结点个数相同，这里的路径包括空结点）
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点，已经不在是传统的叶子结点了，图中的NIL结点就是空结点）

这里对第四点做一补充说明

对于下面这棵树有11条路径，而不是5条路径，因为空结点也包括在内

如果不清楚上面的这一点，如果遇到下面这棵树，可能会误以为他是红黑树，实际上它不是红黑树。

如果我们不看每个空结点的话，它看上去有四条路径，且每条路径都只有两个黑色结点，看上去好像是红黑树。但是实际上要包括空结点，且空结点是黑色的。所以一共有九条路径，最左边的一条路径只有两个黑色结点，其他路径都有三个黑色结点。

第四点中说的虽然是每个结点的每条路径上的黑色结点个数相同，但是由于每个结点的祖先的路径是唯一确定的，所以我们只需要判断从根节点到每个空结点上的路径中黑色结点个数是否相同即可

那么为什么上面的性质可以保证最长路径不超过最长路径的两倍呢？

如下图所示， 最长路径就是黑红相间的情况，最短路径就是全黑的情况。其他路径都是在这两者之间的，此时我们也不难看出最长路径不超过最短路径的两倍。如果最短路径为N，那么最长路径就是2N-1，因为根节点一定是黑色的，最终的叶子结点也一定是黑色的。

三、红黑树和AVL树对比

既然有了AVL树，那么为什么要有红黑树呢？其实是因为AVL树太严格了。它要控制平衡就需要付出代价。而红黑树要求并不严格，综合来看，红黑树的综合性能其实更优

	AVL树	红黑树
高度对比	高度差不超过一	最长路径不超过最短路径的两倍
插入1000个值	logN---->10	2*logN---->20
插入10亿个值	logN---->30	2*logN---->60

我们可以看到，虽然他们的高度有点差异，但是他们的效率都是同一个量级的，而且cpu的速度是非常快的，这点效率对于cpu几乎没有任何区别

性能是同一量级的，但是AVL树控制严格平衡是需要付出代价的，插入和删除需要大量的旋转。

四、红黑树的插入

1. 红黑树的结点定义

如下所示， 由于红黑树有红色结点和黑色结点两种颜色。所以不妨我们使用一个枚举类型来进行表示。红黑树里面我们需要有一个pair类型来进行存储key和value类型的数据。然后我们定义三个指针，分别指向父亲，左孩子，右孩子。最后定义其的颜色。在构造函数中，我们将其的颜色默认设置为红色。

设置为红色是比较有讲究的。那是因为我们大多数场景下都是去创建一个新节点去插入的。如果我们插入的这个新结点是黑色的话，那么造成的后果就是违反了规则4，即每条路径上的黑色结点个数相同，显然这种情况要进行补救的话是十分麻烦的。还不如去插入红色结点，如果插入的是红色结点的话，仅仅有可能会违反规则3，也就是红色结点的孩子必须是黑色结点。这一点的话，我们还有的补救，因为仅仅影响本条路径。

enum Color
{RED,BLACK
};template<class K , class V>
struct RBTreeNode
{pair<K, V> _kv;RBTreeNode<K, V>* _left;RBTreeNode<K, V>* _right;RBTreeNode<K, V>* _parent;Color _color;RBTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_color(RED) // 插入红色结点，违反规则3，只影响一条路径，甚至可能不影响。如果插入黑色结点，违反规则4，影响所有路径{}
};

2. 父亲的颜色

因为我们要插入的结点是红色的，那么在我们插入的位置，它的父亲要么是红色的要么是黑色的。如果是黑色的，那么就是如下的情况

我们可以看到，似乎并未影响整棵树的结构，不违反任何一条规则。最短路径仍然不超过最长路径的两倍。每条路径上的黑色结点个数仍然相等。所以如果插入一个新节点以后，如果此处它的父亲是黑色的，完美，不需要做出任何修改即可。如果父亲甚至都不存在，那么这个结点就是这颗树了。我们只需要将这个结点变为黑色即可。如果父亲是红色的话，那么就比较麻烦了。

如下图所示，就是插入的时候父亲为红色，显然已经违反了规则3了，此时我们需要对这颗树进行处理了。

3. 叔叔的颜色为红色

如果我们插入了一个结点以后，此时，父亲结点为红色，且有父亲的兄弟，即叔叔，且叔叔的颜色是红色。

即如下的情况，uncle存在且为红

这样的话，我们可以将parent和uncle都变黑，然后让grandfather变红，即如下的情形

这样的话，在黑色结点数量不变的条件下，使得连续红色结点的问题暂时解决了。现在原本cur为红色的问题转换为了grandfather为红色的问题。

此时的话，如果这个grandfather如果没有父亲了，那么根据规则1，我们只需要让他变为黑色即可。此时仅仅只是所有的路径多了一个黑色结点。如果grandfather有父亲，那么我们只需要让grandfather变为cur，继续向上处理即可

在这里继续向上处理的时候又分为以下几种情况

1. grandfather没有父亲，那么直接让grandfather变黑即可
2. grandfather有父亲，且父亲为黑色，那么由于前面的树本身就是满足红黑树规则，这里改变了之后仍然满足红黑树规则，那么不处理即可
3. grandfather有父亲，且父亲为红色，这样的情况下，父亲为红色，就隐含了必然存在grandfather的grandfather，因为原来的树也要满足红黑树的规则，这样一来就是类似的问题继续往处理即可。

然后由于此时恰好uncle存在且为红，那么我们只需要按照前面的逻辑进行处理即可，即uncle和parent均变黑，然后grandfather变为红

然后又为了满足根节点为红，所以grandfather变为黑即可

4. 叔叔不存在

如下图所示，当叔叔不存在的时候，我们还插入了一个新节点以后，我们发现最长路径已经超过了最短路径的两倍了。这时候单纯的进行变色，已经无法解决问题了。我们需要旋转了。

所以我们就需要进行旋转＋变色了。

• 对于变色：与前面的情况类似，即本来parent和uncle都为红色的话，就把他们两个变为黑色，然后把grandfather变为红色就可以了。不过现在uncle不存在了。那我们就先不管它了，将parent变为黑色，grandfather变为红色就可以了。
• 对于旋转：这个就需要我们进行具体的分析了，看看究竟是左旋还是右旋还是双旋。具体判断规则与AVL基本是一致的，如果是直线那么就是单旋，我们只需要分析谁高就可以了。如果是折线就是双旋，我们还是分析哪边高就可以了。

如上图所示的情形就是右单旋就可以了

5. 叔叔存在且为黑

我们接着前面的图，我们继续插入一个新的结点

那么此时的uncle存在且为红，我们进行相应的处理后，变为如下的情况

这时候，我们遇到了新的情况，uncle存在且为黑

那么此时的处理情形就和前面的uncle不存在是一样的，直接旋转加变色。这里的如何旋转和变色统一结论后面详细讨论

总结

1. 红黑树的插入主要看uncle

2. uncle存在且为红，变色+继续往上更新

3. uncle不存在或uncle存在且为黑，旋转+变色

6. 插入的抽象图

• 如下是第一种情况，当cur为红，p为红，g为黑,u存在且为红的条件下。

在这种情况下，我们可以p和u改为黑色，g改为红，然后把g当成cur,继续向上调整。

上面是我们的抽象图，我们如果要具体细化每一种情况的下是非常之麻烦的

比如说当a、b、c、d、e均为空，即cur是新增结点的时候，如下所示

当a,b不为空，且cur是黑色结点。那么cde都是含有一个结点的子树，那么cde的每个样子都有四种情况，如下所示

由于它可以在a,b这两个红色结点任意处进行插入，也就是说，可以在四个位置插入。

那么这种变换的情况就复杂很多，有4*4*4*4共256种情况

如果cde有两个黑节点的话，那么情况将更加复杂，画图已经很难表示出来了

显然我们如果用具象图的话，那么红黑树有无数种情况，所以我们只能使用抽象图来表示这种情况。

所以根据前面的分析，我们就可以写出如下的代码了。下面只是处理颜色的部分。

		//开始处理颜色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){}}else{Node* uncle = grandfather->_left;if (uncle&& uncle->_color = RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){}}}

• 接下来，我们讨论第二种情况，即cur为红，p为红，g为黑，u不存在/u存在且为黑

首先来分析uncle不存在的情况下，即如下的情况。此时我们可以注意到，由于uncle不存在，那么cur必然就是新插入的结点。此时我们就根据当前的cur与p的关系来确定是单旋还是双旋。旋转之后，进行变色。在这里的变色中，如果是单旋，就是g和p变色即可。如果是双旋，那么就是cur和g变色

1. p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反p为g的右孩子，cur为p的右孩子，则进行左单旋转

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

2. p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，此时转化了为了第一步的情况

再来看一下uncle存在且为黑的情况下。由于uncle存在且为黑，所以cur之前必然为黑色的，因为为了满足每条路径上的黑色结点个数相同，就代表着，cur必须为先前向上处理后的，在向上处理过程中，cur变为了红色。

当uncle存在且为黑的情况下，他的变色以及旋转规则都是与uncle不存在是一模一样的

1. p为g的左孩子，cur为p的左孩子，则进行右单旋转；相反p为g的右孩子，cur为p的右孩子，则进行左单旋转

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

2. 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->_color = BLACK; //根节点必须是黑色return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv); //插入红色结点if (parent->_kv.first < kv.first){parent->_right = cur;}else if (parent->_kv.first > kv.first){parent->_left = cur;}cur->_parent = parent;//开始处理颜色while (parent && parent->_color == RED){Node* grandfather = parent->_parent;if (grandfather->_left == parent){Node* uncle = grandfather->_right;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){if (parent->_left == cur){RotateR(grandfather);parent->_color = BLACK;grandfather->_color = RED;break;}else{RotateL(parent);RotateR(grandfather);cur->_color = BLACK;grandfather->_color = RED;break;}}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_color == RED){parent->_color = BLACK;uncle->_color = BLACK;grandfather->_color = RED;cur = grandfather;parent = grandfather->_parent;}else if (uncle == nullptr || uncle->_color == BLACK){if (parent->_right == cur){RotateL(grandfather);grandfather->_color = RED;parent->_color = BLACK;break;}else{RotateR(parent);RotateL(grandfather);cur->_color = BLACK;grandfather->_color = RED;break;}}}}_root->_color = BLACK;return true;}void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;Node* ppnode = parent->_parent;//改变parentparent->_right = curleft;parent->_parent = cur;//改变curleftif (curleft != nullptr){curleft->_parent = parent;}//改变curcur->_left = parent;cur->_parent = ppnode;//改变ppnodeif (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}}void RotateR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;Node* ppnode = parent->_parent;//改变parentparent->_left = curright;parent->_parent = cur;//改变currightif (curright != nullptr){curright->_parent = parent;}//改变curcur->_right = parent;cur->_parent = ppnode;//改变ppnodeif (ppnode == nullptr){_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}}

五、红黑树的验证

当我们写完一个比较复杂的程序的时候，我们最好去写一个辅助代码去验证它

1. 检查平衡

如下代码所示，可以去检测我们实现的红黑树当插入数据以后是否会出现不平衡的现象。检查利用的就是每条路径上黑色结点个数相同与不能出现连续的两个红色结点这两条规则。

	bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr){return true;}if (root->_color == RED){return false;}int benchmark = 0;Node* cur = root;while (cur){if (cur->_color == BLACK){benchmark++;}cur = cur->_left;}return CheckColor(root, 0, benchmark);}bool CheckColor(Node* root, int blacknum, int benchmark){//检查每条路径的黑色结点数量是否相等if (root == nullptr){if (blacknum != benchmark){return false;}return true;}if (root->_color == BLACK){blacknum++;}//检查颜色if (root->_color == RED && root->_parent && root->_parent->_color == RED){cout << root->_kv.first << ":" << "出现两个连续的红色结点" << endl;return false;}return CheckColor(root->_left, blacknum, benchmark) && CheckColor(root->_right, blacknum, benchmark);}

2. 计算高度与旋转次数

高度的代码很简单，如下所示

	int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr){return 0;}int leftheight = Height(root->_left);int rightheight = Height(root->_right);return leftheight > rightheight ? 1 + leftheight : 1 + rightheight;}

对于旋转次数，我们可以直接设置一个变量专门计数。每旋转一次这个值加一次

	int Getrotatecount(){return _rotatecount;}

3. 验证

int main()
{RBTree<int, int> rb;srand(time(0));for (int i = 0; i < 10000; i++){int tmp = rand();rb.Insert(make_pair(tmp, tmp));//rb.Insert(make_pair(i, i));//cout << rb.IsBalance() << endl;//cout << i << ":" << tmp << endl;}cout << "height:" << rb.Height() << endl;cout << "rotatecount:" << rb.Getrotatecount() << endl;cout << rb.IsBalance() << endl;return 0;
}

我们使用上面的随机数来进行测试

运行结果如下所示

六、 红黑树与AVL树的比较

红黑树和AVL树都是高效的平衡二叉树，增删改查的时间复杂度都是logN，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数,所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

从源代码中我们也可以看出来，其实map与set的底层都是红黑树，而且是kv结构的红黑树