红黑树

R-B Tree，全称Red-Black Tree，又称红黑树，一种特殊的二叉平衡树。它通过引入颜色标记和一系列约束规则，保证了树的插入、删除等操作后的平衡性，从而使得查找、插入、删除的时间复杂度均保持在O(log n)范围内。

1.前提知识

在了解红黑树之前，我们先得了解BST二叉查找树和AVL平衡二叉树的一些基本概念。

1.1.BST二叉查找树

什么是二叉查找树

二叉查找树(BST) 又叫二叉搜索树，它满足以下性质：

  • 若任意节点的左子树不为空，则左子树上所有的节点的值均小于它的根节点的值。
  • 若任意节点的右子树不为空，则右子树上所有的节点的值均大于它的根节点的值。
  • 任意节点的左、右子树也分别为二查找树。

二叉查找树的查找流程

在二叉查找树b中查找x的过程为：

1.若b是空树，则查找失败，否则：

2.若x等于b的根节点的数据域之值，则查找成功；否则：

3.若x小于b的根节点的数据域之值，则查找左子树；否则：

4.查找右子树。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
    // 在根指针T所指二叉查找树中递归地查找其关键字等于key的数据元素，若查找成功，
    // 则指针p指向该数据元素指针，并返回TRUE，否则指针指向查找路径上访问的最后
    // 一个指针并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
    if (!T) { // 查找不成功
        p = f;
        return false;
    } else if (key == T->data.key) { // 查找成功
        p = T;
        return true;
    } else if (key < T->data.key) // 在左子树中继续查找
        return SearchBST(T->lchild, key, T, p);
    else // 在右子树中继续查找
        return SearchBST(T->rchild, key, T, p);
}

二叉查找树的极端情况

如果插入的数据是有序的或接近有序的（如从大到小依次插入），此时会导致树退化为链表结构，这个时候查询或写入耗时与链表相同，最坏情况的时间复杂度为O(n)。

退化成链表的BST：

如何避免这种情况：

针对这种情况引入了平衡二叉树和红黑树，他们通过旋转等操作确保树的高度保持在O(log n)范围内，从而保证查找、插入和删除操作的时间复杂度为O(log n)。

1.2.AVL平衡二叉树

平衡二叉树也加AVL，属于二叉查找树的一种，但是AVL通过机制保证了自身的平衡。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此他也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是**O(log n)**。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来

特性：

  • 对于任何一颗子树的root根节点而言，它的左子树任何节点的key一定比root小，而右子树任何节点的key一定比root大。
  • 对于AVL树而言，其中任何子树仍然是AVL树。
  • 每个节点的左右子节点的高度差的绝对值最多为1。

在插入、删除树节点的时候，如果破坏了以上规则，AVL树会自动进行调整达到平衡。

1.2.1AVL的平衡调整

导致AVL失衡的四中情况：

  • 左左结构失衡（LL型失衡）
  • 右右结构失衡（RR型失衡）
  • 左右结构失衡（LR型失衡）
  • 右左结构失衡（RL型失衡）
LL型(右旋)：

场景：当某节点的左子树的左子树插入新节点，导致该节点的平衡因子由1变为2。此时通过对该节点进行右旋操作恢复平衡。

图中插入新节点 1 ，导致树失衡，此时以根节点 root 的左子节点为支点（pivot)，进行右旋，旋转完成后：

  • pivot 成为新的根节点。
  • 原来的根节点 root 变为 pivot 的右子节点。
  • pivot 原来的右子节点 6 变为 root 节点的左子节点。

右旋动画演示：

在这里插入图片描述
RR型(左旋):

场景：在某节点的右子树的右子树上插入新节点，导致该节点的平衡因子由-1变为-2。此时通过对该节点进行左旋操作来恢复平衡。

图中插入新节点 13 ，导致树失衡，此时以根节点 root 的右子节点为支点（pivot)，进行左旋，旋转完成后：

  • pivot 成为新的根节点。
  • 原来的根节点 root 变为 pivot 的左子节点。
  • pivot 原来的左子节点 9 变为 root 节点的右子节点。

左旋动画演示：

在这里插入图片描述

LR型(左旋+右旋):

场景：在某节点的左子树的右子树上插入新节点，导致该节点的平衡因子由1变为2。此时需要先对左子树进行左旋（RR旋转），然后对该节点进行右旋（LL旋转）来恢复平衡。

如图插入新节点 7 ，导致树失衡，此时需要进行两次旋转，我们先对它的左子树进行一次左旋，此时以 root 为根节点的树比变为了LL型失衡，然后在进行一次右旋即可。

RL型(右旋+左旋):

场景：在某节点的右子树的左子树上插入新节点，导致该节点的平衡因子由-1变为-2。此时需要先对右子树进行右旋（LL旋转），然后对该节点进行左旋（RR旋转）来恢复平衡。

如图插入新节点 9 ，导致树失衡，此时需要进行两次旋转，我们先对它的右子树进行一次右旋，此时以 root 为根节点的树变为了RR型失衡，然后在进行一次左旋即可。

1.2.2AVL树的问题

