做电气设计有哪些好的网站,织梦网站怎么加入引导页,中国建设行业峰会网站,服务行业网站建设一、红黑树的概念
红黑树是一种二叉搜索树#xff0c;但在每个节点上增加一个存储位表示节点的颜色#xff0c;可以是Red或者BLACK#xff0c;通过对任何一条从根到叶子的路径上各个节点着色方式的限制#xff0c;红黑树确保没有一条路径会比其他路径长出两倍#xff0c;…一、红黑树的概念
红黑树是一种二叉搜索树但在每个节点上增加一个存储位表示节点的颜色可以是Red或者BLACK通过对任何一条从根到叶子的路径上各个节点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因为是接近平衡的。
二、红黑树的性质
·1、每个结点不是红色就是黑色
2、根节点是黑色的
3、如果一个节点是红色的则它的两个孩子节点必须是黑色的。
4、对于每个节点从该节点到其所有后代节点的简单路径上均包含相同的黑色节点每条路径上黑色节点的数量相等根到空节点算一条路径。
5、NIL节点是黑色的 三、怎么做到最长路径不超过最短路径的二倍
根是黑色的NIL是黑色的如果一个节点是红色的那么它的左右孩子都是黑色不同的路径上有相同数量的黑色节点。上面的条件就可以推出最长路径不超过最短路径的两倍。
四、为什么红黑树更优于AVL树。
因为旋转的次数少了。
五、红黑树的插入
再插入的时候我们插入的是红节点如果插入黑色节点就会违背各个路径上的黑色节点是相等的。如果插入红色节点我们可能会违背一个节点是红色的它的左右孩子都是黑色的条件。当父亲是黑色的时候插入红色节点没有违背任何的条件如果当父亲是红色的时候就违背了一个节点是红色的它的左右孩子都是黑色的条件。对于这个情况我们需要分类讨论。红黑树也是一棵不太平衡的平衡二叉树。
情况一
叔叔存在且为红
情况1红黑树我们看的是uncle节点父亲和叔叔变黑grandfather变红 。那么局部的子树里面红黑节点的数量不变且连续的红节点问题暂时解决了。
继续向上处理
1、grandfather没有父亲就是根把grandfather变黑即可。
2、grandfather有父亲且为黑结束。
3、grandfather有父亲且为红和刚才是类似问题处理把grandfather当成插入节点按情况1进行处理。
情况二
叔叔不存在
如果叔叔不存在旋转加变色。
情况三
叔叔存在且为黑
旋转变色
总结
红黑树插入关键看叔叔。
1、叔叔存在且为红变色向上处理
2、叔叔不存在或者叔叔为黑色变色旋转。旋转需要进行根据位置来判断。grandfather-left parent ,parent-left cur
右旋父亲变黑祖父为红不需要再往上一层处理。
先左后右双旋cur为黑grandfather为红
