红黑树（C++实现）

本篇博客讲解红黑树概念，性质，以及插入的原理，

1.红黑树的概念

红黑树是一种二叉搜索树，但在每个结点上增加了一个存储位用于表示结点的颜色，这个颜色可以是红色的，也可以是黑色的，因此我们称之为红黑树。AVL树的绝对平衡使得它的插入删除时旋转次数多，而红黑树不仅查找效率维持在一个log2N的水平，而且插入删除的消耗比AVL数小。

2.红黑树的性质

（1）根节点黑色

（2）不会出现连续的红色节点

（3）每个节点的颜色不是红色就是黑色

（4）每个节点到叶子节点的路径上，都包含相同数目的黑色节点

（5）会在每个数字节点后面，增加一个空的黑色节点

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

实现了一个相对的平衡。

3.红黑树的插入

我们以红黑树的插入为例，讲解一下红黑树的原理。我们这里直接实现KV模型的红黑树，为了方便后序的旋转操作，将红黑树的结点定义为三叉链结构，我们还还新加入了一个成员变量，用于表示结点的颜色。

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

红黑树插入结点的逻辑分为三步：

1. 按二叉搜索树的插入方法，（插入key大于树节点key，往右走）,并找到待插入位置。
2. 将待插入结点插入到树中。
3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。                                                   

若插入结点的父结点是黑色的，那么我们就不用对红黑树进行调整 ，如果我们插入节点的父亲为红色，则需要进入处理，这时记住，如何处理看叔叔节点。笔者都是画的手图。

情况一：如果叔叔存在且为红色，则我们将叔叔和父亲都变为黑色，祖父变成红色，然后继续向上递归即可处理，为什么如此变？首先我们新插入的节点如果由红色变为黑色，那么它在一个支路底端加入一个黑色节点，如果要保证所有路径的黑色节点的数目相同，此时需要改变其它所有路径，而祖父如果变成黑色，此时这两条路上所有黑色节点数目都会增加，如果祖父它还有父亲，那么祖父的兄弟节点以及子树也需要进行调整，所以红黑树路径里面不要轻易增加黑色节点。

情况二：如果叔叔存在且为黑色，这种情况下一定是由情况1向上更新时造成，此时已经出现了红黑色的高度不平衡，我们需要进行旋转处理，在AVL树的旋转中，我们对旋转进过详细讲解，如根据左边高左边高右单旋进行右单旋等，旋转之后需要对节点进行重新着色。

情况二：如果叔叔不存在，在这种情况下的cur结点一定是新插入的结点，而不可能是由情况一变化而来的，同情况二的处理。

//插入函数
pair<Node*, bool> Insert(const pair<K, V>& kv)
{if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点{_root = new Node(kv);_root->_col = BLACK; //根结点必须是黑色return make_pair(_root, true); //插入成功}//1、按二叉搜索树的插入方法，找到待插入位置Node* cur = _root;Node* parent = nullptr;while (cur){if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //待插入结点的key值等于当前结点的key值{return make_pair(cur, false); //插入失败}}//2、将待插入结点插入到树中cur = new Node(kv); //根据所给值构造一个结点Node* newnode = cur; //记录新插入的结点（便于后序返回）if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值{//插入到parent的左边parent->_left = cur;cur->_parent = parent;}else //新结点的key值大于parent的key值{//插入到parent的右边parent->_right = cur;cur->_parent = parent;}//3、若插入结点的父结点是红色的，则需要对红黑树进行调整while (parent&&parent->_col == RED){Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在if (parent == grandfather->_left) //parent是grandfather的左孩子{Node* uncle = grandfather->_right; //uncle是grandfather的右孩子if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整parent->_col = uncle->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateR(grandfather); //右单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}else //cur == parent->_right{RotateLR(grandfather); //左右双旋//颜色调整grandfather->_col = RED;cur->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}else //parent是grandfather的右孩子{Node* uncle = grandfather->_left; //uncle是grandfather的左孩子if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红{//颜色调整uncle->_col = parent->_col = BLACK;grandfather->_col = RED;//继续往上处理cur = grandfather;parent = cur->_parent;}else //情况2+情况3：uncle不存在 + uncle存在且为黑{if (cur == parent->_left){RotateRL(grandfather); //右左双旋//颜色调整cur->_col = BLACK;grandfather->_col = RED;}else //cur == parent->_right{RotateL(grandfather); //左单旋//颜色调整grandfather->_col = RED;parent->_col = BLACK;}break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理}}}_root->_col = BLACK; //根结点的颜色为黑色（可能被情况一变成了红色，需要变回黑色）return make_pair(newnode, true); //插入成功
}//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;//建立subRL与parent之间的联系parent->_right = subRL;if (subRL)subRL->_parent = parent;//建立parent与subR之间的联系subR->_left = parent;parent->_parent = subR;//建立subR与parentParent之间的联系if (parentParent == nullptr){_root = subR;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}
}//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;Node* parentParent = parent->_parent;//建立subLR与parent之间的联系parent->_left = subLR;if (subLR)subLR->_parent = parent;//建立parent与subL之间的联系subL->_right = parent;parent->_parent = subL;//建立subL与parentParent之间的联系if (parentParent == nullptr){_root = subL;_root->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}
}//左右双旋
void RotateLR(Node* parent)
{RotateL(parent->_left);RotateR(parent);
}//右左双旋
void RotateRL(Node* parent)
{RotateR(parent->_right);RotateL(parent);
}

4.红黑树的检测

红黑树的检测分为两步：

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

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

//判断是否为红黑树
bool ISRBTree()
{if (_root == nullptr) //空树是红黑树{return true;}if (_root->_col == RED){cout << "error：根结点为红色" << endl;return false;}//找最左路径作为黑色结点数目的参考值Node* cur = _root;int BlackCount = 0;while (cur){if (cur->_col == BLACK)BlackCount++;cur = cur->_left;}int count = 0;return _ISRBTree(_root, count, BlackCount);
}
//判断是否为红黑树的子函数
bool _ISRBTree(Node* root, int count, int BlackCount)
{if (root == nullptr) //该路径已经走完了{if (count != BlackCount){cout << "error：黑色结点的数目不相等" << endl;return false;}return true;}if (root->_col == RED&&root->_parent->_col == RED){cout << "error：存在连续的红色结点" << endl;return false;}if (root->_col == BLACK){count++;}return _ISRBTree(root->_left, count, BlackCount) && _ISRBTree(root->_right, count, BlackCount);
}