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

目录

数据结构图-树

简介

规则

旋转

重新着色

红黑树构建过程

---

前言-与正文无关

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

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

数据结构图-树

简介

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

规则

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

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

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

旋转

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

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

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

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

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

重新着色

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

红黑树构建过程