红黑树简单模拟实现

我们前面实现了 二叉搜索树和 AVL树。
其中AVL树是二叉搜索树的改进，但是有些人觉得二叉树搜索的插入调整太频繁了，或者说平衡条件过于苛刻。
于是人们放松了左右子树高度差的限制，只需要确保没有一条路径会比其他路劲长出两倍，这就是所谓的红黑树。

定义

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

红黑树满足的性质：

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

满足这上面五个条件就确保了最长路径不会超过最短路径两倍。接下来我解释一下这是为什么。

首先看到34两点。满足了这两点之后，我们的理论最短路径就是全黑结点。
那最长路径呢？
因为要满足第四条，所以只能在全黑结点路径上插入红色结点来增长路径，又因为红色结点不能连续，因此最多插入等量的红色结点。这就确保了最长路径不会超过最短路径的两倍。

那为什么根节点要是黑色结点呢？
假如根节点是红色结点，那么他只能插入黑色结点，这就导致了左右子树的黑色结点数量不同。因此根节点只能是黑色的。

成员变量

enum Color
{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;Color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};
template<class K, class V>
class RBTree
{typedef RBTreeNode<K,V> Node;
public:private:Node* _root = nullptr;
};

旋转

在前文AVL树中我们实现了左单旋和右单旋，那么这两种旋转能不能合并成一个函数呢？
注意到左单旋：

右单旋：

左单旋是将parent右子subR的左子树subRL接到parent的右边。
右单旋是将parent左子subL的右子树subLR接到parent的左边。

如此对称的行为理应可以合并：

