红黑树是一种自平衡的二叉搜索树，它在插入和删除时通过节点的颜色（红色或黑色）和旋转操作来保持平衡，以确保插入、删除和查找操作的时间复杂度在最坏情况下都能维持在 O(log n)。

红黑树的特点是通过一些额外的属性和颜色标记，来确保树的高度接近最优（即平衡的状态），从而避免出现普通二叉搜索树可能产生的退化为链表的情况。

一、红黑树的设定

红黑树的每个节点除了存储键和值，还存储一个用于标记颜色的属性，该属性表示红色或黑色。

红黑树通过以下特性来确保树的平衡。

  • 性质一：节点是黑色或红色的。节点要么是黑色的，要么是红色的。
  • 性质二：根节点是黑色的。红黑树的根节点始终是黑色的。这确保树的基本平衡，不会出现根节点为红色的情况。
  • 性质三：所有叶子结点是黑色的。红黑树中所有的叶子节点都是黑色的。
  • 性质四：红色节点的子节点必须是黑色。红色节点的子节点不能是红色的。也就是说，在红黑树中，两个相邻的节点不可能都是红色的。通过这条规则，红黑树可以避免过长的分支。
  • 性质五：从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。这条规则保证了树的平衡，因为它限制了任何一个分支不会哔其他分支更长，从而防止树退化为链表。

有了上面的几个性质作为限制，即可避免二叉查找树退化成单链表的情况。但仅仅防止红黑树退化成单链表是不够的，还需要考虑每个叶子节点路径长度的问题，如果某些叶子节点的路径过长，那么对这些路径上的节点进行插入删除操作时，效率也会大大降低。

这时，因为性质四和性质五的限制，任意节点到其每个叶子节点的路径最长不会超过最短路径的 2 倍。因为叶子节点到根节点的路径上的黑色节点是可以连续的，所以最短路径必然都是由黑色节点构成的。又因为红色节点是不能连续的，所以最长的路径必然是由红色和黑色节点相间构成的。又因为性质五的限制，从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点，所以路径最长的情况和路径最短的情况黑色节点数量是相同的，在路径最长的情况下，路径上的红色节点数量 = 路径上的黑色节点数量，该路径的长度也就等于最短路径长度的 2 倍。

二、红黑树的操作

查询、插入和删除操作中，插入和删除操作会影响树的平衡，需要通过旋转树和颜色变换来保证树的结构维持红黑树的特性。

1、查询

查找操作在红黑树中与普通的二叉搜索树相同，红黑树是二叉搜索树，左子树的所有节点都小于父节点，右子树的所有节点都大于父节点。其查找操作从根节点开始，根据查找值域当前节点值的大小关系，决定是向左子树还是右子树中递归查找。

查找操作的时间复杂度为 O(log n)，因为红黑树通过平衡保持了树的高度接近最优。

2、插入

插入的流程如下：插入时首先将新节点作为红色节点插入到树中，之后通过旋转、重新着色操作使其重新成为红黑树。

如果插入时将新节点设为黑色，会导致从根到叶子的路径多了一个额外的黑色节点，这个是很难调整的。如果将新节点设为红色节点，会导致出现两个连续红色节点的冲突，通过颜色调换和旋转来调整，会方便一点。

2.1 插入的节点为根节点

当插入的新节点为根节点时，将节点由红色变为黑色即可。

2.2 父亲节点为黑色节点

当插入的新节点的父节点是黑色节点时，不需要进行任何操作，此时树的结构仍然满足红黑树的条件。

2.3 父亲节点是红色节点，叔叔节点是红色节点

将父节点和叔节点变更为黑色，将祖父节点变更为红色。此时祖父节点可能会与他的父节点形成连续的红色节点，所以此时要将祖父节点当做新加入的节点来看待，向上递归进行上述改变颜色的调整，直到把根节点当做新加入的节点时停止，最后将根节点变更为黑色。

父节点为红色，新插入节点也为红色，因为不能有两个连续的红色节点存在，将父节点变更为黑色，叔节点也需要一起变更，因为从某一结点到其所有叶子节点的所有路径上的黑色节点数量要相同。

上面的示例中，在拥有 20，15，25 三个节点的红黑树中，插入新节点 23 时首先会当做红色节点插入到树中，因为其父节点和叔节点都为红色，则将其父节点和叔节点都变更为黑色，将祖父节点变更为红色，因为祖父节点为根节点，所以最后需要将祖父节点变更为黑色。

2.4 父亲节点是红色节点，叔叔节点是黑色节点

2.4.1 新节点为父节点的左孩子，父节点为祖父的左孩子

