C++模拟实现红黑树

目录

介绍----什么是红黑树

 甲鱼的臀部----规定

分析思考

绘图解析+代码实现

节点部分

插入部分+分步解析

●父亲在祖父的左，叔叔在祖父的右：

●父亲在祖父的右，叔叔在祖父的左：

测试部分

整体代码

---

介绍----什么是红黑树

红黑树基于二叉搜索树，它和AVL树一样避免了二叉搜索树中极端场景单边树的情况，保证了检索的效率。红黑树允许最长路径是最短路径的二倍，相较于AVL树而言是近似于平衡的状态，但是减少了旋转的次数。

 甲鱼的臀部----规定

●每个节点都有颜色，不是红色就是黑色。

●根节点一定是黑色的。

●不能连续出现两个红色的节点。

●每条路径上的黑色节点数量相同。

●每个空节点都是黑色的。

●最多允许一条路径上的节点是另一条路径上节点的二倍。

分析思考

节点默认颜色应该选红色还是黑色，为什么？

答：插入红色可能会出现连续的红色节点，插入黑色会改变当前路径上的黑色节点数。选择默认插入节点为红色的原因是插入后的影响会小一些，当父节点是黑色时不用调整。相反的，黑色节点的插入一定会违反红黑树的规则。

满足上述特性为什么能保证最长路径不会超过最短路径的2倍？

答：这里要关注红黑树的两个特性，红色节点的孩子节点一定是黑色，每条路径的黑色节点树相同。也就说最长路径是红色节点和黑色交替，最短路径是全黑节点。这样一来，最长路径和最短路径间的差距就控制在了规定范围内。

绘图解析+代码实现

节点部分

三叉链结构分别指向左右孩子和父亲节点，数据方面存储键值对，除此之外还需要一个记录节点颜色的变量。

enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Color _color;RBTreeNode(pair<K, V> kv, Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};

插入部分+分步解析