void Rotate(Node* child)
{Node* parent = child->_parent;Node** childson[] = {  &(child->_right),&(child->_left) };Node** parentson[] = { &(parent->_left),&(parent->_right) };bool IsRight = (child == parent->_right);*(parentson[IsRight]) = *(childson[IsRight]);if (*(childson[IsRight]))(*(childson[IsRight]))->_parent = parent;*(childson[IsRight]) = parent;child->_parent = parent->_parent;parent->_parent = child;if (parent == _root){_root = child;child->_parent = nullptr;}else {//Node* grandparent = parent->_parent; 千错万错Node* grandparent = child->_parent;if (parent == grandparent->_left) grandparent->_left = child;else grandparent->_right = child;}}

这时候如果要左单旋，就传入旋转点的右孩子，如果要右单旋就传入旋转点的左孩子。

insert

对于插入一个结点，那么是默认他为红色还是黑色呢？
如果默认是黑色就会违反所有路径黑色结点数相同这一个规定，如果默认是红色就有可能违反红色结点不连续这一规定。
显然插入红色结点的冲突比较好处理，因此我们默认插入的结点为红色结点。那么就分三种情况：

1. 插入的结点是根节点，那只需要让根节点变黑即可
2. 插入的结点的父结点是黑色结点，那么不违反规则，不做处理
3. 插入的结点的父结点是红色结点，需要处理。

对于第三种情况，又要分两种情况进行讨论：

1. 叔叔结点存在且为红色：

如上，10结点为插入结点。
首先是很容易想到的，为了维持到10结点这一路径的黑色结点个数不变，我们需要将20结点变黑同时将30结点变红，如果仅仅是将20结点变黑，那么到10结点这一路径的黑色结点数就会+1，违反规定4.
那么在30结点变红之后，到40结点这一路径的黑色节点数是不是就少了一个？所以我们要将40结点变黑。如下处理：

那么30结点有没有可能和他的父结点冲突呢？答案是有可能的，所以我们还需要将30结点看作插入结点继续循环处理。

2. 那么再看到另一种情况，也就是叔叔结点不存在或者为黑色

实际上这种情况又详细分为四种，我们先看第一种插入结点为左子结点，叔叔结点为右子结点或者不存在：

由图可知，先将父亲变黑，爷爷变红然后进行右单旋调整

第二种插入结点为右子结点，叔叔结点为左子结点或者不存在，根据对称性可知，先将父亲变黑，爷爷变红然后进行左单旋调整

第三种插入结点为右子结点，叔叔结点为右子结点或者不存在

可以看到对父亲结点进行左单旋就转换成了第一种情况，这时按第一种情况除了

第四种插入结点为左子结点，叔叔结点为左子结点或者不存在

以234树的角度来待插入操作

我们可以将红黑树看作一棵二三四树，其中黑色结点为2结点，黑色结点加红色结点为3结点，黑色结点和两个红色结点为4结点。
例如：

这时我们插入一个16：

这就对应了父结点时黑色结点，不用处理

如果插入一个3：

这时候对应叔叔结点存在且为红。
那么5结点上溢，叔父变黑，爷爷变红，继续向上处理。

如果插入一个17：

本质上就是父亲做了爷爷，又因为父亲是右子结点，实际上就是进行左单旋。对应插入结点为右子结点，叔叔结点为左子结点或者不存在。

我们再看到如果插入25.5：

实际上是儿子做了爷爷，首先儿子要当爹，又因为儿子是左子结点，因此右单旋。然后儿子就是爷爷的右子结点了，再左单旋就成了爷爷。最后变色处理。
对应插入结点为左子结点，叔叔结点为左子结点或者不存在。

其余情况也是类似讨论，这里不多做赘述。

具体代码

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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//父亲颜色是黑色结束while (parent&&parent->_col == RED){//是否一定有爷爷？肯定的，因为父亲结点是红色，因此不是根节点。Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或者为黑{if (cur == parent->_left){//RotateR(grandfather);Rotate(grandfather->_left);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateL(parent);//RotateR(grandfather);Rotate(parent->_right);Rotate(grandfather->_left);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;//未必有parentparent = cur->_parent;}else//叔叔不存在或为黑{if (cur == parent->_right){//RotateL(grandfather);Rotate(grandfather->_right);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//处理边界情况_root->_col = BLACK;return true;
}

完整代码

完整代码包括InOrder和IsBalance

enum Color
{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;Color _col;RBTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};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);_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->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//父亲颜色是黑色结束while (parent&&parent->_col == RED){//是否一定有爷爷？肯定的，因为父亲结点是红色，因此不是根节点。Node* grandfather = parent->_parent;if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续处理cur = grandfather;//未必有parentparent = cur->_parent;}else//叔叔不存在或者为黑{if (cur == parent->_left){//RotateR(grandfather);Rotate(grandfather->_left);parent->_col = BLACK;grandfather->_col = RED;}else{//RotateL(parent);//RotateR(grandfather);Rotate(parent->_right);Rotate(grandfather->_left);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;//未必有parentparent = cur->_parent;}else//叔叔不存在或为黑{if (cur == parent->_right){//RotateL(grandfather);Rotate(grandfather->_right);parent->_col = BLACK;grandfather->_col = RED;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//处理边界情况_root->_col = BLACK;return true;}void Rotate(Node* child){Node* parent = child->_parent;Node** childson[] = {  &(child->_right),&(child->_left) };Node** parentson[] = { &(parent->_left),&(parent->_right) };bool IsRight = (child == parent->_right);*(parentson[IsRight]) = *(childson[IsRight]);if (*(childson[IsRight]))(*(childson[IsRight]))->_parent = parent;*(childson[IsRight]) = parent;child->_parent = parent->_parent;parent->_parent = child;if (parent == _root){_root = child;child->_parent = nullptr;}else {//Node* grandparent = parent->_parent; 千错万错Node* grandparent = child->_parent;if (parent == grandparent->_left) grandparent->_left = child;else grandparent->_right = child;}}//void RotateR(Node* parent)//{//	Node* subL = parent->_left;//	Node* subLR = subL->_right;//	parent->_left = subLR;//	if (subLR)//		subLR->_parent = parent;//	subL->_right = parent;//	Node* ppNode = parent->_parent;//	parent->_parent = subL;//	if (parent == _root)//	{//		_root = subL;//		_root->_parent = nullptr;//	}//	else//	{//		if (ppNode->_left == parent)//		{//			ppNode->_left = subL;//		}//		else//		{//			ppNode->_right = subL;//		}//		subL->_parent = ppNode;//	}//}//void RotateL(Node* parent)//{//	Node* subR = parent->_right;//	Node* subRL = subR->_left;//	parent->_right = subRL;//	if (subRL)//		subRL->_parent = parent;//	subR->_left = parent;//	Node* ppNode = parent->_parent;//	parent->_parent = subR;//	if (parent == _root)//	{//		_root = subR;//		_root->_parent = nullptr;//	}//	else//	{//		if (ppNode->_right == parent)//		{//			ppNode->_right = subR;//		}//		else//		{//			ppNode->_left = subR;//		}//		subR->_parent = ppNode;//	}//}bool IsBalance(){if (_root->_col == RED){return false;}int refNum = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)refNum++;cur = cur->_left;}return Check(_root,0, refNum);}void InOrder(){_InOrder(_root);cout << endl;}private:bool Check(Node* root,int blackNum,const int refNum){if (root == nullptr){if (blackNum != refNum){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, refNum) && Check(root->_right, blackNum, refNum);}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}Node* _root = nullptr;//size_t _size;
};