C++详细实现红黑树流程详解 C++详细实现红黑树流程详解

红黑树的概念
红黑树的性质
红黑树的定义与树结构
插入
新增结点插入后维护红黑树性质的主逻辑
旋转
验证
红黑树与AVl树的比较
红黑树的应用

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

文章图片

概念总结：
红黑树是二叉搜索树的升级，结点里面存放的成员col标记当前结点的颜色，它的最长路径最多是最短路径的二倍，红黑树通过各个结点着色方式的限制接近平衡二叉树，但是不同于AVL的是AVL是一颗高度平衡的二叉树，红黑树只是接近平衡

红黑树的性质

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

红黑树性质总结：
1、红黑树结点的颜色只能是红色或者黑色
2、红黑树根节点必须是黑色
3、红黑树并没有连续的红色结点
4、红黑树中从根到叶子的每一条路径都包含相同的黑色结点
5、叶子是黑色，表示空的位置
最长路径和最短路径概念：
最短路径：从根结点到叶子结点每一条路径的结点颜色都是黑色的不包含红色
最长路径：红黑交替，黑色结点和红色结点的个数相等

文章图片

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
假设结点个数为N，那么最短路径就是logN，最长路径就是2 * logN，所有并不存在最长路径超过最短路径2倍的情况

红黑树的定义与树结构

//枚举红黑颜色enum colour { RED, BLACK,}; //定义红黑树结点结构templatestruct RBTreeNode { //构造 RBTreeNode(const pair& kv = {0,0}):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(BLACK) { } //定义三叉链 RBTreeNode* _left; //左孩子 RBTreeNode* _right; //右孩子 RBTreeNode* _parent; //父亲 pair _kv; //pair对象 //节点的颜色 colour _col; //定义枚举变量}; //定义红黑树templateclass RBTree {typedef RBTreeNode Node; public://构造RBTree() :_root(nullptr){} private:Node* _root; //定义树的根节点};

插入插入过程类似搜索树的插入，重要的是维护红黑树的性质

