C++:平衡二叉搜索树之红黑树

一、红黑树的概念

红黑树，和AVL都是二叉搜索树，红黑树通过在每个节点上增加一个储存位表示节点的颜色，可以是RED或者BLACK，通过任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树能够确保没有一条路径会比其他路径长出两倍，因此红黑树是接近平衡的。

与AVL树相比，红黑树的插入和删除操作更具优势，因为红黑树是接近平衡的，AVL树是绝对平衡的，因此插入删除等操作时，红黑树需要旋转的次数是比AVL树少的。

二、红黑树的性质

每个节点不是红色就是黑色
根节点是黑色的
如果一个节点是红色的，则它的两个孩子节点是黑色的
一条路径上没有连续的红色节点，每条路径上黑色节点的数量是相同的

下面就是一个红黑树的示例：

根据红黑树的性质我们知道：一个红黑树中，最短路径 * 2 >= 最长路径

理论上：最短路径：全黑最长路径：一黑一红交替

三、红黑树节点的定义

下面是红黑树节点的定义代码：

//节点的颜色定义
enum Colour
{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;//节点的双亲节点Colour _col;//节点的颜色//节点的构造函数RBTreeNode(const pair<K, V>& kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr){}
};

四、红黑树的插入

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

1、按照二叉搜索树的性质插入新节点

2、检测新节点插入后，红黑树的性质是否遭到破坏

新节点的默认颜色是红色，因此，如果双亲节点是黑色就没有违反任何红黑树的性质，不需要调整，但是如果新插入节点的双亲节点是红色时，就违反了不能有相连的红色节点的规则，此时需要对红黑树进行分情况讨论：

cur为当前节点， p为父节点， g为祖父节点， u为叔父节点

4.1情况一：cur 为红， p为红， g为黑， u存在且为黑

注意：这里的树，可能是一棵完整的树，也可能是一个子树

此时abcde子树都为空

这个时候我们只需要进行变色处理，将p 和 u节点变为黑色，将g改为红色

调整完以后，如果g是根节点，需要将g改为黑色，因为红黑树的性质规定根节点的颜色必须是黑色。

如果g是子树，并且g的双亲节点是红色的话就需要继续向上调整，如下图所示：

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

这里说明u的情况有两种：

1.u不存在，此时cur一定是新增节点，如果cur不是新增节点的话，那么cur和p一定有一个节点的颜色是黑色，但是那样就不满足每条路径黑色节点的数目相同这一性质。

p是g的左子节点， cur是p的左子节点，那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点，那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋，再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋；

再进行右单旋：

p是g的右子节点， cur是p的左子节点，先对p进行右单旋，再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

2.u存在且为黑，那么cur节点原来的颜色一定是黑色，现在是红色的原因就是因为cur的子树在调整的过程中将cur的颜色更新成了红色。

p是g的左子节点， cur是p的左子节点，那么就对g进行右单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的右子节点， cur是p的右子节点，那么就对g进行左单旋：

变色处理：p, g变色 – p变黑色， g变红色

p是g的左子节点， cur是p的右子节点，先对p进行左单旋，再对g做右单旋：

变色处理：cur, g变色 – cur变黑色， g变红色

先进行左单旋：

再进行右单旋：

p是g的右子节点， cur是p的左子节点，先对p进行右单旋，再对g进行左单旋：

变色处理：cur， g变色 – cur变黑色， g变红色

先进行右单旋：

再进行左单旋：

左单旋代码实现：

//左单旋void RotateL(Node* parent){Node* SubR = parent->_right;Node* SubRL = SubR->_left;parent->_right = SubRL;if (SubRL){SubRL->_parent = parent;}Node* parentP = parent->_parent;SubR->_left = parent;parent->_parent = SubR;if (parentP == nullptr){_root = SubR;SubR->_parent = nullptr;}else{if (parentP->_left == parent){parentP->_left = SubR;SubR->_parent = parentP;}else{parentP->_right = SubR;SubR->_parent = parentP;}}}

右单旋代码实现：

//右单旋void RotateR(Node* parent){Node* SubL = parent->_left;Node* SubLR = SubL->_right;parent->_left = SubLR;if (SubLR)SubLR->_parent = parent;Node* parentP = parent->_parent;SubL->_right = parent;parent->_parent = SubL;if (parentP == nullptr){_root = SubL;SubL->_parent = nullptr;}else{if (parentP->_left == parent){parentP->_left = SubL;SubL->_parent = parentP;}else{parentP->_right = SubL;SubL->_parent = parentP;}}}

插入函数整体代码实现：

bool Insert(const pair<K, V>& kv){if (_root == nullptr){//如果是个空树就将新节点作为根节点_root = new Node(kv);_root->_col = 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);cur->_col = RED;if (parent->_kv.first > kv.first){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;//处理while (parent && parent->_col == RED){Node* grandfather = parent->_parent;// g//p  u结构if (parent == grandfather->_left){Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED){//变色处理parent->_col = uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else//uncle不存在或者存在且为黑-》旋转加变色{if (cur == parent->_left){//cur为parent的左子结点时进行右旋RotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋RotateL(parent);RotateR(grandfather);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;parent = cur->_parent;}else{if (cur == parent->_right){//cur为父亲的右子节点时对g进行左单旋RotateL(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//双旋 -》 右左双旋RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;return true;}

五、红黑树相关接口的实现

查找函数的实现：

依旧是根据二叉搜索树的查找规则：

//查找函数Node* Find(const K& key){if (_root == nullptr)return nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}elsereturn cur;}return nullptr;}

容量高度相关：

返回有效节点个数：

//有效节点个数int Size(){_Size(_root);}int _Size(Node* root){return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;}

二叉树高度：

//平衡二叉树高度int Height(){_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;}

中序遍历：

//中序遍历void Inorder(){_inorder(_root);cout << endl;}void _inorder(Node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_inorder(root->_right);}

六、红黑树的验证

我们要通过代码来验证我们所实现的红黑树是否是符合红黑树的性质的。

红黑树的验证分为以下两步：

验证其是否满足二叉搜索树也就是中序遍历是否有序
验证其是否满足红黑树的性质

验证代码：

1、验证是否为二叉搜索树：

//中序遍历void Inorder(){_inorder(_root);cout << endl;}void _inorder(Node* root){if (root == nullptr){return;}_inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_inorder(root->_right);}

2、验证是否满足红黑树的性质：

//判断是否为红黑树bool IsBalance(){if (_root == nullptr)return true;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);}bool Check(Node* root, int blackNum, const int refNum){if (root == nullptr){//cout << blackNum << endl;if (refNum != blackNum){cout << "存在黑色节点的数量不相等的路径" << endl;return false;}return true;}if (root->_col == RED && root->_parent->_col == RED){cout << root->_kv.first << "存在连续的红色节点" << endl;return false;}if (root->_col == BLACK){blackNum++;}return Check(root->_left, blackNum, refNum)&& Check(root->_right, blackNum, refNum);}