项目计划书模板word,网站建设优化推广系统,保定网站建设电话,哈尔滨品牌设计公司#x1f3ac;慕斯主页#xff1a;修仙—别有洞天 #x1f49c;本文前置知识#xff1a; AVL树 ♈️今日夜电波#xff1a;Letter Song—ヲタみん 1:36━━━━━━️#x1f49f;──────── 5:35 … 慕斯主页修仙—别有洞天 本文前置知识 AVL树 ♈️今日夜电波Letter Song—ヲタみん 1:36━━━━━━️──────── 5:35 ◀️ ⏸ ▶️ ☰ 关注点赞收藏您的每一次鼓励都是对我莫大的支持 目录 一、前言 红黑树的概念 红黑树与二叉搜索树的异同 二、红黑树的实现 节点的定义 AVL树的初始化定义
红黑树的插入重点及难点 插入大致步骤 插入的总体逻辑 按照二叉搜索树的方法插入节点 父节点为红色 需要进行相应的调整 情况一: cur为红p为红g为黑u存在且为红 情况二: cur为红p为红g为黑u不存在/u存在且为黑编辑 情况三: cur为红p为红g为黑u不存在/u存在且为黑 插入实现 根据构建红黑树的规则验证红黑树 求红黑树高度以及遍历红黑树 三、总体代码 一、前言 本文是基于二叉搜索树以及AVL树的知识前提下对于红黑树进行叙述的主要叙述的方面同AVL树一样主要是在于插入方面的解析其它部分同AVL树和二叉搜索树还是有些相似的。但是对于删除部分来说红黑树就太难了举个例子插入部分红黑树的实现大概180行代码而删除则是400往上接近500行了。难度可想而知作者如果有能力后续会慢慢补齐的 红黑树的概念 红黑树是一种自平衡二叉查找树它的每个节点都有一个颜色属性可以是红色或黑色。红黑树的特性如下 每个节点要么是红色要么是黑色。根节点是黑色。所有的叶子节点NIL节点都是黑色。注意NIL实际上空节点只不过我们将所有空节点看作黑色节点而已如果一个节点是红色那么它的两个子节点都是黑色。意味着黑色可以有黑色的节点也可以有红色的节点但是红色只能有黑色的节点对于每个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点。 这些特性保证了红黑树的搜索效率。在最坏的情况下搜索一棵高度为h的红黑树的时间复杂度是O(h)与AVL树相当。此外由于红黑树的插入和删除操作不需要像AVL树那样频繁地旋转因此红黑树在实际应用中比AVL树更加稳定和高效。 在实际应用中红黑树常用于实现关联数组哈希表的数据结构以及数据库索引等场合。 红黑树与二叉搜索树的异同 红黑树和二叉搜索树的主要区别在于它们如何处理数据冲突。 二叉搜索树BST是一种特殊的二叉树其中每个节点都存储一个键值并且满足左子树中的所有键值小于根节点的键值右子树中的所有键值大于根节点的键值。这使得搜索、插入和删除操作可以在平均情况下以O(log n)的时间复杂度完成。 红黑树也是一种二叉搜索树但它通过限制每个节点的颜色和位置关系来保持树的平衡从而确保搜索、插入和删除操作的时间复杂度始终为O(log n)。与BST不同的是红黑树还具有以下特点 * 每个节点要么是红色要么是黑色。 * 根节点是黑色。 * 所有的叶子节点NIL节点空节点都是黑色。 * 如果一个节点是红色那么它的两个子节点都是黑色。 * 对于每个节点从该节点到其所有后代叶节点的简单路径上均包含相同数目的黑色节点。 这些特性使得红黑树在实际应用中更加强大和灵活。例如红黑树可以通过左右旋转变换快速调整树的形状从而应对动态数据集的变化。此外红黑树还可以应用于许多不同的场景如数据库索引、排序算法、集合类数据结构等等。 二、红黑树的实现 节点的定义 使用枚举来定义结点的颜色提高代码的可读性。定义三叉链方便后续的旋转等等操作定义KV结构的红黑树定义一个枚举变量用于储存颜色。通过构造函数初始化节点。 enum Color
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};AVL树的初始化定义
templateclass K, class V
struct RBTree
{typedef RBTreeNodeK, V Node;public:bool Insert(const pairK, V kv)//插入操作bool IsBalance();//判断是否符合红黑树int Height();//求高度private:Node* _root nullptr;//给缺省初始化}; 红黑树的插入重点及难点 插入大致步骤 下面是红黑树插入的大致步骤 1. 向红黑树中插入新的节点。 2. 确保新节点的颜色为红色。 3. 确保新插入的节点不会破坏红黑树的性质。如果新节点违反了某些性质则需要对红黑树进行旋转操作或更改节点的颜色。 4. 返回到插入节点的父节点继续执行第3步直到所有违反性质的节点都被修复为止。 具体来说当我们向红黑树中插入新的节点时我们需要遵循以下规则 - 每个节点都是红色或黑色。 - 根节点是黑色。 - 所有叶子节点NIL节点空节点都是黑色。 - 如果一个节点是红色则它的两个子节点都是黑色。 - 对于每个节点从该节点到其所有后代叶子节点的简单路径上均包含相同数目的黑色节点。 如果我们违反了这些规则中的任何一个我们就可以通过旋转操作或更改节点的颜色来修复这个问题。例如如果我们发现某个节点有两个子节点都是红色的那么我们就需要将这个节点以及其两个子节点的颜色全部改为黑色然后再将该节点的父节点变为红色。这样就可以确保新插入的节点不会破坏红黑树的性质。 插入的总体逻辑 按二叉搜索树的插入方法找到待插入位置。将待插入结点插入到树中。新插入的节点默认为红若插入结点的父结点是红色的则需要对红黑树进行调整。按情况进行调整情况一: cur为红p为红g为黑u存在且为红。-将p,u改为黑g改为红然后把g当成cur继续向上调整。情况二: cur为红p为红g为黑u不存在/u存在且为黑-p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转p、g变色--p变黑g变红。情况三: cur为红p为红g为黑u不存在/u存在且为黑-p为g的左孩子cur为p的右孩子则针对p做左单旋转再对g做右单旋相反 p为g的右孩子cur为p的左孩子则针对p做右单旋转再对g做左单旋。 按照二叉搜索树的方法插入节点 按照搜索二叉树大往右小往左的思想找到对应的节点插入节点并且链接。大致步骤都是同二叉搜索树是相同的只不过需要注意的是新插入的节点默认都是红色的。当父节点为黑色时直接插入即可。 bool Insert(const pairK, V kv)
{if (_root nullptr)//如果根节点为空则直接开辟一个节点作为根节点并且返回true{_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;//后续遍历找位置以及旋转等Node* cur _root;//遍历用while (cur) // 开始遍历到指定位置-其实就是到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 false;}}//默认新增节点给红色防止给黑破坏平衡cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first)//同父节点比大小{parent-_right cur;//链接新节点}else{parent-_left cur;//链接新节点}cur-_parent parent;//新节点链接父节点//后续根据红黑树特性开始调整...//调整完毕}_root-_col BLACK;//将根处理成黑。因为插入向上处理会改变但是当最后为根时改变后就不能进入循环因此需要最后处理为黑return true;
} 父节点为红色 需要进行相应的调整 重点在于看舅舅节点看舅舅节点的存在与否存在的话是红色还是黑色 根据舅舅节点来确定相应的调整操作。然后再看新插入节点cur处于parent的位置在左还是在右进行相应的调整策略。 情况一: cur为红p为红g为黑u存在且为红 当cur为红p为红g为黑u存在且为红时将p,u改为黑g改为红然后把g当成cur继续向上调整。 情况二: cur为红p为红g为黑u不存在/u存在且为黑 当cur为红p为红g为黑u不存在/u存在且为黑u不存在如果p为g的左cur为p的左如上图一所示则只需对g进行右单旋如果p为g的右cur为p的右则只需对g进行左单旋然后p、g变色--p变黑g变红。 当u存在且为黑即如上图二第2步所示。由图二1、2步我们可以知道cur是由于新增节点而变化而来的我们也可以根据红黑树的定义可知c、d、e分别为对应箭头的颜色。由此我们需要进行对应的旋转以及变色操作对于以上u存在且为黑如果p为g的左cur为p的左则如图二第3步所示对p进行右单旋如果p为g的右cur为p的右则只需对g进行左单旋然后p、g变色--p变黑g变红。 情况三: cur为红p为红g为黑u不存在/u存在且为黑 当cur为红p为红g为黑u不存在/u存在且为黑但是此时,如果p为g的左cur为p的右则如图所示需先对p进行左单旋再对g进行右单旋。如果p为g的右cur为p的左则需对p进行右单旋再对g进行左单旋。然后c、g变色--c变黑g变红。 插入实现 bool Insert(const pairK, V kv){if (_root nullptr)//如果根节点为空则直接开辟一个节点作为根节点并且返回true{_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;//后续遍历找位置以及旋转等Node* cur _root;//遍历用while (cur) // 开始遍历到指定位置-其实就是到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 false;}}//默认新增节点给红色防止给黑破坏平衡cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first)//同父节点比大小{parent-_right cur;//链接新节点}else{parent-_left cur;//链接新节点}cur-_parent parent;//新节点链接父节点//根据红黑树特性开始调整while (parent parent-_col RED)//由于子节点和父节点都是红色则需要调整{Node* grandfather parent-_parent;//储存爷爷节点用于找舅舅节点以及变色甚至旋转if (parent grandfather-_left){// g// p u// cNode* uncle grandfather-_right;//如果父亲节点在爷爷的左则舅舅在右if (uncle uncle-_col RED)//情况一“变色处理” 舅舅节点存在且为红色则我们需要将父亲以及舅舅变黑爷爷变红{// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else //情况二“需要旋转单旋or双旋变色处理” 即舅舅节点存在时为黑或者舅舅节点不存在则我们需要进行相应的旋转{if (cur parent-_left){// 单旋// g p // p - c g// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// 双旋// g g p // p - c - c g// c pRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{// g// u p // c//Node* uncle grandfather-_left;//情况一但是uncle在左// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else//情况二“需要旋转单旋or双旋变色处理”{if (cur parent-_right){// 单旋// g p // p - g c// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g g c// u p - u c - g p// c p u//RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;//将根处理成黑。因为插入向上处理会改变但是当最后为根时改变后就不能进入循环因此需要最后处理为黑return true;}void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}} 根据构建红黑树的规则验证红黑树
1. 每个结点不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色的则它的两个孩子结点是黑色的
4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点
5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) bool IsBalance(){return _IsBalance(_root);}// 根节点-当前节点这条路径的黑色节点的数量bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK)//统计黑色用于判断每条路径黑色都相同{blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){//当前节点与父节点连续红色cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);//递归遍历每条路径}bool _IsBalance(Node* root){//根据构建红黑树的规则进行判断if (root nullptr)return true;if (root-_col ! BLACK)//根不能为红{return false;}// //参考值,统计一条路径的黑色节点数int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//通过检查每条路径的黑色节点数判断是否平衡return CheckColour(root, 0, benchmark);} 求红黑树高度以及遍历红黑树 基本上就是同AVL树以及搜索二叉树相同的道理。 int Height(){return _Height(_root);}//中序遍历void Inorder(){_Inorder(_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(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);} 三、总体代码
#pragma once
#includeiostream
using namespace std;enum Color
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
struct RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, V kv){if (_root nullptr)//如果根节点为空则直接开辟一个节点作为根节点并且返回true{_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;//后续遍历找位置以及旋转等Node* cur _root;//遍历用while (cur) // 开始遍历到指定位置-其实就是到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 false;}}//默认新增节点给红色防止给黑破坏平衡cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first)//同父节点比大小{parent-_right cur;//链接新节点}else{parent-_left cur;//链接新节点}cur-_parent parent;//新节点链接父节点//根据红黑树特性开始调整while (parent parent-_col RED)//由于子节点和父节点都是红色则需要调整{Node* grandfather parent-_parent;//储存爷爷节点用于找舅舅节点以及变色甚至旋转if (parent grandfather-_left){// g// p u// cNode* uncle grandfather-_right;//如果父亲节点在爷爷的左则舅舅在右if (uncle uncle-_col RED)//情况一“变色处理” 舅舅节点存在且为红色则我们需要将父亲以及舅舅变黑爷爷变红{// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else //情况二“需要旋转单旋or双旋变色处理” 即舅舅节点存在时为黑或者舅舅节点不存在则我们需要进行相应的旋转{if (cur parent-_left){// 单旋// g p // p - c g// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// 双旋// g g p // p - c - c g// c pRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{// g// u p // c//Node* uncle grandfather-_left;//情况一但是uncle在左// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else//情况二“需要旋转单旋or双旋变色处理”{if (cur parent-_right){// 单旋// g p // p - g c// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g g c// u p - u c - g p// c p u//RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;//将根处理成黑。因为插入向上处理会改变但是当最后为根时改变后就不能进入循环因此需要最后处理为黑return true;}void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}bool IsBalance(){return _IsBalance(_root);}int Height(){return _Height(_root);}//中序遍历void Inorder(){_Inorder(_root);}private:// 根节点-当前节点这条路径的黑色节点的数量bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK)//统计黑色用于判断每条路径黑色都相同{blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){//当前节点与父节点连续红色cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);//递归遍历每条路径}bool _IsBalance(Node* root){//根据构建红黑树的规则进行判断if (root nullptr)return true;if (root-_col ! BLACK)//根不能为红{return false;}// //参考值,统计一条路径的黑色节点数int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}//通过检查每条路径的黑色节点数判断是否平衡return CheckColour(root, 0, benchmark);}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(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}private:Node* _root nullptr;public:int _rotateCount 0;
}; 感谢你耐心的看到这里ღ( ´ᴗ )比心如有哪里有错误请踢一脚作者o(╥﹏╥)o 给个三连再走嘛~