pair Insert(const pair& kv){ if (!_root) //空树处理 {_root = new Node(kv); _root->_col = BLACK; return { _root, true }; } //二叉搜索树的插入逻辑 Node* cur = _root, * parent = nullptr; 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 { cur, false }; //插入失败} } cur = new Node(kv); cur->_col = RED; //新增结点颜色默认设置为RED //判断插入结点是否在parent的左边或者右边 if (parent->_kv.first > kv.first)//左边 {parent->_left = cur; cur->_parent = parent; } else//右边 {parent->_right = cur; cur->_parent = parent; } /* 红黑树性质处理：如果这棵树一开始是符合红黑树的性质，但在新增结点之后，导致失去了红黑树的性质，这里需要控制结点的颜色和限制每条路径上黑色结点的个数，以上情况都要处理*/ while (parent && parent->_col == RED) //父亲存在且父亲为红色 {Node* grandfather = parent->_parent; //祖父//父亲出现在祖父的左边需要考虑的情况if(parent == grandfather ->left){//1、uncle存在，uncle为红色/*如果parent和uncle都存在并且都为红色这是情况一，需要将parent和uncle的颜色变成红色，祖父颜色变成黑色更新cur、parent、grandfather、uncle 继续向上调整*///2、uncle不存在/*这里考虑两种旋转情况，直线单旋转，折线双旋/*cur出现在parent的左边 ,右单旋转经过右单旋后，parent去做树的根,祖父做为右子树//调节结点颜色parent->_col = BLACK; grandfather->_col = RED; *//*cur出现在parent的右边，左右双旋经过双旋后，cur作为树的根，grandfather为右子树调节结点颜色cur->_col = BLACK; grandfather->_col = RED; */*/ }else//父亲出现在祖父的右边{Node* uncle = grandfather->_left; //叔叔在左子树 /*情况一：叔叔存在，且叔叔和父亲都是红色，那么就需要将父亲和叔叔结点的颜色变成黑色，再将祖父的颜色变成红色，继续向上调整，更新孩子、父亲、祖父、叔叔的位置*//*情况二：叔叔不存在/*1、新增结点出现在父亲的右边，直线情况，左单旋处理旋转完后parent去做父亲的根，grandfather做父亲的左子树//调节颜色，根为黑，左右孩子为红2、新增结点出现在父亲的左边，会出现折现的情况，引发双旋，旋转完后，cur变成根，parent和grandfaher去做cur的左右孩子//调节颜色,根结点为黑，左右孩子为红*/*/ } } //如果父亲不存在为了保证根结点是黑色的，这里一定得将根结点处理为黑色 _root->_col = BLACK; }

新增结点插入后维护红黑树性质的主逻辑

//1、父亲一定存在的情况，叔叔存在/不存在父亲叔叔结点颜色为红色while (parent && parent->_col == RED) //父亲存在且父亲为红色{ Node* grandfather = parent->_parent; //祖父 //如果父亲和叔叔结点颜色都是红色 if (parent == grandfather->_left) {Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED)//对应情况：uncle存在且为红{//处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整uncle->_col = parent->_col = BLACK; grandfather->_col = RED; //向上调整cur = grandfather; //调整孩子parent = cur->_parent; //调整父亲}else//uncle不存在，uncle存在且为黑{//直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转，//旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色if (parent->_left == cur) {RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; }else//parent->_right == cur { //折线情况(cur在parent的右边)：这里会引发双旋RotateL(parent); //以parent为旋转点进行左单旋RotateR(grandfather); //以grandfather为旋转点进行右单旋转//旋转完后cur会去做树的根，那么设置为黑色，//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红cur->_col = BLACK; grandfather->_col = RED; //黑色结点个数相同}} } else //父亲在右子树 {Node* uncle = grandfather->_left; //叔叔在左子树 if (uncle&& uncle->_col == RED)//情况一处理：叔叔存在，且叔叔的颜色是红色的（包含了父亲的颜色是红色的情况）{//根据情况一处理即可：叔叔和父亲变黑，//祖父变红(目的是为了每条路径的黑色结点个数相同)，继续向上cur = grandfather; //孩子parent = cur->_parent; //父亲}else //叔叔不存在 {if (cur == parent->_right)//新增结点在父亲的右边，直线情况左单旋处理{//左单旋转，以grandfather为旋转点，旋转完后parent去做新的根，grandfather去做左子树RotateL(grandfather); //调节颜色grandfather->_col = RED; parent->_col = BLACK; }else //新增结点在父亲的左边，折线情况，引发双旋{//处理：以parenrt为旋转点做右单旋，再以grandfather为旋转点做左单旋RotateR(parent); //右旋RotateL(grandfather); //左旋parent->_col = grandfather->_col = RED; cur->_col = BLACK; }break; }} _root->_col = BLACK; }

拆解讨论：
以下只列举parent在grandfather左边的情况，而parent在grandfather右边的情况处理方式只是反过来的，读者可以自行画图，这里仅留参考代码

Node* uncle = grandfather->_right; if (uncle && uncle->_col == RED)//对应情况：uncle存在且为红{ //处理：父亲和叔叔变成黑色，祖父变成红色，继续向上调整 uncle->_col = parent->_col = BLACK; grandfather->_col = RED; //向上调整 cur = grandfather; //调整孩子 parent = cur->_parent; //调整父亲}

文章图片

else//uncle不存在，uncle存在且为黑{ //直线情况(cur在parent的左边)：只考虑单旋，以grandfather为旋转点进行右单旋转， //旋转完后将祖父的颜色变成红色，将父亲的颜色变成黑色 if (parent->_left == cur) {RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else//parent->_right == cur { //双旋转 }}

文章图片

//折线情况(cur在parent的右边)：这里会引发双旋RotateL(parent); //以parent为旋转点进行左单旋RotateR(grandfather); //以grandfather为旋转点进行右单旋转//旋转完后cur会去做树的根，那么设置为黑色，//为了保证每条路径的黑色结点个数相同，grandfather结点颜色设置为红cur->_col = BLACK; grandfather->_col = RED;

文章图片

旋转

void RotateR(Node* parent) //右单旋 {Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR) subLR->_parent = parent; //防止subLR为nullptrsubL->_right = parent; Node* parent_parent = parent->_parent; //指针备份parent->_parent = subL; if (_root == parent) //如果parent就是树的根 {_root = subL; //subL取代parent_root->_parent = nullptr; }else//如果parent并不是树的根{if (parent_parent->_left == parent) parent->_left = subL; else parent_parent->_right = subL; subL->_parent = parent_parent; //subL去做parent_parent的孩子} } //左单旋 void RotateL(Node* parent) {Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL) subRL->_parent = parent; subR->_left = parent; Node* parent_parent = parent->_parent; parent->_parent = subR; if (_root == parent){_root = subR; _root->_parent = nullptr; }else{if (parent_parent->_left == parent) parent_parent->_left = subR; else parent_parent->_right = subR; subR->_parent = parent_parent; } }

验证

/* 红黑树的几点性质在于： 1、根结点必须是红色的 2、不会出现连续的红色结点 3、所有路径的黑色结点个数是相同的*/bool _CheckBlance(Node* root, int isBlackNum, int count) { if (!root) {if (isBlackNum != count) {printf("黑色结点个数不均等\n"); return false; }return true; //遍历完整棵树，如果以上列举的非法情况都不存在就返回true } //检查是否出现连续的红色结点 if (root->_col == RED && root->_parent->_col == RED) {printf("出现了连续的红色结点\n"); return false; } //走前序遍历的过程中记录每一条路径黑色结点的个数 if (root->_col == BLACK) count++; //递归左右子树 return _CheckBlance(root->_left, isBlackNum, count) && _CheckBlance(root->_right, isBlackNum, count); }//验证红黑树bool CheckBlance(){ if (!_root) return true; //树为null //根结点是黑色的 if (_root->_col != BLACK) {printf("根结点不是黑色的\n"); return false; } //每一条路径黑色结点的个数必须是相同的， int isBlcakNum = 0; Node* left = _root; while (left) {if (left->_col == BLACK) isBlcakNum++; // 统计某一条路径的所以黑色结点个数left = left->_left; } //检查连续的红色结点，检查每一条路径的黑色结点个数是否相等 return _CheckBlance(_root, isBlcakNum ,0); }

红黑树与AVl树的比较红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树，增删改查的
时间复杂度都是O( log n)，红黑树不追求绝对平衡，其只需保证最长路径不超过最短路径的2倍，相对而言，降低了插入和旋转的次数，所以在经常进行增删的结构中性能比AVL树更优，而且红黑树实现比较简单，所以实际运用中红黑树更多。

红黑树的应用