【c++】【数据结构】红黑树

红黑树的定义

红黑树是一种自平衡的二叉搜索树，通过特定的规则维持树的平衡。红黑树在每个结点上都增加一个存储位表示结点的颜色，结点的颜色可以是红色或者黑色，然后做出一下规定：

1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的，则它的两个孩子结点是黑色的
4. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

通过这五条规则的限制，红黑树就可以保证树中没有一条路径会比其他路径的两倍还长，红黑树将这种状态视为为平衡。为什么通过这几条规则就能做到呢？其重点在于规则4，即对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点，这样的话不难想到，最短路径的情况就是一条路径上面全是黑色结点；而通过规则3我们可以知道，一条路径上的红节点是不能连续存在的，又因为规则4的限制，我们要想让一条路径尽可能地长就只有往黑节点的间隙插入红节点，但是红节点不能连续，所以就是一个黑节点接一个红结点。最短路径是全黑，最长路径是一个黑接一个红，不难想象，最长路径不会超过最短路径的两倍，最多也就是两倍。

红黑树的部分模拟实现

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;enum Color
{red,black
};template<class Key, class Value>
struct RB_Node
{typedef RB_Node<Key, Value> Node;RB_Node(Key k, Value v, Color c) :_key(k),_value(v),_color(c){}Node* _parent = nullptr;Node* _left = nullptr;Node* _right = nullptr;Key _key = 0;Value _value = 0;Color _color = red;
};template<class Key, class Value>
class RB_Tree
{
public:int rotation_num = 0;typedef RB_Node<Key, Value> Node;bool insert(Key k, Value v){if (!_root){_root = new Node(k, v, black);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == k) return false;parent = cur;if (cur->_key > k) cur = cur->_left;else cur = cur->_right;}cur = new Node(k, v, red);if (parent->_key > cur->_key){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (parent->_color == black) break;Node* pparent = parent->_parent;Node* uncle = nullptr;if (pparent->_key > parent->_key) uncle = pparent->_right;else uncle = pparent->_left;if (!uncle || uncle->_color == black){if (pparent->_key > parent->_key){if (parent->_key > cur->_key){Rrotation(parent);parent->_color = black;pparent->_color = red;}else{LRrotation(parent);cur->_color = black;pparent->_color = red;}}else{if (parent->_key < cur->_key){Lrotation(parent);parent->_color = black;pparent->_color = red;}else{RLrotation(parent);cur->_color = black;pparent->_color = red;}}if (parent == _root) parent->_color = black;break;}else if (uncle->_color == red){uncle->_color = parent->_color = black;pparent->_color = red;if (pparent == _root){pparent->_color = black;break;}cur = pparent;parent = pparent->_parent;}}return true;}//void inorder()//中序打印//{//	_inorder(root);//}//int high()//树的高度//{//	return _high(root);//}//void check()//检查结点平衡//{//	_check(root);//}bool CheckColour(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->_key << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_color != black){return false;}// 基准值int benchmark = 0;Node* cur = _root;while (cur){if (cur->_color == black)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);}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 ? leftHeight + 1 : rightHeight + 1;}private://int _check(Node* cur)//{//	if (!cur) return 0;//	int lret = _check(cur->_left);//	int rret = _check(cur->_right);//	if (lret != rret) cout << cur->_key << " : 错误" << endl;//	if (cur->_color == black) return lret + 1;//	return lret;//}//int _high(Node* cur)//{//	if (!cur) return 0;//	int releft = _high(cur->_left);//	int reright = _high(cur->_right);//	return releft > reright ? releft + 1 : reright + 1;//}//void _inorder(Node* cur)//{//	if (!cur) return;//	_inorder(cur->_left);//	cout << cur->_key << endl;//	_inorder(cur->_right);//}void LRrotation(Node* cur){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);}void RLrotation(Node* cur){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);}void Lrotation(Node* cur){rotation_num++;Node* parent = cur->_parent;Node* pparent = parent->_parent;Node* cur_left = cur->_left;parent->_right = cur_left; //左右节点更新cur->_left = parent;if (cur_left) cur_left->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{_root = cur;cur->_parent = nullptr; //解耦}//cur->_color = black; //颜色更新//parent->_color = red;}void Rrotation(Node* cur){rotation_num++;Node* parent = cur->_parent;Node* pparent = parent->_parent;//Node* son = cur->_left;Node* cur_right = cur->_right;parent->_left = cur_right; //左右节点更新cur->_right = parent;if (cur_right) cur_right->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{_root = cur;cur->_parent = nullptr; //解耦}//cur->_color = black; //颜色更新//parent->_color = red;}Node* _root = nullptr;
};