对新插入节点的祖父节点进行一次右旋，并交换新插入节点的父节点和祖父节点的颜色。

上图的示例中，在拥有 20，15 两个节点的红黑树中插入节点 10，新节点 10 插入时首先会被当做红色节点，此时新插入的节点和其父节点都为红色，叔节点为黑色，且新插入节点位于父节点的左子树上，需要对新插入节点的祖父节点进行右旋，之后交换新插入节点的父节点和组父节点的颜色。

2.4.2 新节点为父节点的右孩子，父节点为祖父的右孩子

对新插入节点的祖父节点进行一次左旋，并交换新插入节点的父节点和祖父节点的颜色。

上图的示例中，在拥有 20，25 两个节点的红黑树中插入节点 28，新节点 28 插入时首先会被当做红色节点，此时新插入的节点和其父节点都为红色，叔节点为黑色，且新插入节点位于父节点的右子树上，需要对新插入节点的祖父节点进行左旋，之后交换新插入节点的父节点和祖父节点的颜色。

2.4.3 新节点为父节点的右孩子，父节点为祖父的左孩子

先对新插入节点的父节点进行一次左旋，调整新插入节点和其父节点的位置。

之后调整新插入节点和其原祖父节点（现父节点）的颜色，并对新插入节点的原祖父节点进行一次右旋。也就是当做“新节点为父节点的左孩子，父节点为祖父的左孩子”情形来处理。

上图示例中，在拥有 20，15 两个节点的红黑树中插入节点 18，新节点 18 插入时首先会被当做红色节点，此时新插入的节点和其父节点都为红色，叔节点为黑色，且新插入的节点位于父节点的右子树上，而父节点位于祖父节点的左子树上，需要先对父节点进行一次左旋，调整新插入节点 18 和其父节点 15 的位置。

之后对祖父节点 20 进行右旋，同时交换新插入节点 18 与原祖父节点（现父节点）20 颜色。这一步就当做“新节点为父节点的左孩子，父节点为祖父的左孩子”情形来处理。

2.4.4 新节点为父节点的左孩子，父节点为祖父的右孩子

先对新插入节点的父节点进行一次右旋，调整新插入节点和其父节点的位置。

之后交换新插入节点和其原祖父节点（现父节点）的颜色，并对新插入节点的原祖父节点进行一次左旋。也就是当做“新节点为父节点的右孩子，父节点为祖父的右孩子”情形来处理。

上图示例中，在拥有 20，25 两个节点的红黑树中插入节点 23，新节点 23 插入时首先会被当做红色节点，此时新插入的节点和其父节点都为红色，叔节点为黑色，且新插入的节点位于父节点的左子树上，而父节点位于祖父节点的右子树上，需要先对父节点进行一次右旋，调整新插入节点 23 和其父节点 25 的位置。

之后对祖父节点 20 进行左旋，同时交换新插入节点 23 与原祖父节点（现父节点）20 的颜色。这一步就当做“新节点为父节点的右孩子，父节点为祖父的右孩子”情形来处理。

3、删除

对于二叉排序树，在删除带有两个非叶子儿子的节点时，需要去寻找该节点左子树中最大的元素或右子树中最小的元素（二叉树中序遍历时节点的前驱节点或后继节点），并把寻找到的节点的值转移到要删除的节点中，之后删除从中复制出值的那个节点（寻找到的节点）。因为前驱节点或后继节点必定最多只有一个子节点（否则其不可能是前驱节点或后继节点），因此可以将其简化为删除一个最多只有一个儿子（非叶子）的节点的问题。

为什么说是前驱节点或后继节点最多只有一个儿子呢？中序遍历中，先处理节点的左孩子，再处理当前节点，之后再处理右孩子，也就是说某节点的前驱节点肯定是左子树中最后被处理的节点，后继节点肯定是右子树中最先被处理的节点。又因为二叉排序树中某节点的左孩子值肯定比该节点小，右孩子肯定比该节点大。所以其前驱节点肯定是左子树中最大的节点，后继节点肯定是右子树中最小的节点，前驱节点不可能有右孩子（右孩子值比节点值大），后继节点不可能有左孩子（做孩子值比节点值小）。

因此，只需要讨论删只有一个儿子的节点的情况。如果两个儿子都为空节点，即均为叶子节点，可以任意将其中一个看做它的儿子。