红黑树是二叉搜索树，插入节点的规则和二叉搜索的特点一样：

   typedef RBTreeNode<K,V> Node;bool inster(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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->_color = RED;if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//节点插入后，需要检查红黑树的特性有没有被破坏掉//......}

上述我们谈论过新节点的颜色默认为红色的原因，那么接下来的插入如果新节点插入后其父节点的颜色是黑色，那么直接插入即可。如果其父节点的颜色为红色，那么就出现了两个红色节点出现的情况，此时就需要进行调整：

 

关注：红黑树的处理方法重点关注这样的几个节点：cur(新增节点)、parent(父亲节点)、uncle(叔叔节点)、grandfather（祖父节点）。

当节点的插入违反了红黑树“龟腚”时，对应不同的情况分别处理：

●父亲在祖父的左，叔叔在祖父的右：

情况1：cur为红，parent红色，叔叔节点存在且是红色，祖父是黑色；

 

如上图所示，情况1的处理方法就是将父亲和叔叔的节点变为黑色，祖父的节点变为红色。对于祖父为什么要变红是基于这样的考虑，我们当前的处理很可能只是在子树当中，如果祖父节点保持黑色不变，对于子树这两条路径而言，增加了黑色节点，这样一来就“拆东墙补了西墙”，又违反了另一条规则。如果祖父节点是根节点，改为红色当然是不合理的，我们在最后做下强制处理即可。

注意：这种情况可能是局部的处理，当祖父节点变红且不是根节点时，可能会破坏规则，所以针对情况1需要继续向上查找，也就是将祖父节点看成新增节点，祖父的父亲看做新增节点的父节点，继续向上更新检查树结构。

                if (uncle && uncle->_color == RED){//情况1，叔叔节点存在，且是红色的parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//更新cur和parent的位置cur = grandfater;parent = cur->_parent;}

情况2：cur为红（插入或者调整后和父亲祖父为一条直线），parent红色，叔叔不存在或者叔叔是黑色，祖父是红色。

当叔叔不存在时：这种情况较好分析，新节点插入后左边高，左边高度超过右边的2倍，进行一次右单旋，祖父变成红色，父亲变为黑色，这颗树调整完毕，不管它是不是子树都不会向上影响。

叔叔存在且为黑色，观察下图，每条路径上的黑色节点数量不相等，所以cur的位置应该是从黑色调整为的红色。

注意：这里不要受图示的影响，感觉uncle路径上的黑节点好像是多一个。调整前后的每条路径数量都是相等的，想象小三角中有着不同的结构就可以了。

叔叔的存在与否只是分析的过程不同，它们的代码处理方式是一样的： 

                    //在一条线上if (parent->_left == cur){//情况2，叔叔节点不存在或者存在是黑色的//右单旋RotaR(grandfater);parent->_color = BLACK;grandfater->_color = RED;}

 

情况3：cur为红（插入或者调整后和父亲祖父为线一条折），parent红色，叔叔不存在或者叔叔是黑色，祖父是红色。

uncle不存在：

 uncle存在:

                      if(cur == parent->_left){//情况3,叔叔节点存在是黑色的，在一条折线上RotaL(parent);RotaR(grandfater);cur->_color = BLACK;grandfater->_color = RED;}

●父亲在祖父的右，叔叔在祖父的左：

处理大思路和上述一致，只是叔叔和父亲交换了位置，不在画图分析，列举处理要点：
情况1：叔叔存在且为红色，叔叔和父亲变黑，祖父变红。向上继续查找。

                if (uncle && uncle->_color == RED){//情况1，叔叔存在且是红色parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//继续向上更新cur = grandfater;parent = cur->_parent;}

情况2：叔叔不存在或者存在为黑色，cur的位置和父亲祖父是一条直线，右边高，以祖父为轴点左单旋。祖父变红，父亲变黑。

                   //在右边插入if (parent->_right == cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent->_color = BLACK;//祖父的的颜色变成红色grandfater->_color = RED;}

情况3：叔叔不存在或者存在为黑色，cur的位置和父亲祖父是一条折线，先以父亲为轴右单旋，在以祖父为轴点左单旋，祖父变红，cur变黑。

                    if(cur == parent->_left)//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater->_color = RED;cur->_color = BLACK;}

测试部分

因为红黑树是二叉搜索树，在测试时很可能会有隐式的错误，比较难发现，所以需要下面的测试接口对红黑树的特性进行检查，检查是否有连续的红色节点出现，每条路径上的黑色节点是否相等。

bool check(Node* root,int num,int BLACKNUM){if (root == nullptr){if (num != BLACKNUM){cout << "某条路径上的黑色节点和其他路径不相等" << endl;return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "连续出现两个红色节点" << endl;return false;}if (root->_color == BLACK){num++;}return check(root->_left, num, BLACKNUM)&&check(root->_right, num, BLACKNUM);}bool IsBalance(){if (_root == nullptr){return false;}//根节点的颜色一定要是黑色if (_root->_color != BLACK){return false;}Node* ret = _root;int _blacknum = 0;while (ret){if (ret->_color == BLACK){_blacknum++;}ret = ret->_left;}return check(_root,0,_blacknum);}

整体代码

#include <time.h>
enum Color
{RED,BLACK
};template<class K,class V>
struct RBTreeNode
{RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;pair<K, V> _kv;Color _color;RBTreeNode(pair<K, V> kv, Color color = RED):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_color(color){}
};template <class K,class V>
class RBTee
{
public:typedef RBTreeNode<K,V> Node;bool inster(const pair<K, V>& kv){if (_root == nullptr){_root = new Node(kv);_root->_color = BLACK;return true;}Node* parent = nullptr;Node* cur = _root;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->_color = RED;if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}//插入的节点默认是红色的while (parent && parent->_color == RED){Node* grandfater = parent->_parent;if (parent == grandfater->_left){Node* uncle = grandfater->_right;if (uncle && uncle->_color == RED){//情况1，叔叔节点存在，且是红色的parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//更新cur和parent的位置cur = grandfater;parent = cur->_parent;}else {//左边新增if (parent->_left == cur){//情况2，叔叔节点存在是黑色的，在一条线上//右单旋RotaR(grandfater);parent->_color = BLACK;grandfater->_color = RED;}//右边新增else{//情况3,叔叔节点存在是黑色的，在一条折线上RotaL(parent);RotaR(grandfater);cur->_color = BLACK;grandfater->_color = RED;}//树进行了旋转调整，已经平衡，跳出循环break;}}else //parent在grandfater的右边{Node* uncle = grandfater->_left;if (uncle && uncle->_color == RED){//情况1，叔叔存在且是黑色parent->_color = uncle->_color = BLACK;grandfater->_color = RED;//继续向上更新cur = grandfater;parent = cur->_parent;}else//uncle的颜色是黑色{//在右边插入if (parent->_right == cur){//进行一个左单旋RotaL(grandfater);//父亲的颜色变成黑色parent->_color = BLACK;//祖父的的颜色变成红色grandfater->_color = RED;}else//左边插入{//右单旋RotaR(parent);//左单旋RotaL(grandfater);//改变颜色grandfater->_color = RED;cur->_color = BLACK;}break;}}}_root->_color = BLACK;return true;}void Inorder(){_Inorder(_root);}bool check(Node* root,int num,int BLACKNUM){if (root == nullptr){if (num != BLACKNUM){cout << "某条路径上的黑色节点和其他路径不相等" << endl;return false;}return true;}if (root->_color == RED && root->_parent->_color == RED){cout << "连续出现两个红色节点" << endl;return false;}if (root->_color == BLACK){num++;}return check(root->_left, num, BLACKNUM)&&check(root->_right, num, BLACKNUM);}bool IsBalance(){if (_root == nullptr){return false;}//根节点的颜色一定要是黑色if (_root->_color != BLACK){return false;}Node* ret = _root;int _blacknum = 0;while (ret){if (ret->_color == BLACK){_blacknum++;}ret = ret->_left;}return check(_root,0,_blacknum);}
private:void _Inorder(Node* root){if (root == nullptr){return ;}_Inorder(root->_left);cout << root->_kv.first << ":" << root->_kv.first << endl;_Inorder(root->_right);}void RotaL(Node* pparent){Node* subR = pparent->_right;Node* subRL = subR->_left;pparent->_right = subRL;if (subRL){subRL->_parent = pparent;}Node* pNode = pparent->_parent;pparent->_parent = subR;subR->_left = pparent;if (pNode == nullptr){_root = subR;_root->_parent = nullptr;}else{if (pNode->_left == pparent){pNode->_left = subR;}else if (pNode->_right == pparent){pNode->_right = subR;}subR->_parent = pNode;}}void RotaR(Node* pparent){Node* subL = pparent->_left;Node* subLR = subL->_right;pparent->_left = subLR;if (subLR != nullptr){subLR->_parent = pparent;}Node* pNode = pparent->_parent;subL->_right = pparent;pparent->_parent = subL;if (pNode == nullptr){_root = subL;_root->_parent = nullptr;}else{if (pNode->_left == pparent){pNode->_left = subL;}else{pNode->_right = subL;}subL->_parent = pNode;}}private:Node* _root = nullptr;
};