对于红黑树来说，其最核心的无疑就是插入和删除函数，这里笔者能力有限，只实现了插入函数。

首先搞个枚举定义红跟黑两种状态，在结点中引入颜色变量，颜色默认为红色。因为要维持对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点 ，所以黑色节点是不会轻易添加的，默认就是添加红结点。

颜色的向上更新

插入函数的插入逻辑的实现与普通二叉搜索树无异，这里不过多赘述，这里重点讲讲颜色的更新方式。首先我们看向下面这张图，


我们在插入红结点时，会遇到这两种情况，一种是父结点为红色，一种是父结点为黑色。当父结点为黑色时，红节点的插入不会破坏任何规则，当父结点为红色时，红结点的插入会破坏如果一个节点是红色的，则它的两个孩子结点是黑色的规则，这时我们应该怎么办呢？把父结点或者子结点的颜色变成黑色吗？不行，因为要维持对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点的规则，擅自增加黑结点会破坏这种规则，那应该怎么办呢？我们看向下面这张图，

方块就是结点连接的子树，这样这张图就能代表更为普遍的情况。可以看到，当出现连续红结点冲突时，我们应该将父结点与叔叔结点一起变成黑色，再将爷爷结点变成红色，之后我们应该看向爷爷结点的父结点，如果又出现了连续红结点，就应该继续这个过程，向上更新颜色。

上面讲的这种情况是在叔叔结点为红的情况下的做法，但是叔叔结点也可能为黑或者直接不存在，这时就没法直接用变色的套路了。AVL树中我们遇到平衡因子为2或-2时，就表示树不平衡了，需要使用旋转函数，这里也是如此，当父结点为红而叔叔结点为黑或不存在时，就表明父结点所在的子树的高度大于叔叔结点所在子树的高度，因为父结点所在的子树红节点更多，而且由于是一路向上变色而来的，父结点所在的子树就是一红一黑这种最长的排法，所以可以认为此时的红黑树已经是一种不平衡的状态了，以至于无法正常向上变色了，这时我们采取和AVL树一样的做法，那就是动用旋转算法。

旋转算法

单旋算法

红黑树的旋转算法与AVL树的一模一样，但是AVL需要在旋转后改变平衡因子，而红黑树则需要改变结点的颜色，更新策略如下，

这是叔叔结点为黑的情况，如果叔叔节点不存在，根据红黑树的性质，则一定是下面这个样子，

son一定是新插入的结点，这种情况可以与叔叔节点为黑的情况一起处理，都是通用的。当然我这里举例的都是左子树高的情况，把我画的图镜像过来就是右子树高的情况。对于左子树高的情况我们用右旋，右子树高的情况我们用左旋，与AVL树一致，旋转的思路我在介绍AVL树的文章中写过了，这里不过多赘述，直接上代码，

	void Lrotation(Node* cur) //左单旋{rotation_num++;Node* parent = cur->_parent;Node* pparent = parent->_parent;Node* cur_left = cur->_left;parent->_right = cur_left; //左右节点更新cur->_left = parent;if (cur_left) cur_left->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{_root = cur; //更新根结点cur->_parent = nullptr; //解耦}//cur->_color = black; //颜色更新//parent->_color = red;}void Rrotation(Node* cur) //右单旋{rotation_num++;Node* parent = cur->_parent;Node* pparent = parent->_parent;//Node* son = cur->_left;Node* cur_right = cur->_right;parent->_left = cur_right; //左右节点更新cur->_right = parent;if (cur_right) cur_right->_parent = parent; //父节点的更新parent->_parent = cur;cur->_parent = pparent;if (pparent) //判断是不是空{if (pparent->_key > cur->_key) pparent->_left = cur; //父节点的父节点更新else pparent->_right = cur;}else{_root = cur;cur->_parent = nullptr; //解耦}//cur->_color = black; //颜色更新//parent->_color = red;}

