Java 数据结构 二叉树（二）红黑树

目录

数据结构图-树

简介

规则

旋转

重新着色

红黑树构建过程

---

前言-与正文无关

        生活远不止眼前的苦劳与奔波，它还充满了无数值得我们去体验和珍惜的美好事物。在这个快节奏的世界中，我们往往容易陷入工作的漩涡，忘记了停下脚步，感受周围的世界。让我们一起提醒自己，要适时放慢脚步，欣赏生活中的每一道风景，享受与家人朋友的温馨时光，发现那些平凡日子里隐藏的幸福时刻。因为，这些点点滴滴汇聚起来的，才是构成我们丰富多彩生活的本质。希望每个人都能在繁忙的生活中找到自己的快乐之源，不仅仅为了生存而工作，更为了更好的生活而生活。

        送你张美图！希望你开心！

数据结构图-树

简介

红黑树是一种自平衡的二叉搜索树。在二叉搜索树中，树中的每个节点都有一个键值，且每个节点的键值都大于其左子树中任何节点的键值，并小于其右子树中任何节点的键值。红黑树增加了一些额外的属性来确保树保持平衡，这样任何时间的查找、插入和删除操作的最坏情况时间复杂度都保持在 O(log n)。

规则

红黑树必须遵循以下属性：

1. 节点颜色: 每个节点要么是黑色，要么是红色。
2. 根节点: 树的根节点是黑色的。最底层每个叶子节点（NIL节点，空节点）是黑色的。
3. 红色节点规则: 如果一个节点是红色的，则其子节点必须是黑色的（即不允许连续的红色节点）。
4. 黑色高度: 从任一节点到其任何叶子节点的所有路径上的黑色节点数量相同（平衡的关键） 
5. 新插入的节点为红色: 新插入节点默认为红色，插入后需要校验红黑树是否符合规则，不符合则需要进行平衡

为了维持这些属性，红黑树在插入新节点或删除节点后会通过旋转和重新着色来进行调整。

旋转

旋转: 当插入或删除节点导致红黑树的性质被破坏时，可以通过旋转来重新平衡树。旋转有两种：

• 左旋: 节点的右子节点上升到其位置，而原节点变成了这个右子节点的左子节点。

左旋操作将节点 Y旋转到节点 X 的位置，而节点 X 成为了 Y的左子节点。重要的是要注意，a节点比X小，成为x左节点，c同理还是在Y右边因为比Y大。b因为他是比Y小，按照规则他应该是在半边，又因为他比x大，所以在x右下面，这样左旋操作不会违反二叉搜索树的性质。

• 右旋: 节点的左子节点上升到其位置，而原节点变成了这个左子节点的右子节点。

右旋我就不细说了，和左旋类似，看左旋你应该就明白了

重新着色

如果节点的颜色导致红黑树性质被破坏（特别是连续红色节点的问题），则可以通过改变某些节点的颜色来修复。

就是当前节点与父节点、叔叔节点同为红色，这种情况违反了红黑树的规则3，需要将红色向祖辈上传， 父节点和叔叔节点红色变为黑色，爷爷节点从黑色变为红色（顶级爷爷节点必为黑色，这里是做演示，可以理解现在顶级祖宗还是黑的）。这样每条叶子结点到根节点的黑色节点数量并未发生变化。

红黑树构建过程

 

        新插入节点默认为红色，5<10 ，插入到左子节点，插入后左子树深度为 2 （叶子节点黑色【只是上图没画出来，根据规则2】 + 根节点 黑色），右子树深度为也是2 （叶子节点黑色 + 根节点黑色），满足红黑树规则。

        新插入节点为红色，9<10 ，需要在左子树进行插入，再和 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博客