建设银行网站每天几点更新,网络营销推广方案,小孩子和大人做的网站,域名查询网138⭐博客主页#xff1a;️CS semi主页 ⭐欢迎关注#xff1a;点赞收藏留言 ⭐系列专栏#xff1a;C进阶 ⭐代码仓库#xff1a;C进阶 家人们更新不易#xff0c;你们的点赞和关注对我而言十分重要#xff0c;友友们麻烦多多点赞#xff0b;关注#xff0c;你们的支持是我… ⭐博客主页️CS semi主页 ⭐欢迎关注点赞收藏留言 ⭐系列专栏C进阶 ⭐代码仓库C进阶 家人们更新不易你们的点赞和关注对我而言十分重要友友们麻烦多多点赞关注你们的支持是我创作最大的动力欢迎友友们私信提问家人们不要忘记点赞收藏关注哦 【高阶数据结构】红黑树 一、红黑树的概念二、红黑树的性质三、红黑树结点的定义四、红黑树结点的插入对红黑树是否需要调整怎么调整情况一、插入的叔叔结点存在且为红色情况二、插入的叔叔结点存在且为黑色一条直线型折线 情况三、插入结点的叔叔结点不存在一条直线型折线 代码操作 五、验证是否是红黑树六、红黑树的高度七、红黑树的查找八、红黑树的删除一情况一二情况二1、brother为红色2、brother为黑色且其左右孩子都是黑色结点或为空3、brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空4、brother为黑色且其右孩子是红色结点 三右边子树四情况说明五删除操作代码 九、红黑树与AVL树的比较 一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。 二、红黑树的性质
红黑树的五大性质
1、每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
我们需要思考一个问题为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍
根据性质三说明红节点后必定是黑节点红黑树中不可能出现连续的红色结点再根据性质四说明在每个结点的后代结点的简单路径上均包含相同数目的黑色结点。 假如我们假设有N个黑色结点那么最短路径就是全部由黑色结点构成的路径其长度为N。 最长可能路径是一黑一红间隔往下排列所以总长度为2N。 所以红黑树从根到叶子的最长可能路径不超过最短可能路径的2倍。
三、红黑树结点的定义
我们定义了一个K-V的模型的红黑树。为了方便后续的旋转操作我们将红黑树的结点定义为三叉链的结构我们还加入了一个定义结点颜色的枚举类型表示结点的颜色。
// 定义结点颜色
enum Col
{RED,BLACK
};// 定义红黑树结点
templateclass K, class V
struct RBTreeNode
{// 构造函数RBTreeNode(const pairK, V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED),_kv(kv){}// 三叉链RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;// 存储颜色int _col;// 存储键值对pairK, V _kv;
};四、红黑树结点的插入
插入之前我们先思考一个简单的问题每次插入插入什么颜色的结点呢 答案是红色结点为什么呢 因为我们假如插入的是黑色结点发现这条路径下的黑色结点比别的路径下的黑色结点多了一个就会违背性质四所以就需要调整黑色结点和红色结点调整的结点数有可能是全部而加入说我们插入的是红色结点这条路上的黑色结点是没有增加的而且其他路的黑色结点也都是没有增加的所以是平衡的但有一种情况是其父节点是红色的插入的是红色结点就会导致连续的红色结点即违背了性质三所以也是需要调整的我们在下面进行总结 1、插入黑色结点失误点在于必然导致这一条路径下黑色结点增多违背性质四必须要调整颜色。 2、插入红色结点失误点在于可能其父节点为红色需要调整但如果其父节点本来就是黑色那就不需要调整。 所以我们在根据权衡利弊后决定需要插入红色结点。
插入过程三段步骤和AVL树的插入整体思路大致相同 1、找根据二叉搜索树的插入方法找到待插入位置。 2、插将待插入结点插入到树中。 3、调若插入结点的父结点是红色的则需要对红黑树进行调整。 对红黑树是否需要调整怎么调整
并不是所有的红黑树都需要调整有一种情况是需要调整的结点的父节点为黑色结点我们插入红色的结点并不会对本树有影响所以这种情况是不需要进行调整的。
所以只有插入结点的父节点为红色结点才需要进行调整的因为这样会出现连续的红色结点此时也说明了其父节点绝对不是根节点因为性质二是根节点root是黑色的所以其插入结点的祖父结点一定存在此时红黑树的调整需要判断父节点的兄弟结点即叔叔结点所以根据叔叔结点来判断一下不同的情况
情况一、插入的叔叔结点存在且为红色
为了保持没有连续的红色结点我们可以将父节点变黑因为要保证每一条路径的黑色结点是一样的所以就需要将叔叔节点也变成黑色的。同样也解决了红色结点连续的问题。
但此时调整并没有完因为我们不确定祖父节点是不是整个红黑树的根节点所以就需要进行判断
如果祖父节点是根节点我们仅需要将组父节点变成黑色的即可也就是每条路上多增加了一个黑色结点不影响。
而如果祖父节点不是根节点我们就需要继续往上判断判断祖父的父节点的颜色再根据这些进行判断叔叔节点。
此时不管cur在父节点的左孩子还是右孩子其调整都是一样的。
情况二、插入的叔叔结点存在且为黑色
这种情况我们可以进行具体的分析一下我们画张图表示
我们插入的话是这样的但是不知道大家有没有发现一个错误这我们不是说每条路径下黑色节点是一样的吗我们假设组父节点g之上的黑色结点数为x个叔叔结点之下的黑色节点为y个则在插入cur之前我们的左右两边的黑色结点数分别为x1路径一直到NIL空结点和xy2。明显右子树的黑色结点多根本不满足红黑树的要求所以这个插入情况肯定不是在新插入时候的情况而是在情况一往上进行更新的过程中存在的。
注意小贴士 1、我们算黑色结点是需要算到空的也就是我们的NIL结点不是到叶子结点结束而是算到它下面的空结点。 2、出现这种情况我们单纯靠变色是肯定不行的所以就需要我们进行像AVL树的旋转操作而旋转操作以后是不需要继续往上调整了。
两种情况
一条直线型
仅用单旋左旋或者是右旋我们这里列举一种情况用右单旋–p在g的左孩子cur在p的左孩子 左单旋的情况是p在g的右孩子cur在p的右孩子。
折线
若curpg这三个结点成为一条折线的情况下需要进行双旋操作再进行变色处理我们这里讲解一下左右双旋即先左单旋再右单旋我们画个抽象图 当p是g的右孩子cur是p的左孩子的时候用的是右左双旋。
情况三、插入结点的叔叔结点不存在
我们还是分析一下这个结点cur是否是新插入的结点我们先来画一张图来解决一下
一条直线型
我们下面图是使用右单旋
当p是g的右孩子cur也是p的右孩子的时候我们使用的是左单旋之后再进行变色处理即可。
折线
当cur、p、g三个结点成为一条折线的时候是需要进行双旋的我们下面使用的是左右双旋 若p是g的右孩子cur是p的左孩子的时候是右左双旋再进行改变颜色。
代码操作
我们在进行代码书写之前我们需要了解一下pair中的尖括号有一个很奇妙的作用也就是前面存储指针后面存储bool值显示是不是插入成功。我们可以简单了解一下:pairNode*, true和Node*, false前面一个代表插入的指针后面一个变量表明是否插入成功。
// 插入pairNode*, bool Insert(const pairK, V kv){// 一棵空树if (_root nullptr){// 创建新结点 颜色初始化为黑色_root new Node(kv);_root-_col BLACK; // 根节点得是黑的return make_pair(_root, 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 make_pair(cur, false);}}// 将当前结点的值插入进去cur new Node(kv); // new一个新的结点cur-_col RED;Node* newnode cur; // 记录新插入的结点// 新插入的节点值小于父节点的节点值插入到parent的左边if (kv.first parent-_kv.first){parent-_left cur;cur-_parent parent;}// 新插入的节点值小于父节点的节点值插入到parent的左边else{parent-_right cur;cur-_parent parent;}// 新插入结点的父节点是红色的需要做出调整while (parent parent-_col RED){Node* grandfather parent-_parent; // parent是红色则其父结点一定存在// 以grandparent左右孩子为分界线分成if和elseif (parent grandfather-_left) // 左孩子{Node* uncle grandfather-_right;if (uncle uncle-_col RED)// 情况一uncle存在且为红色{// 颜色调整grandfather-_col RED;uncle-_col parent-_col BLACK;// 继续往上处理cur grandfather;parent cur-_parent;}else// 情况二uncle存在且为黑色 / 情况三uncle不存在{// 用左右孩子分为两半一半是if用来表示在左孩子一半是else用来表示在右孩子if (cur parent-_left){// g// p// c// 右单旋RoateR(grandfather);// 颜色调整parent-_col BLACK;grandfather-_col RED;}else{// g// p// c// 左右双旋RoateLR(grandfather);// 颜色调整cur-_col BLACK;grandfather-_col RED;}break;}}else // 右孩子{Node* uncle grandfather-_left;if (uncle uncle-_col RED)// 情况一uncle存在且为红色{// 颜色调整grandfather-_col RED;uncle-_col parent-_col BLACK;// 继续往上处理cur grandfather;parent cur-_parent;}else// 情况二uncle存在且为黑色 / 情况三uncle不存在{// 用左右孩子分为两半一半是if用来表示在左孩子一半是else用来表示在右孩子if (cur parent-_right){// g// p// c// 左单旋RoateL(grandfather);// 颜色调整parent-_col BLACK;grandfather-_col RED;}else{// g// p// c// 右左双旋RoateRL(grandfather);// 颜色调整cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return make_pair(newnode, true);}// 左单旋void RoateL(Node* parent){// 三叉链Node* subr parent-_right;Node* subrl subr-_left;Node* ppnode parent-_parent;// subrl与parent的关系parent-_right subrl;if (subrl)subrl-_parent parent;// subl和parent的关系subr-_left parent;parent-_parent subr;// ppnode和subr的关系if (ppnode nullptr){_root subr;subr-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subr;}else{ppnode-_right subr;}subr-_parent ppnode;}}// 右单旋void RoateR(Node* parent){// 三叉链Node* subl parent-_left;Node* sublr subl-_right;Node* ppnode parent-_parent;//sublr和parent之间的关系parent-_left sublr;if (sublr)sublr-_parent parent;//subl和parent的关系subl-_right parent;parent-_parent subl;//ppnode 和 subl的关系if (ppnode nullptr){_root subl;subl-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left subl;}else{ppnode-_right subl;}subl-_parent ppnode;}}// 左右双旋void RoateLR(Node* parent){RoateL(parent-_left);RoateR(parent);}// 右左双旋void RoateRL(Node* parent){RoateR(parent-_right);RoateL(parent);}五、验证是否是红黑树
先验证一下是否是平衡二叉树。 // 中序遍历void InOrder(){return _InOrder(_root);}void _InOrder(Node* root){if (root nullptr)return;// 中序_InOrder(root-_left);cout root-_kv.first ;_InOrder(root-_right);}// 验证是否平衡// 先检查检查颜色bool CheckColour(Node* root, int blacknum, int blenchnum) // 基准值{if (root nullptr){// 每个路径黑色不相等if (blacknum ! blenchnum){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, blenchnum) CheckColour(root-_right, blacknum, blenchnum);}// 再检查是否平衡bool IsRBTree(){return _IsRBTree(_root);}bool _IsRBTree(Node* root){if (root nullptr){return true;}if (root-_col RED){return false;}// 找最左路径作为黑色结点数目的参考值int blenchnum 0;Node* cur _root;while (cur){if (cur-_col BLACK)blenchnum;cur cur-_left;}return CheckColour(root, 0, blenchnum);}六、红黑树的高度
其实很简单红黑树的高度算的是左右子树中最高的那个树的层数的高度所以我们仅仅需要计算一下左右子树中最高的那棵子树即可。 // 计算树的高度int Height(){return _Height(_root);}int _Height(Node* root){if (root nullptr){return 0;}int leftcount _Height(root-_left);int rightcount _Height(root-_right);return leftcount rightcount ? leftcount 1 : rightcount 1;}七、红黑树的查找
与搜索二叉树的查找方式是一模一样的 1、要找的值比当前结点小往左子树走 2、要找的值比当前结点大往右子树走 3、要找的值等于当前结点找到了 4、找到空都没找到则返回空 // 红黑树的查找Node* Find(const pairK, V kv){Node* cur _root;while (cur){// 当前结点的值大于寻找的结点的值if (cur-_kv.first kv.first){cur cur-_left;}else if(cur-_kv.first kv.first){cur cur-_right;}else{// 找到了return cur;}}return nullptr;}八、红黑树的删除 第一步先找待删除的结点 与搜索二叉树大致相同如果我们找到待删除的结点的左右子树不为空则需使用替换法进行删除所以我们最终需要删除的都是左右子树至少有一个为空的结点。 第二步调整红黑树 同样跟AVL树一样先需要判断是否对红黑树的颜色有影响如果破坏了红黑树的四条性质那就需要调整红黑树。
如果本次删除结点为红色结点的话那么本次删除操作不会破坏红黑树的性质因此我们不需要对红黑树进行调整。然而如果本次删除的结点为黑色结点的话那么本次删除操作必然会破坏红黑树的性质因为黑色结点的减少必然会破坏性质四所以就需要对红黑树做出调整。
一情况一
待删除的结点只有一个孩子左孩子/右孩子即待删除的结点是只有一个孩子为空的情况。 二情况二
待删除结点的左右孩子的结点都是空的。 我们以待删除结点是其父结点的左孩子为例分为以下四种情况
1、brother为红色 当待删结点的brother为红色的情况下先以parent为旋转点进行左单旋将brother当老大再进行颜色的调整brother变成黑色parent变成红色我们再对cur做分析这样就是下面三种情况了。
2、brother为黑色且其左右孩子都是黑色结点或为空 3、brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空 我们先以brother为旋转点进行右单旋再将brother颜色变红brotherleft颜色变黑再需要根据情况变成情况四的情况。
4、brother为黑色且其右孩子是红色结点 我们进入到第四种情况时候就结束了调整以parent为旋转点进行一次左单旋然后将parent的颜色赋值给brother再将parent的颜色变为黑色最后将brotherRight变为黑色。
三右边子树
右边子树和左边子树是大同小异的。
四情况说明
我们总共有四种情况最重要的是我们需要走到第四种情况这样红黑树的调整才是好了所以我们有下面的关系 1-2,3,4 2-1,2,3,4 3-4 4-结束 我们知道了关系所以4是一定能退出的3能够转化到4然后退出的1能够转化为2,3,4也是有办法退出的而只有2这种情况最纠结了因为刚进入2这种情况parent的颜色是个迷不管是黑色还是红色都是没有问题的
五删除操作
根据搜索二叉树的删除规则连接这个结点的左/右孩子即可。
代码 // 删除bool Erase(const K key){// 用于遍历二叉树找结点Node* parent nullptr;Node* cur _root;// 用于标记实际的删除结点及其父结点Node* delparentpos nullptr;Node* delpos nullptr;// 先找到while (cur){// 所给key值小于当前节点的值 -- 往左树走if (key cur-_kv.first){parent cur;cur cur-_left;}// 所给key值大于当前结点的值 -- 往右树走else if (key cur-_kv.first){parent cur;cur cur-_right;}// 找到了else{// 左子树为空if (cur-_left nullptr){// 待删除结点是根节点if (cur _root){// 让根节点的右子树作为新的结点_root _root-_right;if (_root)_root-_parent nullptr;delete cur; // 删除原节点return true;}else // 不是根节点{delparentpos parent; // 标记当前待删除结点的父节点delpos cur; // 标记当前待删除的结点}break; // 删除结点有祖先的结点需要更新平衡因子}// 右子树为空else if (cur-_right nullptr){// 待删除结点是根节点if (cur _root){// 让根节点的左子树作为新的结点_root _root-_left;if (_root)_root-_parent nullptr;delete cur; // 删除原节点return true;}else // 不是根节点{delparentpos parent; // 标记当前待删除结点的父节点delpos cur; // 标记当前待删除的结点}break; // 删除结点有祖先的结点需要更新平衡因子}// 左右子树都不为空else{// 替换法// 寻找待删除结点的右子树中的最小值Node* minparent cur;Node* minright cur-_right;while (minright-_left){minparent minright; // 记录一下父节点minright minright-_left; // 往左子树走}cur-_kv.first minright-_kv.first;// 将待删除结点first替换为右子树的最小值cur-_kv.second minparent-_kv.second;// 将待删除结点second替换为右子树的最小值// 记录一下要删除的父节点delparentpos minparent;// 记录一下实际要删除的结点delpos minright;break; // 祖先结点的平衡因子需要改变}}}// 没有被修改过说明没找到当前要删除的结点if (delparentpos nullptr)return false;// 记录当前要删除结点和当前要删除结点的父节点Node* del delpos;Node* delP delparentpos;// 调整红黑树if (delpos-_col BLACK){if (delpos-_left delpos-_left-_col RED) //待删除结点有一个红色的左孩子{// delpos// _leftdelpos-_left-_col BLACK; //将这个红色的左孩子变黑}else if (delpos-_right delpos-_right-_col RED) //待删除结点有一个红色的右孩子{// delpos// _rightdelpos-_right-_col BLACK; //将这个红色的右孩子变黑}else // 待删除结点的左右均为空{while (delpos ! _root){// 待删除的结点是其父节点的左孩子if (delpos delparentpos-_left){// delparentpos// delpos brotherNode* brother delparentpos-_right; // 兄弟结点是其父结点的右孩子// 情况1:brother为红色if (brother-_col){// 先左旋再调颜色RoateL(delparentpos);delparentpos-_col RED;brother-_col BLACK;// 继续向上调整brother delparentpos-_right;}// 情况2brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;// 分情况if (delparentpos-_col RED){delparentpos-_col BLACK;break;}// 向上调整delpos delparentpos;delparentpos delpos-_parent;}else{// 情况3brother为黑色且其右孩子是红色结点// 左旋RoateL(delparentpos);brother-_col delparentpos-_col;delparentpos-_col BLACK;brother-_right-_col BLACK;break;// 情况4brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_right nullptr) || (brother-_right-_col BLACK)){brother-_left-_col BLACK;brother-_col RED;RoateR(brother);brother delparentpos-_right; }}}// 待删除的结点是其父节点的右孩子else{Node* brother delparentpos-_right; // 兄弟结点是其父结点的右孩子// 情况1brother为红色if (brother-_col RED){RoateR(delparentpos);delparentpos-_col RED;brother-_col BLACK;// 继续向上调整brother delparentpos-_left;}// 情况2brother为黑色且其左右孩子都是黑色结点或为空if (((brother-_left nullptr) || (brother-_left-_col BLACK)) ((brother-_right nullptr) || (brother-_right-_col BLACK))){brother-_col RED;if (delparentpos-_col RED){delparentpos-_col BLACK;break;}delpos delparentpos;delparentpos delpos-_parent;}else{// 情况3brother为黑色且其右孩子是红色结点RoateR(delparentpos);brother-_col delparentpos-_col;delparentpos-_col BLACK;brother-_left-_col BLACK;break;// 情况4brother为黑色且其左孩子是红色结点右孩子是黑色结点或为空if ((brother-_left nullptr) || (brother-_left-_col BLACK)){brother-_right-_col BLACK;brother-_col RED;RoateL(brother);brother delparentpos-_left;}}}}}}// 进行删除// 删除的结点的左子树是空树if (del-_left nullptr){if (del delP-_left) //删除结点是其父结点的左孩子{delP-_left del-_right;if (del-_right)del-_right-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_right;if (del-_right)del-_right-_parent delP;}}else // 删除的结点的右子树是空树// del-_right nullptr {if (del delP-_left) //实际删除结点是其父结点的左孩子{delP-_left del-_left;if (del-_left)del-_left-_parent delP;}else //实际删除结点是其父结点的右孩子{delP-_right del-_left;if (del-_left)del-_left-_parent delP;}}delete del;return true;}九、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O( l o g 2 N log_2 N log2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
