温州网站设计定制,seo新人怎么发外链,健康网站建设与管理,邢台地区网站建设口碑好目录
数据结构图-树
简介
规则
旋转
重新着色
红黑树构建过程 前言-与正文无关 生活远不止眼前的苦劳与奔波#xff0c;它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中#xff0c;我们往往容易陷入工作的漩涡#xff0c;忘记了停下脚步#xf…目录
数据结构图-树
简介
规则
旋转
重新着色
红黑树构建过程 前言-与正文无关 生活远不止眼前的苦劳与奔波它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中我们往往容易陷入工作的漩涡忘记了停下脚步感受周围的世界。让我们一起提醒自己要适时放慢脚步欣赏生活中的每一道风景享受与家人朋友的温馨时光发现那些平凡日子里隐藏的幸福时刻。因为这些点点滴滴汇聚起来的才是构成我们丰富多彩生活的本质。希望每个人都能在繁忙的生活中找到自己的快乐之源不仅仅为了生存而工作更为了更好的生活而生活。 送你张美图希望你开心 数据结构图-树 简介
红黑树是一种自平衡的二叉搜索树。在二叉搜索树中树中的每个节点都有一个键值且每个节点的键值都大于其左子树中任何节点的键值并小于其右子树中任何节点的键值。红黑树增加了一些额外的属性来确保树保持平衡这样任何时间的查找、插入和删除操作的最坏情况时间复杂度都保持在 O(log n)。 规则
红黑树必须遵循以下属性
节点颜色: 每个节点要么是黑色要么是红色。根节点: 树的根节点是黑色的。最底层每个叶子节点NIL节点空节点是黑色的。红色节点规则: 如果一个节点是红色的则其子节点必须是黑色的即不允许连续的红色节点。黑色高度: 从任一节点到其任何叶子节点的所有路径上的黑色节点数量相同平衡的关键 新插入的节点为红色: 新插入节点默认为红色插入后需要校验红黑树是否符合规则不符合则需要进行平衡 为了维持这些属性红黑树在插入新节点或删除节点后会通过旋转和重新着色来进行调整。
旋转
旋转: 当插入或删除节点导致红黑树的性质被破坏时可以通过旋转来重新平衡树。旋转有两种
左旋: 节点的右子节点上升到其位置而原节点变成了这个右子节点的左子节点。 左旋操作将节点 Y旋转到节点 X 的位置而节点 X 成为了 Y的左子节点。重要的是要注意a节点比X小成为x左节点c同理还是在Y右边因为比Y大。b因为他是比Y小按照规则他应该是在半边又因为他比x大所以在x右下面这样左旋操作不会违反二叉搜索树的性质。
右旋: 节点的左子节点上升到其位置而原节点变成了这个左子节点的右子节点。
右旋我就不细说了和左旋类似看左旋你应该就明白了 重新着色
如果节点的颜色导致红黑树性质被破坏特别是连续红色节点的问题则可以通过改变某些节点的颜色来修复。 就是当前节点与父节点、叔叔节点同为红色这种情况违反了红黑树的规则3需要将红色向祖辈上传 父节点和叔叔节点红色变为黑色爷爷节点从黑色变为红色顶级爷爷节点必为黑色这里是做演示可以理解现在顶级祖宗还是黑的。这样每条叶子结点到根节点的黑色节点数量并未发生变化。 红黑树构建过程 新插入节点默认为红色510 插入到左子节点插入后左子树深度为 2 叶子节点黑色【只是上图没画出来根据规则2】 根节点 黑色右子树深度为也是2 叶子节点黑色 根节点黑色满足红黑树规则。 新插入节点为红色910 需要在左子树进行插入再和 5 比较大于 5 放到 5 的右子树中此时各个叶子节点到根节点的深度依然是2 但 5 和 9 两个节点都是红色不满足规则第 4 条需要进 行左旋、右旋操作使其符合规则。可以看出经过操作后左右子树又维持了平衡。 下面不想看可以没必要看其实还是上面那些再多讲些罢了 插入节点3 后可以看到又不符合红黑树的规则了而此时的情况需要采用颜色反转的操作就 是把5 、 10 两个节点变为黑色 5 、 10 的父节点变为红色但父节点 9 是根节点不能为红色于是再将 9 变为黑色这样整个树的深度其实增加了1 层。 继续插入6 节点对树深度没有影响。 插入7 节点后 6 、 7 节点都为红节点不满足规则 4 需要进行颜色反转调整也就是 7 的父节点和叔叔节点变为黑色爷爷节点5 变为红色 继续插入节点19 对树深度没有影响红黑树的规则都满足无需调整。 插入节点32 后又出现了不满足规则 4 的情况此时节点 32 没有叔叔节点如果颜色反转的话左右子树的深度就出现不一致的情况所以需要对爷爷节点进行左旋操作。 父节点取代爷爷节点的位置父节点变为黑色爷爷节点变为父节点的左子树变为红色 插入节点24 后红黑树不满足规则 4 需要调整。 此时父节点32 和叔叔节点 10 都为红色需要进行颜色反转爷爷节点 19 变为红色父节点、叔叔 节点变为黑色颜色反转树的深度不发生变化。 ------------------------------------------与正文内容无关------------------------------------ 如果觉的文章写对各位读者老爷们有帮助的话麻烦点赞加关注呗作者在这拜谢了! 混口饭吃了如果你需要Java 、Python毕设、商务合作、技术交流、就业指导、技术支持度过试用期。请在关注私信我本人看到一定马上回复 这是我全部文章所在目录看看是否有你需要的如果遇到觉得不对地方请留言看到后我会查阅进行改正。 A乐神-CSDN博客
