专业网站定制平台,wordpress文章页打赏,wordpress 魔板,实体店100个营销策略目录 这个性质可以总结为
红黑树的最短最长路径
红黑树的路径范围
code
结构
搞颜色
类
插入
插入逻辑
新插入节点
思考#xff1a;2. 检测新节点插入后#xff0c;红黑树的性质是否造到破坏#xff1f;
解决方法
变色
旋转变色
第三种情况#xff0c;如果根…目录 这个性质可以总结为
红黑树的最短最长路径
红黑树的路径范围
code
结构
搞颜色
类
插入
插入逻辑
新插入节点
思考2. 检测新节点插入后红黑树的性质是否造到破坏
解决方法
变色
旋转变色
第三种情况如果根节点上面还有节点 这个性质可以总结为
1.每个节点不是红色就是黑色
2.根节点是黑色的
3.不能有两个连续的红色节点 即可以出现 红黑 黑黑 不能出现红红
4.每条路径上的黑色机节点数量不一样
至于性质5:每个叶子结点都是黑色的这里的叶子节点并不是真的叶子节点而是NIL节点即空节点。如图a NIL节点有什么作用如图a-2有多少条路径:
正确答案是有7条。路径路径的判断规则是从根节点到NULL。
如果我们把NIL节点标记出来就好找路径了 再比如图(a-3)是否是红黑树 大致一看好像是但是把NIL节点标出来之后: 路径(b)只有两个黑色节点不满足红黑树的性质不是红黑树。 红黑树的最短最长路径
那么红黑树的最短路径是什么样子的应该是全黑的最短 那最长的路径呢应该是一黑一红间隔排列的最长 根据图(a-1我们可以看出最长的路径是最短的路径的2倍。 ps
一个红黑树不一定有最长路径也不一定有最短路径。
如图a-2有最短路径没有最长路径:
红黑树的路径范围
而知道了最短路径最长路径剩下的路径都在最短路径最长路径范围内可以写为 [n,2*n]code
结构
templateclass K,class Vstruct RBTreeNode
{RBTreeNodeK,V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* parent;pairK, V;Color _col;//初始话列表RBTreeNode(const pairK, Vkv):_left(nullptr),_right(nullptr), _parent(nullptr), pairK, V,_col(RED){}
};搞颜色
enum Color
{RED,BALACK
};
类
templateclass K,class Vclass RBTree{typedef RBTreenodek,v Node;public:private:Node* _root nullptr;};
插入 插入逻辑
如果节点为空就给黑色。如果节点不为空就插入值。
这个值如果比根节点小就往左边插入否则就往右边插入。
bool Insert(const pairK, v kv){if (_root nullptr){_root new(kv);_root-_col BALACK;return true;}//初始化父亲节点和根节点Node* parent nullptr;Node* cur _root;while (cur){//key值大往右走if (cur-kv.first kv.first){cur cur-right;}//key值小往左走else if (cur-kv.first kv.first){cur -cur-left;}//否则key值和当前节点相等不插入else{return false;}}//找到了返回true1return true; }
新插入节点
思考2. 检测新节点插入后红黑树的性质是否造到破坏 如图b-1现在要插入一个节点那么是插入一个黑色节点还是红色节点呢
如果插入黑色节点那么该路径就会多一个黑色节点根据红黑树特性其他路径都要补一棵黑色节点
如果插入红色节点则只会影响父节点
即
1.如果父节点也会红节点。两个红节点不能紧挨需调整
2.如果父亲节点是黑色则不需调整直接插入。。 我们看一下怎么调整如图b-2新插入了一个红色节点7 解决方法
能变色先变色变色完之后还不行再旋转
变色
如图(b-3)先把父节点8变黑 这个时候该路径就多了一个黑色节点再变图(b-4把6节点变红
这个时候该路径又少了个黑色节点再变图b-5 把5节点变黑 旋转变色
第二种情况例如图(b-6如果还是把父节点变为黑色把6节点变为红色那么其他路径就会多一个黑色节点。
而该路径又没有其他节点可以再变黑色来平衡这种状态所以靠变色解决不了这个问题。
这个时候就要旋转了。
先右旋为图c-1
再左旋为图c-2:
然后再变色为图(c-4 情况一: cur为红p为红g为黑u存在且为红
解决叔叔存在 变色 如图(d-0)新插入了一个节点cur: cur为红色节点那就需要调整。
把p节点变为黑色节点那么u节点也要变为黑色节点那么此时就要把g节点变为红色节点。也就是图(d-1):
为什么要把g节点变为红色节点呢
假设g节点不变为红色也就是图d-3: 由图(d-1变为图(d-3我们发现每条路径凭空多了1个黑色节点。 g节点上面还有节点那么多了个黑色节点就会影响上面的路径所以需要把g节点变红来平衡一下。
如图(d-1
这个时候万一g节点的父节点是红色节点如图(d-4两个红色节点不能连续还要调整如果g节点的父亲节点为黑色如图(d-5那就不需要再调整: 新增节点给红色
cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){paret-_right cur;cur-_parent parent;}else if (_parent-_kv.first kv.first){parent-_left cur;cur-_parent parent;}
父亲节点是红色就调整是黑色就不用调整: while (parent-_col RED){}
父亲节点可能在左边(e-1)也可能在右边(e-2)但是不论父亲节点在左在右父亲节点的父亲父亲节点肯定是granparent节点。
先说图(e-1的情况即父亲节点在左
按照之前的推演应该先把父亲节点和叔叔节点变为黑色然后为了防止影响了上面的节点还要把grandparent节点变为红色
while (parent parent-_col RED) //当父亲为红色时{Node* grandparent parent-_parent;//祖父节点是父亲节点的父亲节点if (parent grandparent-_left)//第一种情况叔叔节点在右时{Node* uncle grandparent-_right;//叔叔节点在祖父节点的右边if (unlce unluce-_col RED){uncle-_col parent-_col BLACK;//叔叔节点的颜色要变成黑色grandparent-_col RED;//祖父节为了平衡要把父亲节的颜色变为红色
即变为图(d-1):
此时又有两种情况 d-4,(d-5) d-4(d-5的情况会在后续处理。
继续向上处理
这个时候把祖父节点当做当前节点让祖父节点去找它的父亲 }while (parent parent-_col RED) //当父亲为红色时{Node* grandparent parent-_parent;//祖父节点是父亲节点的父亲节点if (parent grandparent-_left)//第一种情况叔叔节点在右时{Node* uncle grandparent-_right;//叔叔节点在祖父节点的右边if (unlce unluce-_col RED){uncle-_col parent-_col BLACK;//叔叔节点的颜色要变成黑色grandparent-_col RED;//祖父节为了平衡要把父亲节的颜色变为红色//继续向上处理cur grandparent; //把祖父节点当做当前节点parent cur-parent; //祖父节点去找它的父亲}}}这个时候万一祖父节点向上不再有节点祖父节点就是最终节点怎么办
祖父节点若上面没有节点那么祖父节点就是作为根节点根节点不能为红把根节点再变黑。(r如图D-5 while (parent-_col RED){Node* grandparent parent-_parent;//祖父节点是父亲节点的父亲节点if (parent grandparent-_left)//第一种情况父亲节点是左子树叔叔节点是右子树{Node* uncle grandparent-_right;//叔叔节点在祖父节点的右边uncle-_colparent-_col BLACK;//叔叔节点的颜色要变成黑色grandparent-_col RED;//祖父节为了平衡要把父亲节的颜色变为红色}//把祖父当成当前节点继续向上处理cur grandparent;}//祖父节点向上不再有节点祖父节点作为根节点必须为黑色_root-_col BACK; 情况二: cur为红p为红g为黑u不存在/u存在且为黑
解决把祖父右旋走 让父亲做新根根就要为黑色节点再把父亲变黑
图(0-0)到(0-1为演变过程:
while (parent parent-_col RED) //当父亲为红色时{Node* grandparent parent-_parent;//祖父节点是父亲节点的父亲节点if (parent grandparent-_left)//第一种情况叔叔节点在右时{Node* uncle grandparent-_right;//叔叔节点在祖父节点的右边if (unlce unluce-_col RED){uncle-_col parent-_col BLACK;//叔叔节点的颜色要变成黑色grandparent-_col RED;//祖父节为了平衡要把父亲节的颜色变为红色//继续向上处理cur grandparent; //把祖父节点当做当前节点parent cur-parent; //祖父节点去找它的父亲}else //第二种情况叔叔节点在左边{if (cur parent-left) //当前节点在父亲节点的左边{ //单旋变色 RotateR(granparent); //旋转:把祖父右旋走让父亲做新根parent-_col BLACK; //变色:做新根就要为黑色节点grandparent-_col RED; //祖父为了平衡变红}}}}//祖父节点向上不再有节点祖父节点作为根节点必须为黑色_root-_col BLACK; 情况三p为g的左孩子cur为p的右孩子如图e-1 解决方案
Ap为g的左孩子cur为p的右孩子则针对p做左单旋转相反 Bp为g的右孩子cur为p的左孩子则针对p做右单旋转
图e-1符合(A解决方案以下是对图(e-1用(A)方案进行推演的过程 else 父亲在右边
如图f-3 while (parent parent-_col RED) //当父亲为红色时{Node* grandparent parent-_parent;//祖父节点是父亲节点的父亲节点if (parent grandparent-_left)//第一种情况叔叔节点在右时{Node* uncle grandparent-_right;//叔叔节点在祖父节点的右边if (uncle uncle-_col RED){uncle-_col parent-_col BLACK;//叔叔节点的颜色要变成黑色grandparent-_col RED;//祖父节为了平衡要把父亲节的颜色变为红色//继续向上处理cur grandparent; //把祖父节点当做当前节点parent cur-_parent; //祖父节点去找它的父亲}else //第二种情况叔叔节点在左边{if (cur parent-_left) //当前节点在父亲节点的左边{ //单旋变色 RotateR(grandparent); //旋转:把祖父右旋走让父亲做新根parent-_col BLACK; //变色:做新根就要为黑色节点grandparent-_col RED; //祖父为了平衡变红}else //当前节点在父亲节点右边{ //双旋 RotateL(parent); //父亲右旋RotateR(grandparent); //祖父右旋cur-_col BLACK; //当前节点变黑grandparent-_col RED; //祖变红}break;}}else //父亲在右边{Node* uncle grandparent-_left;//叔叔节点在祖父节点的右边if (uncle grandparent-_left) //叔叔在左边//变色if (uncle uncle-_col parent-_col RED) //if叔叔存在且颜色为红色{uncle-_col parent-_col BLACK; //叔叔父亲都变黑grandparent-_col RED; //祖父上面还有节点要变红//继续向上处理cur grandparent;}else //叔叔颜色为黑色{if (cur parent-_right) //叔叔在右边{RotateL(grandparent); //左旋爷 parent-_col BLACK;grandparent-_col RED; //祖变红}else //叔叔在左边{// g// u p// cRotateR(parent); // 父亲右旋RotateL(grandparent); //祖父旋走让cur当根cur-_col BLACK; //根变黑色grandparent-_col RED; //祖父为了平衡变红色}}}}//祖父节点向上不再有节点祖父节点作为根节点必须为黑色_root-_col BLACK;//找到了返回true1return true;
}