平衡二叉树在插入或删除节点时，由于严格的平衡要求，频繁触发失衡调整（如多次旋转），导致大量的时间消耗在维护平衡上，效率低下，因此AVL树一般用于查询场景，而不是增加删除频繁的场景。

红黑树对于AVL的问题又做了相应的优化：

  • 继承自平衡优点 ：保留了AVL树自平衡的特性，确保树的高度始终保持在O(log n)范围内，从而保证基本操作的时间复杂度。

  • 放宽平衡条件 ：通过允许最长路径不超过最短路径两倍的“近似平衡”，减少了插入和删除时的旋转次数，提升了动态场景下的效率。

  • 适合频繁更新场景 ：相比AVL树，红黑树在插入和删除操作中调整成本更低，更适合频繁增删的场景。

2.红黑树概念

2.1.性质

  • 节点是红色或黑色：每个节点都有一个颜色的属性，要么红色，要么黑色。

  • 根节点是黑色：树的根节点始终为黑色。

  • 叶子节点（NIL节点）是黑色：树的叶子节点，也就是树的边界节点，它们默认都为黑色。

  • 红色节点的子节点必须是黑色：如果一个节点是红色，则它的子节点必须是黑色（也就是说不能出现连续的红色节点）。

  • 从任意节点到其每个叶子节点的所有简单路径上，包含相同数量的黑色节点：这一性质称为“黑高”，确保了树的平衡性。

基于上面这些性质，我们一般在插入红黑树节点的时候，会将这个节点设置为红色。原因是由于最后一条性质，红色破坏性质的可能性最小，如果是黑色，很可能导致这条支路的黑色节点比其他支路的要多，破坏平衡。

2.2.红黑树的节点结构

以HashMap中红黑树的实现为例。

HashMap中红黑树节点由TreeNode类表示，继承自LinkedHashMap.Entry，并增加了颜色标记和父子指针字段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  	//父节点
    TreeNode<K,V> left;		//左子节点
    TreeNode<K,V> right;	//右子节点
    TreeNode<K,V> prev;		//前驱节点（用于双向链表），便于删除操作
    boolean red;  			//颜色标记（true 表示红色，false 表示黑色）
    
    //构造方法
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    
    //其他方法...
}

3.红黑树插入节点

在红黑树的插入操作中，新节点被插入后可能会破坏红黑树的性质，因此需要进行修复。以下是插入时可能遇到的几种情况及其处理方法：

3.1.插入的新节点是根节点

场景：树为空，新节点成为根节点。

处理：直接将根节点的颜色设置为黑色即可。（性质2：根节点必须是黑色）

3.2.新节点的父节点为黑色

场景：新插入节点的父节点已经是黑色。

处理：无需任何操作，因为默认插入红色节点不会影响黑高或连续红色节点的规则。

3.3.新节点的父节点为红色

如果新节点的父节点为红色，那么该节点的父节点不可能为根节点，所以插入节点总存在祖父节点(三代关系)。由于性质四：红色节点的子节点必须是黑色。所以此时会出现两种情况：

叔叔节点为红色：

场景：父节点和叔叔节点均为红色。

处理：

  • 将父节点和叔叔节点的颜色变为黑色。
  • 将祖父节点颜色变为红色。
  • 如果祖父为根，再将根变为黑色，如果祖父为非根，将祖父设置为当前节点在进行其他判断。

叔叔节点为黑色：

如果叔叔节点是黑色，根据新节点的位置，分为以下四种旋转场景：

（1）LL型

场景：新节点是父节点的左子节点，父节点是祖父节点的左子节点。

处理：

  • 交换父节点和祖父节点的颜色（父节点变黑，祖父节点变红）。

  • 对祖父节点进行右旋。

（2）RR型

场景：新节点是父节点的右子节点，父节点是祖父节点的右子节点。

处理：

  • 交换父节点和祖父节点的颜色（父节点变黑，祖父节点变红）。

  • 对祖父节点进行左旋。

（3）LR型

场景：新节点是父节点的右子节点，父节点是祖父节点的左子节点。

处理：

  • 对父节点进行左旋，转换为LL型。
  • 按照LL型情况处理（1.变色 2.右旋 P节点）。

（4）RL型

场景：新节点是父节点的左子节点，父节点是祖父节点的右子节点。

处理：

  • 对父节点进行右旋，转化为RR型。
  • 按照RR型情况处理（1.变色 2.左旋 P节点）。

4.红黑树与AVL树区别

1.平衡机制不同：

红黑树根据路径上黑色节点数目是否一致，来确认是否平衡，如果失衡，通过变色和旋转恢复平衡。

AVL树根据树的平衡因子绝对值是否超过 1，来确认是否失衡，如果失衡，通过旋转来恢复。

2.红黑树插入与删除效率更高：

红黑树的非严格的平衡换取插入与删除节点时旋转的次数，任何不平衡都会在三次旋转以内解决。

AVL树是严格的平衡树，在插入与删除节点时，根据不同情况，旋转的次数比红黑树要多，所以红黑树的插入效率更高。

3.适用性

AVL追求极致的查找性能，而红黑树在查询、插入和删除之间取得平衡，如果在你的应用中查找的次数远远大于插入和删除，选择AVL树，如果查询和插入删除次数差不多，那么选择红黑树更好。