门窗网站制作宣传语泰州seo管理

当前位置： 首页 > news >正文

门窗网站制作宣传语,泰州seo管理,金华市住房和城乡建设厅网站,郑州网站权重前言#xff1a; AVL树与红黑树相似#xff0c;都是一种平衡二叉搜索树#xff0c;但是AVL树的平衡要求太严格#xff0c;如果要对AVL树做一些结构修改的操作性能会非常低下#xff0c;比如#xff1a;插入时要维护其绝对平衡#xff0c;旋转的次数比较多#xff0c;更…前言 AVL树与红黑树相似都是一种平衡二叉搜索树但是AVL树的平衡要求太严格如果要对AVL树做一些结构修改的操作性能会非常低下比如插入时要维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果要对一个结构经常修改AVL树就不太适合这时就需要运用对平衡要求不太严格的红黑树。 一红黑树的认识 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 红黑树确保没有一条路径会比其他路径长出俩倍的原因是由红黑树的性质决定。 红黑树的性质 1. 每个结点不是红色就是黑色。  2. 根节点是黑色的。 3. 如果一个节点是红色的则它的两个孩子结点必须是黑色的。即从上层到下层不存在连续的红节点。 4. 对于每个结点从该结点到其所有后代叶子结点的简单路径上包含此节点均包含相同数目的黑色结点即每条路径均包含相同数量的黑色节点。 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)。这里所到最终节点指的就是空节点。如上图中NIL空节点为黑色。 红黑树就是满足以上的性质才确保没有一条路径会比其他路径长出两倍。至于原因我们可来设想一下极端情况。由于任意一个节点到其所有后代叶子结点的黑色节点相同且红色节点不能连续出现所以极端情况下我们令一个节点的左边为最短路径——全部黑色高度h右边为最长路径——黑色节点之间每隔一个都有一个红色节点高度最大为2*h。这样我们得出最大路径刚好是最小路径的两倍。由此看来红黑树下任意节点的路径之差在 [h2h] 区间。 红黑树对比AVL树可得红黑树对平衡的要求不是那么严格比较宽松虽说效率逊于AVL树但是综合性能比AVL树高。而且AVL树的高度很接近 logN红黑树高度很接近 2logNlogN 的数值足够小两者之间效率基本微乎其微基本可忽略不计。 二红黑树的插入操作 2-1红黑树节点的定义 红黑树的结点定义大致跟AVL树一样唯一要不同的是红黑树中没有平衡因子只包含颜色。 //节点的颜色——这里用枚举表示 enum Color {     RED,       //红色     BLACK   //黑色 }; //红黑树节点的结构 template class K, class V struct RBTreeNode {     RBTreeNodeK, V _parent;   //双亲节点     RBTreeNodeK, V* _left;        //左孩子节点     RBTreeNodeK, V* _right;     //右孩子节点     Color _color;                             //节点颜色     pairK, V _kv;                         //节点数据     RBTreeNode(const pairK, V kv)   //为了后面插入方便这里构造为红色节点         : _parent(nullptr)         , _left(nullptr)         , _right(nullptr)         , _color(RED)             , _kv(kv)     {    } }; 2-2红黑树的插入操作 红黑树的插入跟AVL树一样都是在二叉搜索树的基础上加上了平衡限制因此可分为两步1按照二叉搜索树的规则进行插入。2检测插入后的红黑树是否造到平衡破坏若平衡被破坏这里要进行旋转或变色由于这里的平衡是根据颜色来控制的插入后若平衡别破坏颜色管理一定失调但插入后颜色失调不一定会导致平衡破坏这里可想象一下当平衡满足AVL平衡时插入的场景。 红黑树由于要满足左右所有路径上的黑色节点相同若插入黑色节点会引发上面一系列结构问题和不平衡现象因此这里最好插入红色节点。 首先我们先来考虑什么情况下插入新节点后不会发生旋转和变色。这里很显然若我们在黑色节点后面插入新节点红色节点是不会影响颜色管理至于是否影响平衡还要看极端情况。在极端情况下插入发生平衡失调这绝对不会插入在黑色节点后面。因此若插入新节点在黑色节点后面我们可放任不管。 若我们插入的新节点cur在红色节点后面此时的红色结点必然无孩子且一定要进行变色恢复红黑树颜色规则还可能要进行旋转恢复红黑树平衡规则因为若此时红色结点存在一个孩子那么这个孩子必然是黑色的这样一来就违背了红黑树的左右路径黑色结点数量相同的性质。此情况下因为cur的双亲结点是红色的所以必然会存在黑色的爷爷结点所以这里的情况可分为三类谈论1存在cur的叔叔节点双亲结点的兄弟结点且为红。2不存在cur的叔叔结点。3存在cur的叔叔结点且为黑。其中情况二和情况三在代码实现中可分为一种情况具体原因下面会说明。 情况一存在cur的叔叔节点u且为红 我们来看新插入结点cur的叔叔结点为红色时的情况。根据已有条件可知cur的双亲结点parent简写p为红色那么cur的爷爷结点grandparent简写g必为黑色叔叔结点uncle简写u为红色。如下图 我们先来观察a结构。这里先只看以p为根节点的子树由于p为红色且插入cur之前p的左边路径为1所以a要么为空要么只有一个黑色结点。当为黑色结点时左右路径的黑色结点数量不相等所以a只能为空。b和c同理只看以g为根节点的子树结构b和c不能为黑色但b和c为红色这里也不能为红色所以只能为空。如下 这种情况下是否需进行旋转暂不明确但显然违反了颜色规则——红色结点之间相连需进行颜色变换。颜色变色这块需明白当一个结点变色后是不会影响此节点的下层颜色规则只会影响上面结构。因此这里变色规则是p和u变黑色g变红色控制原本黑色结点的数量不变保证上层结构。如果g是根节点再将其变黑色然后结束操作如果g不是根节点需要继续往上查看因为这里虽说满足黑色结点数量的规则但是g变成了红色g的双亲结点可能为红色或黑色。当g的双亲结点为黑色时颜色变色后满足规则可直接结束当g的双亲结点为红色时这里就要将重复操作即将cur g继续排查直到遇到p为黑色或cur为根节点为止。注意这里往上排查过程中也可能遇到情况2u结点不存在或情况3u结点存在且为黑色这里先提前说一下其实排查过程中不可能遇到情况2至于原因和遇到情况3下面会详细说明。 这里有两个问题。1p结点和g结点是否存在即是否为空。2平衡是否被破坏即是否需要进行旋转。 问题一 p结点可能为空此时cur结点为根节点对照上面cur为根节点直接处理情况若在刚开始p为空此时新插入结点cur为根节点插入后直接返回即可。 g结点这里一定不为空因为当g结点为空时p结点就是根节点p结点一定为黑色。我们使用g结点的前提条件是p结点为红色若p是黑色直接退出根本就没有g结点这一环节。 问题二 这种条件下平衡一定不会被破坏。插入新节点后平衡被破坏的前提是插入前结构必为极端情况而在极端情况下cur必有叔叔结点u且为黑或无叔叔结点u。因此此种情况只需变色无需旋转。从这可说明发生旋转和变色的只有cur存在叔叔结点u且为黑色或无叔叔结点u。 注意在情况一下又可划分为四种情况如下 1p是g的左孩子u是g的右孩子新插入结点cur是p的左孩子。如上图 2p是g的左孩子u是g的右孩子新插入结点cur是p的右孩子。 3p是g的右孩子u是g的左孩子新插入结点cur是p的左孩子。 4p是g的右孩子u是g的左孩子新插入结点cur是p的右孩子。 这里划分的四种情况都可看成一种情况因为这里只需变色无需旋转针对的目标是p、u、g三结点的颜色至于谁是左孩子谁是右孩子根本不理会。       情况二不存在cur的叔叔结点u 当不存在叔叔结点u时插入新节点cur时显然违反了平衡规则——左右最大高度与最小高度不满足二倍关系至于怎么旋转我们从AVL树中可知需看cur、p的具体位置前文中已有AVL树旋转的详细讲解以及原理若这里不明白的请看前文AVL树讲解然而这里存在四种小情景         1p是g的左孩子新插入结点cur是p的左孩子。p一定没有右孩子因为p为红色且插入前无左孩子。此种情景跟AVL树中插入在g的左子树的左侧相似进行右单旋旋转后还要变色。为了保证这里黑色结点数量不变保证上层结构且在此子树下的左右路径黑色结点数量相同保证本层子树结构即最底层结构需将g变为红色p变为黑色如下图 2p是g的左孩子新插入结点cur是p的右孩子。p一定没有左孩子因为p为红色且插入前无右孩子。此种情景跟AVL树中插入在g的左子树的右侧相似进行左右旋旋转后也要变色。这里的变色规则跟上面一样即将g变为红色cur变为黑色如下图 3p是g的右孩子新插入结点cur是p的左孩子。与上同理这里p一定无右孩子。此种情景跟AVL树中插入在g的右子树的左侧相似进行右左旋旋转后也要变色。这里的变色规则跟上面一样即将g变为红色cur变为黑色。 4p是g的右孩子新插入结点cur是p的右孩子。与上同理p一定无左孩子。此种情景跟AVL树中插入在g的右子树的右侧相似进行左单旋旋转后还要变色需将g变为红色p变为黑色。 当出现此种情况时cur绝不可能是往上排查中的情况必定为新插入结点因为在这种情况下以g为根节点的子树左右路径之差根本不满足红黑树的性质例如以上面情景四为例当cur不是新插入的结点时g的左边高度固定为1右边高度大于3。 这里当发生这种情况时旋转变色后可直接退出因为无论出现以上哪四种场景旋转后都将恢复原本平衡变色后在g位置的结点都为黑色根本不影响上层结点情况或g为根节点情况。 情况三存在cur的叔叔结点且为黑 首先我们先来观察cur为新插入结点时遇到此情况的时候。 我们来分析以上情况这里叔叔结点u为黑色根据红黑树性质这里以g为根节点的子树中a结构必须有一个黑色结点但在插入前图中p没有左孩子这里以p为根节点的子树中情景跟上面一样a结构必须为空与上形成矛盾因此cur为新插入结点的情况根本不可能出现也就是说cur的叔叔结点为黑色的情况下只能是cur不为新插入的结点即情况一中往上排查中遇到的情况遇到情况二一步操作后直接退回。     从情况一中的问题二可知发生旋转和变色的情况只有在cur必有叔叔结点u且为黑色或无叔叔结点u的条件下其中无叔叔结点只能是在刚插入时的情况而此情况只能在上层中遇到但注意当遇到此种情况时还不能说明平衡一定被破坏即平衡可能被破坏也可能没有被破坏。为了方便起见这里处理的方式是无论平衡是否被破坏都进行旋转处理因为旋转调节后我们严格遵守红黑树的颜色管理也就间接不会破坏平衡而且旋转的本质是将高度大的一方减一高度小的一方加一此种情况又是在上层结构中遇到的当平衡时旋转调节后一定不会破坏这里的平衡。当平衡被破坏时路径最长的是2*h1新插入结点的一方路径最短的是h旋转之后路径最长的变为2h路径最短的变为h1满足条件。 旋转之前我们来分析已确定的条件。首先这里叔叔既然存在且为黑那么必然存在g结点。其次这里的cur结点是情况一中往上排查时上一次的g结点——原本是黑色的现在变成红色的相当于又一次检验因此cur是红色的那么p结点也是红色的如果p是黑色的在情况一中就直接退出了根本不会进行到下一轮且就算叔叔结点u是黑色的但若双亲结点p是黑色的根本不可能出现不平衡现象即颜色失调现象。最后由于p是红色的那么g是黑色的。总的来说当发生这种情况时就已确定g结点和u结点是黑色的p结点和cur结点是红色的。 此种情况跟情况二相似对应的也有四种不同位置的场景由于需要进行旋转所以这里都要进行讨论。 1cur是p的左孩子p是g的左孩子u是g的右孩子。 这里我们要明白是左右中的哪里高度出现了问题需在哪里进行旋转。上面说过存在叔叔节点u且为黑时进行旋转必然是插入前已处于极端情况下此处高度大的一方就是cur的一方因此此场景的旋转类似于AVL树中插入在g的左子树的左侧进行右单旋。旋转后这里违背了颜色分配规则具体的变化规则必须要依据插入前的原结构。插入前a、b、c、d、e结构尚未可知但除去a、b、c、d、e结构外g结点位置的左边无黑色结点右边有一个黑色结点g位置上是黑色结点防止上面的双亲结点除了这里已知结点外还要注意a、b、c、d、e结构中头节点的颜色为了周全这里最好全部都看成不为空时的情况即a、b、c的头节点必定为黑d、e未知因此这里需注意d、e为红的情况——若为红色它们的双亲必须是黑色若为黑色它们的双亲可随意。旋转后必须也要满足此条件和以上注意情况否则颜色分配这里可能就会出问题因此这里颜色的变化是将p变为黑色g变为红色如下图。 2cur是p的右孩子p是g的左孩子u是g的右孩子。 这里高度大的一方还是cur的一方原因与上一样。此时场景如同AVL树中插入在g的左子树的右侧旋转的方式是左右旋——先左旋后右旋。颜色变化更上面场景原理一样除去a、b、c、d、e结构g位置的右边有一个黑色结点g位置的左边没有黑色结点g位置上是一个黑色结点为了防止g位置的双亲结点。这里还是将a、b、c、d、e子树结构看成都不为空时的情况其中a、b、c的根节点必是黑色的d、e的根节点可能是红色的因此这里旋转后连接d、e的结点必须也是黑色的。具体的颜色变化是将cur变成黑色g变成红色如下图 3cur是p的左孩子p是g的右孩子u是g的左孩子。 这里cur高度超出范围与上一样。此时的旋转跟AVL树中插入在g的右子树的左侧时进行的旋转一样——进行左右旋先左单旋后右单旋。旋转后颜色的变化逻辑思想与上相同g位置上是黑色结点g位置左边有一个黑色结点g位置右边没有黑色结点且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此这里的颜色变色规则是g变成红色cur变成黑色如下图 4cur是p的右孩子p是g的右孩子u是g的左孩子。 这里cur高度超出范围与上一样。此时的旋转跟AVL树中插入在g的右子树的右侧时进行的旋转一样——进行左单旋。旋转后颜色的变化逻辑思想与上相同g位置上是黑色结点g位置左边有一个黑色结点g位置右边没有黑色结点且d、e子树结构的根节点可能是红色的。变色后应满足以上规则且连接d、e子树结构的结点必须是黑色的。因此这里的颜色变色规则是g变成红色p变成黑色如下图 这里不难发现处于这种情况下的无论哪种场景叔叔结点u以及叔叔结点u下层的结构不做任何改变至于p和cur下层的结构若不为空根节点必为黑色这里完全不影响上面结点的颜色。仔细思考可发现这里发生的旋转和不同场景下颜色的改变跟情况二中无叔叔结点时一摸一样—即g结点的位置是黑色的且满足颜色分配旋转变色后可直接退出可归为一类。 代码实现    总上所述这里红黑树的插入操作逻辑大致是这样当插入结点的双亲结点是黑色的不做任何处理当插入结点的双亲结点是红色的这时分两种情况来判断1存在叔叔结点且为红。2存在叔叔结点且为黑或不存在叔叔结点。当存在叔叔结点且为红这种情况只用于变色并向上做出排查直到排查到根节点当不存在叔叔结点或存在叔叔结点且为黑直接进行旋转并变色后退出。由于情况一需要对叔叔结点进行变色而情况二需要确定叔叔结点的位置以便确定哪种旋转所以这里可再分两种小情况进行讨论——叔叔结点u是g的左孩子或叔叔结点u是g的右孩子。于情况一而言这里只用变色无需注意其它结点位置于情况二而言由于需要旋转只确定p和u的位置还不够还需确定cur的具体位置。代码如下 bool Insert(const pairK, V kv) {     //1插入节点     if (_root nullptr)     {         _root new Node(kv);         _root-_color BLACK;         return true;     }     Node cur _root;     Node* parent _root-_parent;     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;         }     }     if (parent-_kv.first kv.first)     {         parent-_left new Node(kv);         cur parent-_left;     }     else     {         parent-_right new Node(kv);         cur parent-_right;     }     cur-_parent parent;     //2旋转或变色    //只用处理插入结点cur的双亲结点是红色时的情况要注意cur是根节点的情况     while (parent parent-_color RED)      {         //存在parent且parent是红色时由于根节点是黑所以一定存在它的双亲结点         Node* grandparent parent-_parent;        //cur双亲结点parent在左叔叔结点uncle在右         if (parent grandparent-_left)         {             Node* uncle grandparent-_right;             //情况一: 存在叔叔结点且为红             //这种情况平衡不会被破坏不用关心结点的具体位置只需变色             if (uncle uncle-_color RED)             {                 //变色                 grandparent-_color RED;                 parent-_color uncle-_color BLACK;                 //往上排查                 cur grandparent;                 parent cur-_parent;             }            //情况二: 存在叔叔结点且为黑或不存在叔叔结点             else              {                 //情景一: p是g的左孩子u是g的右孩子cur是p的左孩子                 if (cur parent-_left)                 {                     //旋转                     RotateR(grandparent);                     //变色                     grandparent-_color RED;                     parent-_color BLACK;                 }                 //情景二: p是g的左孩子u是g的右孩子cur是p的右孩子                 else                 {                     //旋转                     RotateLR(grandparent);                     //变色                     grandparent-_color RED;                     cur-_color BLACK;                 }                 break;//旋转变色后直接退出             }         }        //cur双亲结点parent在右叔叔结点uncle在左         else         {             Node* uncle grandparent-_left;             //情况一: 存在叔叔结点且为红             //情况以上一样这里只需变色无需旋转             //这里之所以不能单独列出来是因为叔叔结点不确定是否存在             if (uncle uncle-_color RED)             {                 //变色                 grandparent-_color RED;                 parent-_color uncle-_color BLACK;                 //继续往上排查                 cur grandparent;                 parent cur-_parent;             }             //情况二: 存在叔叔结点且为黑或不存在叔叔结点             else              {                 //情景三: p是g的右孩子u是g的左孩子cur是p的左孩子                 if (cur parent-_left)                 {                     //旋转                     RotateRL(grandparent);                     //变色                     grandparent-_color RED;                     cur-_color BLACK;                 }                 //情景四: p是g的右孩子u是g的左孩子cur是p的右孩子                 else                 {                     //旋转                     RotateL(grandparent);                     //变色                     grandparent-_color RED;                     parent-_color BLACK;                 }                 break;//旋转变色后直接退出             }         }     }    //直接暴力解决cur为根节点情况     _root-_color BLACK;     return true; } //旋转算法 void RotateL(Node* parent) //左单旋 {     Node* cur parent-_right;     Node* curL cur-_left;     Node* pparent parent-_parent;     //旋转     parent-_right curL;     if (curL)         curL-_parent parent;     //更新节点     if (parent _root)     {         _root cur;         _root-_parent nullptr;     }     else     {         if (pparent-_left parent)         {             pparent-_left cur;             cur-_parent pparent;         }         else         {             pparent-_right cur;             cur-_parent pparent;         }     }     //旋转     cur-_left parent;     parent-_parent cur; } void RotateR(Node* parent) //右单旋 {     Node* cur parent-_left;     Node* curR cur-_right;     Node* pparent parent-_parent;     //旋转     parent-_left curR;     if (curR)         curR-_parent parent;     //更新节点     if (parent _root)     {         _root cur;         _root-_parent nullptr;     }     else     {         if (pparent-_left parent)         {             pparent-_left cur;             cur-_parent pparent;         }         else         {             pparent-_right cur;             cur-_parent pparent;         }     }     //旋转     cur-_right parent;     parent-_parent cur; } void RotateLR(Node* parent) //左右旋 {    //先左再右两次旋转     RotateL(parent-_left);     RotateR(parent); } void RotateRL(Node* parent) //右左旋 {    //先右再左两次旋转     RotateR(parent-_right);     RotateL(parent); } 2-3红黑树的验证 红黑树的验证不能根据红黑树的特点判断即不能根据最长路径不超过最短路径的二倍来判断。红黑树之所以路径会满足此特点是由红黑树的性质决定的但反过来满足路径关系却不一定满足红黑树的性质所以这里要根据红黑树的性质进行验证。 红黑树的检测分为两步1. 检测其是否满足二叉搜索树(中序遍历是否为有序序列) 2. 检测其是否满足红黑树的性质。 这里重点说明第二步。红黑树的性质验证的核心检查有三点1根节点是黑色的。2没有连续的红色结点。3每条路径的黑色结点的数量相等。 第一点代码很好实现不做过多说明。第二点直接使用前序遍历整个树当遍历到此时结点为红色时查看它的双亲结点若双亲结点也是红色的验证失败。第三点方法有很多这里可先从树的根节点选任意一个路径记录此路径黑色结点的数量作为标杆然后不断前序遍历所有路径若有任意一个路径的黑色结点数量与之不同那么遍历失败。原因很简单树的所有路径都可看成从根节点开始的路径的子路径只要我们在每个结点到叶子结点路径上遇到黑色结点的数量加上上面从根节点开始到此路径的黑色结点数就如同从根节点开始的一条路径黑色结点数即任意一个结点这里是根节点到后代所有路径的黑色结点数比较。 //核心检查三步:1根节点是黑色的。2没有连续的红色结点。3每条路径的黑色结点的数量相等。 bool IsBalance() {     //核心检查1—根节点是黑色的     if (_root _root-_color RED)         return false;     //核心检查3—每条路径的黑色结点的数量相等     Node* cur _root;    //检查3中先检查红黑树的左子树黑色结点总共的个数即标杆     size_t sign 0;     while (cur)     {         if (cur-_color BLACK)             sign;         cur cur-_left;     }     return Check(_root, 0, sign); } bool Check(const Node* root, size_t blacknum, size_t sign) {    //一条路径结束开始判断黑色结点数量是否相同     if (!root)     {         if (blacknum ! sign)             return false;         return true;     }     //核心检查2—没有连续的红色结点     Node* parent root-_parent;     if (root-_color RED parent-_color RED) //root结点是红色时一定不是根节点         return false;    //检查3中然后以标杆做依据遍历每个路径的黑色结点也之是否相同     if (root-_color BLACK)         blacknum;     return Check(root-_left, blacknum, sign) Check(root-_right, blacknum, sign); }