红黑树的删除过程类似于二叉排序树的删除，但需要做出一些额外的操作来维护红黑树的性质。红黑树删除的基本步骤如下：

  • 找到要删除的节点并删除
    • 如果待删除节点没有非空儿子，即为叶子节点，则直接删除即可
    • 如果待删除节点只有一个儿子，删除该节点，并用该节点的唯一子节点顶替它的位置
    • 如果待删除节点有两个儿子，则找到它的后继节点或前驱节点（通常选择后继节点）并将值替换到待删除节点。替换时不替换颜色。之后准备删除其前驱节点或后继节点。
  • 删除节点后修复红黑树。删除节点，如果要删除的节点的颜色是红色的，不需要进行修复。如果删除的是黑色的节点，则可能会破坏红黑树的平衡，需要进行修复。

待删除节点是红色节点

如果要删除的节点为红色的，因为红黑树性质的限制，此时该节点的儿子都将为叶子节点，它的父亲和儿子一定是黑色的，所以可以简单的用其黑色儿子（空节点，叶子节点）替换它（即删除），不会破坏红黑树的性质三和性质四。通过该节点到达所有叶子节点的路径上只是少了一个红色节点，也不会破坏性质五。

为什么说改节点的儿子都将为叶子节点呢？红色节点不能连续，当该红色节点有一个非空黑色儿子时又不满足性质五，所以它的两个儿子必定都为空节点。

待删除节点是黑色节点

如果要删除的节点是黑色的，会导致根节点到其每个叶子节点的所有路径上黑色节点数量不相等，会破坏红黑树的平衡，也就是双重黑色节点问题。此时需要进行修复操作。修复的关键是通过重新着色或旋转操作，恢复红黑树的平衡。

待删除节点是黑色节点，且有一个红色子节点

当待删除的黑色节点有一个红色子节点时，用这个红色子节点代替被删除的节点，并将该子节点染成黑色即可。这样路径上的黑色节点数量没有发生变化，不会破坏红黑树的性质五。

待删除节点是黑色节点，且儿子节点为黑色

这是一种复杂的情况。这种情况下该节点的两个儿子都是叶子节点（即空节点），也就是说这种情况下该节点没有非空儿子。若其中一个儿子是黑色非叶子节点，另一个儿子是叶子节点，那么从该节点通过非叶子节点儿子的路径上的黑色节点数最小为 2，而从该节点到另一个叶子节点儿子的路径上的黑色节点数为 1，违反了性质五。

这里首先要做的操作是将要删除的节点替换为它的儿子（空节点），称呼这个儿子为 N（新位置上），称呼其兄弟为 S，称呼 N 的父亲为 P，称呼兄弟节点 S 的左儿子为 L，右儿子为 R。

红黑树确实有一点复杂。。。

删除操作没有理解透彻，这里将待删除节点是黑色节点的某些情况删除，归类为待整理。。。

三、红黑树与 AVL 树对比

两者都是自平衡的二叉搜索树，两者主要目的是在查找、插入和删除操作时保持平衡，以保证这些操作的最坏时间复杂度为 O(log n)。

两者差异主要体现在如下方面：

  • 平衡条件
  • 旋转次数
  • 查询效率
  • 插入和删除效率
  • 存储开销
  • 应用场景

红黑树通过节点的红黑性质和一组规则来保持近似平衡，但允许局部的不完全平衡，其最大高度约为 2 log n

因为允许部分不平衡，其高度可能会比 AVL 树更高一些。但其插入和删除操作性能更高，因为其不需要像 AVL 树那样频繁地旋转。

AVL 树更严格地保持平衡，要求每个节点的左右子树高度差不超过 1，严格地平衡条件使得 AVL 树的高度非常接近 log n

AVL 树在相比于红黑树更加平衡，因此其查找操作性能通常比红黑树更快。

四、二叉树的近侄子和远侄子

在二叉树中，近侄子和远侄子是相对于一个节点及其兄弟节点的位置关系来定义的，通常用来描述修复平衡二叉树（如红黑树、AVL 树）中的旋转和调整操作。

假设现在有一个节点 x 和它的兄弟节点 w，根据 w 是其父节点的左子节点还是右子节点，以及子节点的位置，定义了“近侄子”和“远侄子”。

1、近侄子

指的是节点 x 的兄弟节点 w 的子节点中，靠近 x 的那个子节点，是对 x 来说较近的子节点。

例如：

  • 如果 w 是 x 的左兄弟，那么 w 的右孩子为 x 的近侄子
  • 如果 w 是 x 的右兄弟，那么 w 的做孩子为 x 的近侄子

2、远侄子

指的是节点 x 的兄弟节点 w 的子节点中，远离 x 的那个子节点，是对 x 来说较远的子节点。

例如：

  • 如果 w 是 x 的左兄弟，那么 w 的左孩子为 x 的远侄子
  • 如果 w 是 x 的右兄弟，那么 w 的右孩子为 x 的远侄子

相关链接

OB tags

#数据结构 #二叉树 #未完待续