网站图标ico 需要多大,湖南昌正建设有限公司网站,南宁网站建设公司招聘,找做仿网站目录
1. 红黑树的概念和性质
2. 红黑树的插入
2.1. 情况一#xff1a;新增节点的父亲为空
2.2. 情况二#xff1a;新增节点的父亲非空且为黑色节点
2.3. 情况三#xff1a;当父亲为红节点#xff0c;叔叔存在且为红
2.3.1. 当祖父为根节点的时候
2.3.2. 当祖父不是根…目录
1. 红黑树的概念和性质
2. 红黑树的插入
2.1. 情况一新增节点的父亲为空
2.2. 情况二新增节点的父亲非空且为黑色节点
2.3. 情况三当父亲为红节点叔叔存在且为红
2.3.1. 当祖父为根节点的时候
2.3.2. 当祖父不是根节点的时候
2.4. 情况四当父亲为红节点叔叔不存在或者存在为黑
2.5. 情况五父亲为红、叔叔不存在或者为黑
3. 验证红黑树的插入
4. 红黑树插入的完整实现 1. 红黑树的概念和性质 红黑树是一种自平衡的二叉搜索树它通过约束节点的颜色和结构来保持平衡。红黑树是由 Rudolf Bayer 在1972年发明的被认为是一种优秀的平衡树结构广泛应用于各种数据结构和算法中。 红黑树具有以下几个性质 二叉搜索树性质红黑树是一种二叉搜索树即满足以下性质 左子树中的所有节点的键都小于该节点的键。右子树中的所有节点的键都大于该节点的键。左右子树都是二叉搜索树。 节点颜色性质每个节点被标记为红色或黑色 根节点性质根节点为黑色 叶子节点NIL节点性质叶子节点都为黑色的空节点(NIL节点)并被视为红黑树的终止节点 红色节点性质红节点的子节点必须是黑节点不能出现连续的红色节点 黑节点性质从任一节点到其每个叶子节点 (NIL 节点) 的路径上经过的黑节点数量是相同的黑色平衡性 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍以上因而是接近平衡的。 这些性质保证了红黑树的平衡性和有序性。红黑树通过在插入和删除操作中进行颜色调整和旋转操作来维护平衡性。与AVL树相比红黑树对于平衡性的要求相对宽松因此插入和删除操作的平衡调整(旋转)相对较少。 由于红黑树的平衡性其高度相对较小平均时间复杂度为 O(log n)提供了快速的查找、插入和删除操作。红黑树在各种应用中被广泛使用例如C STL中的map和set容器以及各种数据库、编译器和操作系统的实现。 总结来说红黑树是一种具有自平衡性质的二叉搜索树通过约束节点的颜色和结构来保持平衡。它具有二叉搜索树的性质并通过节点颜色、根节点性质、叶子节点性质、红色节点性质和黑节点性质来维护平衡性。红黑树提供了高效的查找、插入和删除操作被广泛应用于不同领域的数据结构和算法中。 思考 为什么红黑树可以保证任何一条路径不会比其他路径长出两倍以上呢 首先我们要知道什么是路径 路径是从根节点开始沿着树的分支一直走到达叶子节点。注意这里的叶子节点特指为空节点在这里一般用NIL节点表示空节点且NIL节点是黑色的。 对于一棵红黑树而言它的最短路径和最长路径分别为 最短路径就是这条路径上的节点是全黑的最长路径该路径是由一黑一红连续组成的。 红黑树的性质告诉我们每条路径上的黑色节点个数是一定的且没有连续的红色节点 那么我们假设最短路径的黑色节点个数为N。 那么最长路径的黑色节点个数也为N其红色节点个数最多也为N那么最长路径的节点个数为2N 因此我们可以得出红黑树的最长路径可以是最短路径的二倍但是不会超过二倍 因此红黑树的任意一条路径的节点个数不可能比其他任何一条路径长过两倍以上以达到近似平衡的状态。 综上所述红黑树通过对节点的着色和结构的限制确保了树的高度相对较小从而保证了没有一条路径会比其他路径长出两倍以上。这种限制确保红黑树保持近似平衡的状态从而提供了较好的性能。 2. 红黑树的插入 如下图所示这就是一颗红黑树 第一个问题如果我们现在要插入一个新节点我们是把这个新节点的初始颜色设置为黑色还是红色呢 假设我把新增节点设置为黑色那么就会有下面的场景 我们发现此时就出现了问题插入了5之后这棵树还是红黑树吗 抱歉根据红黑树的性质每个路径上的黑色节点个数必须相等故插入5之后 (黑色节点)此时这棵树已经不是红黑树了。 但如果我将新增节点的初始颜色设置为红色呢又会出现什么情况如下图所示 我们发现当我们把新增节点的初始颜色设置为红色的时候插入之后会有两种情况 第一种情况插入之后违反了红黑树的规则即不能出现连续的红色节点第二种情况插入之后没有违反任何规则。 综上所述我们将新增节点的初始颜色设置为红色。因为如果新增节点是黑色那么一定会违反红黑树的规则反之如果是红色则可能插入之后不违反任何规则因此我们将新增节点设置为红色。 严格意义上讲红黑树的插入会有五种情况让我们一一进行理解。 2.1. 情况一新增节点的父亲为空 这种情况最为简单就是当是一颗空树的时候直接插入即可。并将新增节点的颜色更新为黑即可。 2.2. 情况二新增节点的父亲非空且为黑色节点 这种情况也很简单直接插入红色节点即可不会破环红黑树的规则。 2.3. 情况三当父亲为红节点叔叔存在且为红 当新增节点的父亲节点和叔叔节点非空且为红时变色即可。 因为 parent 为红那么它一定不是根节点因此它一定有父亲节点即 grandfather 一定不为空。 声明 g --- grandfather(祖父节点 ) p --- parent(父节点) u --- uncle(叔叔节点)c --- cur(新增节点)。 变色规则p、u变黑g变红 如图所示 2.3.1. 当祖父为根节点的时候 2.3.2. 当祖父不是根节点的时候 总结当p、u为红的时候那么将p、u变黑、将g变红c g; p c-parent继续判断如果符合前面的条件(p、u为红)继续向上更新最后为了避免不同的情况将根节点的颜色更新为黑即可。 2.4. 情况四当父亲为红节点叔叔不存在或者存在为黑 父亲为红、叔叔不存在或者存在且为黑且g、p、c在同一条直线上单旋处理处理完插入结束。 因为 parent 为红那么它一定不是根节点因此它一定有父亲节点即 grandfather 一定不为空。 单旋非为左单旋和右单旋两种情况具体操作如图所示 其中a、b、c、d、e代表红黑树子树。 总结当g、p、c在同一条直线上就进行单旋虽然有两种情况但是最后它们的变色情况是一致的p由红变黑 g由黑变红。 2.5. 情况五父亲为红、叔叔不存在或者为黑 父亲为红、叔叔不存在或者存在为黑且g、p、c不在同一条直线上需要双旋处理处理完插入结束。 因为 parent 为红那么它一定不是根节点因此它一定有父亲节点即 grandfather 一定不为空。 双旋非为左右双旋和右左双旋两种情况具体操作如图所示 其中a、b、c、d、e代表红黑树子树。 总结当g、p、c不在同一条直线上(一条折线就是双旋)就进行双旋虽然有两种情况但是最后它们的变色情况是一致的c由红变黑 g由黑变红 p不变保持红色 3. 验证红黑树的插入 思路只要满足下面的所有条件就是红黑树。 第一个条件 根节点是黑色的。第二个条件 红色的节点的左右子树都必须是黑色的也就是说父子节点只能有一个红色节点 思路 只要某节点是红色的那么只要判断它的父亲即可如果父亲是红色的那么就不是红黑树反之则符合红黑树。 第三个条件 每一条路径的黑色节点的个数是相等的步骤 步骤一 先求一条路径上的黑色节点个数作为基准值 步骤二 用该基准值分别于其他所有路径的黑色节点个数进行比较 路径从根节点到 叶子节点。注意这里的叶子节点不是传统意义上的叶子节点在这里把空节点当作叶子节点。 代码如下 bool is_balance_tree()
{// 检查根节点if (_root-_col ! BLACK){std::cout 根节点是红色,异常 std::endl;return false;} return _is_balance_tree(_root);
}bool _is_balance_tree(Node* root)
{if (!root)return true;else{// basic_value作为这颗红黑树的黑色节点个数的基准值int basic_value _get_black_node_num(root);return _is_check_rb_tree(root, 0, basic_value);}
}bool _is_check_rb_tree(Node* root, int black_num, int basic_value)
{// basic_value: 红黑树的一条路径中的黑色节点个数在这里作为基准值if (root nullptr){if (black_num ! basic_value){std::cout 某条路径中的黑色节点个数不相等,异常 std::endl;return false;}elsereturn true;}else{if (root-_col BLACK)black_num;// 如果一个节点是红色的,那么该节点一定不是根,因此一定有父亲// 如果这个节点的父亲也是红色的,那么就说明出现异常if (root-_col RED root-_parent-_col RED){std::cout child: root-_kv.first parent: root-_parent-_kv.first 出现了连续的红色节点,异常 std::endl;return false;}return _is_check_rb_tree(root-_left, black_num, basic_value) _is_check_rb_tree(root-_right, black_num, basic_value);}
}// 获得一条路径的黑色节点的个数
int _get_black_node_num(Node* root)
{if (root nullptr)return 0;else{int ret 0;while (root){if (root-_col BLACK)ret;root root-_left;}return ret;}
}
4. 红黑树插入的完整实现
#pragma once
#include iostream
#include utility
#include assert.h
#include queue
#include vector
#include time.hnamespace Xq
{enum color{RED,BLACK};templateclass K, class Vstruct rb_tree_node{rb_tree_nodeK, V* _left;rb_tree_nodeK, V* _right;rb_tree_nodeK, V* _parent;std::pairK, V _kv;color _col;rb_tree_node(const std::pairK, V kv std::pairK, V()):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}};templateclass K, class Vclass rb_tree{private:typedef rb_tree_nodeK, V Node;public:rb_tree(Node* root nullptr) :_root(root){}bool insert(const std::pairK, V kv){if (!_root){_root new Node(kv);_root-_col BLACK;return true;}else{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);if (kv.first parent-_kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;// 当父节点parent的颜色为红色时,需要调整while (parent parent-_col RED){// 因为父节点parent-_col RED,那么说明parent一定有父节点Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// case 1: 当父节点为红,且叔叔不为空且为红// Solution : 变色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;if (grandfather _root)grandfather-_col BLACK;// 继续向上判断,如果依旧符合case 1,继续变色cur grandfather;parent cur-_parent;continue;}// case 2: 父节点为红,且叔叔为空或者不为空且为黑,并且g、p、c在同一条直线上// Solution: 单旋, 在这里就是对grandfather右单旋else if (parent-_left cur ((!uncle) || uncle-_col BLACK)){// g p// p u --- c g// c uright_rotate(grandfather);parent-_col BLACK;grandfather-_col RED;// 旋转完,更新完颜色,调整就结束break;}// case 3:父节点为红,且叔叔为空或者不为空且为黑,并且g、p、c不在同一条直线上// Solution: 双旋,在这里就是先对p进行左单旋,在对g进行右单旋else if (parent-_right cur ((!uncle) || uncle-_col BLACK)){// g 先对p进行左单旋 g 在对g进行右单旋 c// p u --- c u --- p g // c p uleft_rotate(parent);right_rotate(grandfather);cur-_col BLACK;grandfather-_col RED;// 旋转完,更新完颜色,调整就结束break;}else{// 非法情况assert(false);}}// 当parent是grandfather的右孩子,那么uncle就是grandfather的左孩子else{Node* uncle grandfather-_left;// case 1: 当父节点为红,且叔叔不为空且为红// Solution : 变色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;if (grandfather _root)grandfather-_col BLACK;// 继续向上判断,如果依旧符合case 1,继续变色cur grandfather;parent cur-_parent;continue;}// case 2: 父节点为红,且叔叔为空或者不为空且为黑,并且g、p、c在同一条直线上// Solution: 单旋, 在这里就是对grandfather左单旋else if (parent-_right cur ((!uncle) || uncle-_col BLACK)){// g 对g进行左单旋 p// u p --- g c// c u left_rotate(grandfather);parent-_col BLACK;grandfather-_col RED;//旋转并将颜色更新后,就退出调整break;}// case 3:父节点为红,且叔叔为空或者不为空且为黑,并且g、p、c不在同一条直线上// Solution: 双旋,在这里就是先对p进行右单旋,在对g进行左单旋else if (parent-_left cur ((!uncle) || uncle-_col BLACK)){// g 先对p进行右单旋 g 在对g进行左单旋 c// u p --- u c --- g p// c p u right_rotate(parent);left_rotate(grandfather);cur-_col BLACK;grandfather-_col RED;break;}else{// 非法情况,断死assert(false);}}}_root-_col BLACK;return true;}}void level_order(){_level_order(_root);}bool is_balance_tree(){if (_root-_col ! BLACK){std::cout 根节点是红色的,异常 std::endl;return false;}return _is_balance_tree(_root);}int get_rb_tree_high(){return _get_rb_tree_high(_root);}private:void _level_order(Node* root){if (!root)return;else{std::queueNode* qu;qu.push(root);while (!qu.empty()){Node* front qu.front();qu.pop();if (front){qu.push(front-_left);qu.push(front-_right);}if (!front)std::cout N ;elsestd::cout front-_kv.first ;}std::cout std::endl;}}void left_rotate(Node* parent){Node* cur parent;Node* cur_right cur-_right;Node* cur_right_left cur_right-_left;Node* cur_parent cur-_parent;cur-_right cur_right_left;if (cur_right_left)cur_right_left-_parent cur;cur_right-_left cur;cur-_parent cur_right;if (!cur_parent){cur_right-_parent nullptr;_root cur_right;}else{if (cur_parent-_left cur){cur_parent-_left cur_right;}else{cur_parent-_right cur_right;}cur_right-_parent cur_parent;}}void right_rotate(Node* parent){Node* cur parent;Node* cur_left cur-_left;Node* cur_left_right cur_left-_right;Node* cur_parent cur-_parent;cur-_left cur_left_right;if (cur_left_right)cur_left_right-_parent cur;cur_left-_right cur;cur-_parent cur_left;if (!cur_parent){cur_left-_parent nullptr;_root cur_left;}else{if (cur_parent-_kv.first cur_left-_kv.first){cur_parent-_left cur_left;}else{cur_parent-_right cur_left;}cur_left-_parent cur_parent;}}bool _is_balance_tree(Node* root){if (!root)return true;else{int basic_value _get_black_node_num(root);return _is_check_rb_tree(root, 0, basic_value);}}bool _is_check_rb_tree(Node* root, int black_num, int basic_value){// basic_value: 红黑树的一条路径中的黑色节点个数在这里作为基本值if (root nullptr){if (black_num ! basic_value){std::cout 路径中的黑色节点个数不相等,异常 std::endl;return false;}elsereturn true;}else{if (root-_col BLACK)black_num;// 如果一个节点是红色的,那么该节点一定不是根,因此一定有父亲// 如果这个节点的父亲也是红色的,那么就说明出现异常if (root-_col RED root-_parent-_col RED){std::cout child: root-_kv.first parent: root-_parent-_kv.first 出现了连续的红色节点,异常 std::endl;return false;}return _is_check_rb_tree(root-_left, black_num, basic_value) _is_check_rb_tree(root-_right, black_num, basic_value);}}int _get_black_node_num(Node* root){if (root nullptr)return 0;else{int ret 0;while (root){if (root-_col BLACK)ret;root root-_left;}return ret;}}int _get_rb_tree_high(Node* root){if (root nullptr)return 0;else{int left_high _get_rb_tree_high(root-_left);int right_high _get_rb_tree_high(root-_right);return left_high right_high ? left_high : right_high;}}private:Node* _root;};
}
