大型服装商城网站建设,常州建站服务,分销系统平台有哪些,东莞企业网站建设价格本文就红黑树的插入操作进行细致到每一个小步骤的解析。1#xff0c;成员变量本红黑树使用了三叉链结构#xff0c;使用的时候尤其要记得处理指向父亲的指针。为何在节点的构造函数中#xff0c;默认节点的颜色为红色#xff1f;因为考虑到红黑树的性质#xff08;对于每个…本文就红黑树的插入操作进行细致到每一个小步骤的解析。1成员变量本红黑树使用了三叉链结构使用的时候尤其要记得处理指向父亲的指针。为何在节点的构造函数中默认节点的颜色为红色因为考虑到红黑树的性质对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点所以设置为红色是最为合理方便的如果插入的时候会有连续的红色节点再做调整也很方便。但是如果默认为黑节点就要做调整保证每个路径上的黑节点相同相比之下会很麻烦。2Insert函数的实现分为各个细节讨论2,1插入时红黑树是否为空树考虑到此情况要先判断红黑树是否为空树。若是进行相关操作后return若不是向下进行2,2若不是空树迭代到树的底部并插入节点不必担心parent的空指针解引用问题由于不是空树所以parent一定不会为nullptr。2,3插入节点后控制平衡理论基础理论我们先约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点情况一 cur为红p为红g为黑u存在且为红如下图此图是个抽象图代表着多种情况带省略号的长方形表示一个未知的树。解决方法将p,u改为黑g改为红然后把g当成cur继续向上调整如果g是根节点调整完成后需要将g改为黑色其实只要在调整操作的最后将_root的颜色置为黑色就行不必在每种情况下特殊处理如果g是子树g一定有双亲且g的双亲如果是红色需要继续向上调整。——————————————————————————————————————情况二 cur为红p为红g为黑u不存在/u存在且为黑且为单旋情况如下图如下图解决方法p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转p、g变色--p变黑g变红旋转函数1左单旋解释要实现一个操作往往有多种方法函数的设计也有多种。本人选择将旋转函数参数统一设置为要处理的两个节点中处于上方的节点。如图于是写出代码实现如下cur是node的右子节点parent是node的父节点。要特别注意此时使用的是三叉链结构在链接节点的同时一定不要忘记对_parent进行处理在对_parent进行处理时当然也要注意_parenrt是否存在所以我们还要判断node是否为根节点再进行相关操作。2右单旋分析同上不在赘述。如下图代码实现————————————————————————————————————————在插播了左单旋和右单旋的实现后继续回来讨论第三种情况情况三cur为红p为红g为黑u不存在/u存在且为黑且需要双旋有了以上基础此处直接上图。解决方法p为g的左孩子cur为p的右孩子则针对p做左单旋转再对g做右单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转再对g做左单旋转。将cur置为黑色g置为红色代码实现复用左单旋和右单旋即可。代码实现解释整个循环结束的条件是parent不存在或者parent为黑色并且不必担心祖父是否存在因为如果parent parent-_col RED的话祖父节点一定存在并且为黑色因为parent为红色节点不可能是根节点。如果是第一种情况的话是需要迭代调整的要将g的位置变为cur继续向上检查。而第二三种情况则不需要因为旋转了之后没有对上层产生影响所以可以在调整之后直接跳出循环结束后将_root置为黑色保证结构即可。