双旋算法

AVL树中出现折线形时使用单旋函数就不管用了，对于红黑树也是一样，

使用单旋同样就不管用了，

需要使用双旋来解决问题，

双旋算法的思路与AVL也是一致的，这里不过多赘述，双旋完之后注意变色就行，这里因为son结点变成了黑色，所以同样不需要再向上变色了。

	void LRrotation(Node* cur){Lrotation(cur->_right);cur = cur->_parent;Rrotation(cur);}void RLrotation(Node* cur){Rrotation(cur->_left);cur = cur->_parent;Lrotation(cur);}

这样insert函数就完成了，

bool insert(Key k, Value v)
{if (!_root){_root = new Node(k, v, black);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (cur->_key == k) return false;parent = cur;if (cur->_key > k) cur = cur->_left;else cur = cur->_right;}cur = new Node(k, v, red);if (parent->_key > cur->_key){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (parent->_color == black) break;Node* pparent = parent->_parent;Node* uncle = nullptr;if (pparent->_key > parent->_key) uncle = pparent->_right;else uncle = pparent->_left;if (!uncle || uncle->_color == black){if (pparent->_key > parent->_key){if (parent->_key > cur->_key){Rrotation(parent);parent->_color = black;pparent->_color = red;}else{LRrotation(parent);cur->_color = black;pparent->_color = red;}}else{if (parent->_key < cur->_key){Lrotation(parent);parent->_color = black;pparent->_color = red;}else{RLrotation(parent);cur->_color = black;pparent->_color = red;}}if (parent == _root) parent->_color = black;break;}else if (uncle->_color == red){uncle->_color = parent->_color = black;pparent->_color = red;if (pparent == _root){pparent->_color = black;break;}cur = pparent;parent = pparent->_parent;}}return true;
}

除了插入函数之外，我还写了一些其他的函数来测试插入函数的正确与否，大家可以用作参考，实现思路较为简单，不做过多赘述。

红黑树与AVL树的对比

红黑树与AVL树都属于自平衡的二叉搜索树，两者都有自己的一套维护手段，但对于平衡的维护方面，红黑树允许最长路径达到最短路径的两倍，而AVL只允许两子树的高度差最多为1，所以AVL毫无疑问在维护平衡方面是比红黑树严格得多的，所以我们可以预见在相同一组随机数据（得足够多，太少可能看不出差异）插入后AVL树一定排的比红黑要满，AVL树的高度也一定比红黑树要低，所以AVL树在插入后的查找效率是比红黑略高的，但是，我们应该明白为了这点查找效率AVL树付出了多少代价，我这里写了一组测试函数，用我写的红黑与AVL放进来测试，我在AVL和红黑中都放了有个记录旋转次数的变量，每调用一次旋转函数，就++这个变量，又写了一个函数递归计算树的高度，

void test()
{RB_Tree<int, int> x;AVL_Tree<int, int> y;for (int i = 0; i < 10000000; ++i){int tmp = rand() % 10000000 + i;x.insert(tmp, 0);y.insert(tmp, 0);}cout << "RB : " << "旋转次数 : " << x.rotation_num << " 高度 : " << x.Height() << endl;cout << "AVL : " << "旋转次数 : " << y.rotation_num << " 高度 : " << y.high() << endl;
}int main()
{srand(time(NULL));test();return 0;
}

我这里用了一组十分可观的数据量，跑出来的结果是，

我们可以看到红黑树的高度比AVL大了7，但是红黑树比AVL少旋转了约74万次，计算机多查找7层眨眼间的工夫就能完成，但多旋转74万次计算机可就要跑好一会了。所以我们可以明白，除非需要极其频繁的查找或需要极致的查找效率，不然AVL为了那点查找效率所付出的代价是得不偿失的。事实上，在实际运用中，红黑的实用性也是远远大于AVL，c++中set和map的底层用的就是红黑而不是AVL，java中的TreeMap也是如此。