数据结构和算法之树形结构(4)
文章出处：数据结构和算法之树形结构(4)
关注码农爱刷题，看更多技术文章！！！
六、红黑树(接前篇)
红黑树是为了弥补AVL树在大规模频繁增删节点场景下性能不理想而设计出来的一种平衡二叉查找树。红黑树不是一种严格的平衡树，它通过牺牲一定的平衡性来降低增删节点时自平衡旋转的执行次数，以此来满足大规模频繁增删节点场景下的性能需求。
红黑树规范
在了解红黑树是怎样通过它的自平衡机制降低旋转的执行次数从而在大规模频繁增删节点场景下获得更好性能之前，我们们先了解红黑树的相关概念和规范，红黑红黑，顾名思义，红黑树是一棵有颜色的树，非黑即红，这正是其与AVL树不同的特点：它在每个节点上增加一个存储位表示节点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍（即最长路径也不会超出最短路径的两倍，因此红黑树的平衡性要求相对宽松，没有AVL树那样严格），从而使二叉查找树达到一种相对平衡的状态即节点高度的相对平衡。具体关于红黑树的规范和特点总结如下表：
那红黑树的上述规范应该怎么理解呢？红黑树又是怎样保证二叉查找树的相对平衡的呢？其实，正是以上几条规范，特别是第4条和第5条保证了二叉查找树的相对平衡。其中第4条隐藏的含义就是，同一条路径下不能有连续的两个红色节点，而第5条规范的意思是不论是最短路径还是最长路径黑色节点数必须相同；正是这两条的限制，使最短路径和最长路径的相差不会超出两倍。这么说可能不直观，我们举例说明：假设有一起始节点为黑色，其最短路径有两个黑色子孙节点，其长度为3，对于其最长路径和最短路径差距可以有下表的推断：
从上图1-1及对应表的推断内容，不难看出正是第4、5条规范约束了最长路径的长度(至于图1-1右方红节点14、16和18下方补了黑节点也是为了让所有路径都满足规范5)，从而保证了二叉查找树高度的相对平衡，当然其他的规范也起了作用，例如规范1规定每个节点非黑即红。如果觉得这是个例，我们可以再换一个案例：把起始节点换成红色，则对于其最长路径和其最短路径可以有下表的推断：
从图1-2和上表可以看到，最长路径已经不到最短路径的两倍，换句话说，相比案例一，节点的平衡性更高。即使你在案例一基础上对最短路径增加新的黑色节点(增加红色节点，对最长路径的长度增加没有变化)，那最长路径的最多也就是增加相同数目的红色节点和黑色节点，总节点数依然在两倍以内。简单的说，规范5约定了每条路径只能有相同数目的黑节点，当黑节点数不变时，则要增加某条路径的长度或高度，则只能添加红节点，而规范4约定了同一路径红节点不能相邻连接，那在某条路径上可以增加的红节点数最多也不会超过黑节点的数目，那么最长路径自然最多也只能是最短路径的两倍。所以以上两个案例以前能充分地说明了，正是红黑树前述规范保证了其二叉查找树高度的相对平衡。
我们再仔细看看规范3和规范5，都提到了叶子节点：
规范3：叶子节点都是黑色（此处指nil节点或null节点）规范5：任意节点到达其每个叶子节点的简单路径上，黑色节点数目相同。
其中，黑色节点数目相同这个黑色节点数就包括了必须是黑色的叶子节点。那为空的黑色叶子节点到底有什么作用呢? 在前文针对图1-1和图1-2中的阐述中，没有叶子节点，规范不一样实现了对二叉查找树相对平衡的保证？我们先来看两幅图：
上图1-3是没有叶子节点的情况，从节点20到到末端节点只有两条路径，图1-4是有叶子节点的情况，从节点20到各叶子节点则有六条路径；如果没有叶子节点，我们肯定认为图1-3是有效的红黑树，满足了规范4和5的要求，因为每条路径上只有2个黑色节点，也是相对平衡的，不用再进行平衡调整；而图1-4把叶子节点画出来之后，我们可以看到节点20-25-null这条路径上只有两个黑色节点(包括叶子节点)，而其他路径上是则为3个黑色节点，所以还需要进一步进行平衡调整，即要对节点24进行右旋，处理成下图1-5的结果：
这就是有叶子节点和没有叶子节点的区别，有和没有叶子节点对后续自平衡的处理结果会不同；这里没有对错，只是有叶子节点，红黑树自平衡的处理和应用会更加方便，大家在后续实践中会明白，下面是大模型通义千问的回复：
在一些红黑树的实现中，会使用一种特殊的“叶子节点”概念来简化插入和删除操作。这些通常被称为“哨兵”节点，它们总是被设定为黑色，并且通常指向一个空值（nil 或 null）。这些哨兵节点可以被视为红黑树的外部节点，而真正的数据存储在内部节点中。这样的设计可以使得边界情况处理更加简单，因为在插入或删除时，不需要频繁地调整指针来处理原本的空指针位置。使用这些“哨兵”或“伪叶子节点”的好处包括：
1.插入或删除操作后更容易维护红黑树的性质。2.可以避免在边界情况下处理空指针，从而简化了代码逻辑。3.在进行旋转等平衡调整操作时，可以更方便地处理边界情况。
需要注意的是，并不是所有的红黑树实现都会采用这种带哨兵节点的方法；有些实现会直接处理空指针，而不是使用哨兵节点。
总之，叶子节点的引进是为了后续调整平衡更加方便。同样，规范2约定根节点必须是黑色，也是为了简化代码实现、保持树的平衡，以避免红色节点的连续出现，以及考虑到红黑树与2-3树的关系。
自平衡机制
接下来，我们介绍红黑树的自平衡机制，讲述红黑树是怎样通过它的自平衡机制降低旋转的执行次数的。红黑树自平衡机制用来调整平衡的方法只有三个，简而言之：变色、左旋和右旋。我们先简单介绍这三种方法，再结合增删节点场景来讲，因为通常只有增删节点后才需要调整平衡。三种方法总结如下表：
以上是三种方法的基本定义和发生时机，但具体需要结合增删节点场景来决定何时用变色，何时用左旋和右旋进行平衡调整，因为只有增删节点时，才会让红黑树的相对平衡遭到破坏从而需要调整。
这里说明一下，我们后续讲到的分情况的场景，都是指新增之前或被删除之前的场景，而且在新增或删除发生之前，场景下的红黑树应该是相对平衡且没有违反红黑树的所有规范。
插入场景的自平衡处理
对于新增的节点来说，其颜色必须是红色，这也是约定成俗的规范，因为新增节点为黑色会违反规范5，会改变某些路径上黑色节点的数目，从而破坏平衡性，同时这样约定，也是为了方便后续的调整处理。
通常对于新增的节点，在其被新增之前，其父节点只有黑色和红色两种。其中对于黑父，新增节点时不用作任何处理，因为此时新增红色节点不会影响所有路径上黑色节点的数目，也不会违反任何规范。而对于红父，新增红色节点会出现红红相连，违反规范4需要调整；一般分红父无叔节点和红父有叔节点两种情况。
红父无叔节点
对于这种情况，一般处理方法包括两部分：变色和旋转，变色一般是把其父节点和祖父节点颜色互换，父节点变黑，祖父节点变红；至于是左旋还是右旋和旋转几次，取决于新增节点和父节点的位置；变色和旋转没有顺序先后，先变色先旋转都可以。
1. 红父为左节点，新增节点也为左节点
上图1-6新增节点6N和父节点15P红红相连违反红黑树规范4，处理逻辑是：先变色，父节点15P变为黑色，祖父节点20G变为红色；后右旋父节点15P，使之替代祖父节点位置，祖父节点20G成为父节点15P的右节点。
处理后，满足红黑树各规范，各路径上黑色节点数相同无红红相连。
2. 红父为左节点，新增节点为右节点
上图1-7新增节点18N和父节点15P红红相连违反红黑树规范4，处理逻辑是：先左旋新节点18N，替代父节点15P位置，使父节点15P位置成为其左节点；此时还原成图1-6初始状态，则按图1-6的处理逻辑做后续调整。
处理后，满足红黑树各规范，各路径上黑色节点数相同无红红相连。
3. 红父为右节点，新增节点也为右节点
上图1-8新增节点26N和父节点25P红红相连违反红黑树规范4，处理逻辑是：先变色，父节点25P变为黑色，祖父节点20G变为红色；后左旋父节点25P，使之替代祖父节点位置，祖父节点20G成为父节点25P的左节点。
至此，处理后子树满足红黑树各规范，各路径上黑色节点数相同无红红相连。
4. 红父为右节点，新增节点也为左节点
上图1-9新增节点23N和父节点25P红红相连违反红黑树规范4，处理逻辑是：先右旋新节点23N，替代父节点25P位置，使父节点25P位置成为其右节点；此时还原成图1-8初始状态，则按图1-8的处理逻辑做后续调整。
处理后，满足红黑树各规范，各路径上黑色节点数相同无红红相连。以上是新增节点红父无叔节点的情况。
红父有叔节点
对于这种情况，新增节点的叔节点只能是红色，不会存在黑色叔节点的场景。一般处理逻辑包括两部分：第一部分是对以新增节点为基础往上的三代进行变色；第二部分是对新增节点的祖父节点往上三代进行变色和旋转处理并递归，我们暂称之为祖父节点们的递归处理；这里是有顺序的，处理完第一部分，才能确定是否要进行第二部分处理，如果祖父节点和其父节点没有出现红红相连的情况，就无须处理，否则要继续往上处理甚至递归。
红父红叔情况下第一部分变色逻辑处理
上图1-10新增节点23N和父节点20P红红相连违反红黑树规范4，处理逻辑是：只用变色处理，把父节点20P和叔节点28U变成黑色，再把祖父节点25G变成红色。
对于第一部分的处理，不用考虑父节点和新增节点的位置，因为只是颜色的变换，没有涉及旋转位置的移动；变色后，第一部分的处理结束。此后，要看祖父节点25G和它的父节点是否会出现红红相连的情况，如果出现，则要进行第二部分的祖父节点们的递归处理。而往上递归处理的场景需要考虑多种场景，这里就会出现红父黑叔的场景，基于不同场景酌情处理。祖父节点的递归处理的场景如下，其实和新增节点大同小异，只是祖父节点的红父黑叔场景要等同新增节点的红父无叔节点场景处理。
1. 红父红叔，等同新增节点图1-10的处理逻辑处理逻辑同图1-10是：只用变色处理，把父节点和叔节点变成黑色，再把祖父节点变成红色。
2. 红父黑叔，红父为左节点，目标节点为左节点，处理逻辑同图1-63. 红父黑叔，红父为左节点，目标节点为右节点，处理逻辑同图1-74. 红父黑叔，红父为右节点，目标节点为右节点，处理逻辑同图1-85. 红父黑叔，红父为右节点，目标节点为左节点，处理逻辑同图1-9
所以不论是新增节点，还是对于要被递归处理的祖父节点们，其实归纳起来就五种场景和对应的五种处理逻辑(如果把叶子节点画上，新增节点的红父无叔场景就等同红父黑叔场景，这也正说明了叶子节点的作用，简化了红黑树场景分析)，当然实际处理时，可能是以上五种场景和处理逻辑的嵌套和组合。从上述处理逻辑，我们可以看到，红黑树在处理新节点插入时，在黑父和红父红叔的两种场景下，完全不用旋转，要么不用处理要么就通过变色处理；其他场景，也可以通过旋转和变色组合来降低旋转次数。
考虑这篇文章的篇幅和红黑树删除场景的复杂性，关于红黑树的删除的自平衡处理和各种场景，决定单独放到一章去讲解。烦请关注！
码农爱刷题
为计算机编程爱好者和从业人士提供技术总结和分享 ！为前行者蓄力，为后来者探路！
