红黑树

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 6k 阅读时长 ≈ 5 分钟

红黑树：自平衡二叉查找树的高效实现

红黑树是一种自平衡的二叉查找树，通过一套特定的规则（颜色约束和旋转操作）保证树的高度始终维持在O(logn)级别，解决了普通二叉查找树在极端情况下退化为链表（查询效率降至O(n)）的问题。它广泛应用于 Java 的TreeMap、C++ 的map等集合类，以及数据库索引的底层实现。

二叉查找树的局限性与红黑树的诞生

二叉查找树的核心特性

二叉查找树（BST）满足：

  • 左子树所有节点值 < 根节点值；
  • 右子树所有节点值 > 根节点值；
  • 左右子树均为二叉查找树。

其查询、插入、删除的平均时间复杂度为O(logn)，但在有序插入时（如依次插入 1,2,3,4），会退化为单链表，此时操作复杂度飙升至O(n)。

根据二分查找树的特性来说，使用中序遍历可以得到一个由小到大的有序序列。

插入节点

  • 以根节点为当前节点开始搜索
  • 新节点的值与当前节点比较
  • 如果新节点大于当前节点，则以当前节点的右子节点作为新的当前节点；如果新节点小于当前节点，则以当前节点的左子节点作为新的当前节点
  • 重复上述操作，直到搜索到合适的叶子节点，将该新节点添加为叶子节点的左/右节点

删除节点

  • 如果删除的节点是叶子节点，只需将它从其父节点中删除
  • 如果不是叶子节点，且只有一个子节点，被删除的节点p只有左子树，将p的左子树pL添加为p的父节点的左子树；被删除的节点p只有右子树，将p的右子树pR添加为p的父节点的右子树
  • 如果被删除的p的左右节点都非空，有两种做法
    • 做法一：将pL设为p的父节点q的左或右子节点，将pR设为p节点的中序前驱结点s的右子节点(s是pL最右下节点)
    • 做法二：以p节点的中序前驱或后继替代p所指节点，然后再从原二叉查找树中删去中序前驱或后继节点(用大于p的最小节点或小于p的最大节点代替p节点)
static class TreeNode<E> {
    E data;
    TreeNode<E> parent;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E data) {
        this.data = data;
    }

    public TreeNode(E data, TreeNode<E> parent, TreeNode<E> left, TreeNode<E> right) {
        this.data = data;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        TreeNode<?> treeNode = (TreeNode<?>) o;

        if (!data.equals(treeNode.data)) return false;
        if (!parent.equals(treeNode.parent)) return false;
        if (!left.equals(treeNode.left)) return false;
        return right.equals(treeNode.right);
    }

    @Override
    public int hashCode() {
        int result = data.hashCode();
        result = 31 * result + parent.hashCode();
        result = 31 * result + left.hashCode();
        result = 31 * result + right.hashCode();
        return result;
    }
}

// 根节点
private TreeNode<E> root;

public LookBinTree(E root) {
    this.root = new TreeNode<>(root);
}

/**
 * 添加节点
 *
 * @param data
 * @return
 */
public void add(E data) {
    // 根节点为空，则为根节点
    if (root == null) {
        root = new TreeNode<>(data);
    } else {
        TreeNode<E> current = root;
        TreeNode<E> parent = null;
        // 从根节点往下搜索,找到合适的叶子节点
        int cmp = 0;
        do {
            parent = current;
            cmp = data.compareTo(parent.data);
            if (cmp > 0) { // 新节点大于当前节点
                current = current.right;
            } else { // 新节点小于当前节点
                current = current.left;
            }
        } while (current != null);
        // 创建新节点
        TreeNode<E> newNode = new TreeNode<>(data, parent, null, null);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

    }
}

/**
 * 删除节点
 *
 * @param data
 */
public void remove(E data) {
    TreeNode<E> node = getNode(data);
    if (node == null) { // 没有该元素
        return;
    }

    if (node.left == null && node.right == null) { // 左右子树都是空的
        if (node == root) { // 如果是根节点
            root = null;
        } else {
            if (node.parent.left == node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            node.parent = null;
        }

    } else if (node.left == null && node.right != null) { // 左子树为空，右子树不为空
        if (node == root) { // 如果是根节点
            root = node.right;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.right;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
        }

    } else if (node.left != null && node.right == null) { // 左子树不为空，右子树为空
        if (node == root) { // 如果是根节点
            root = node.left;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.left;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.left;
            }
            node.left.parent = node.parent;
        }

    } else { // 左右子树都不为空
        TreeNode<E> leftMaxNode = node.left;
        // 找到左子树的最大值
        while (leftMaxNode.right != null) {
            leftMaxNode = leftMaxNode.right;
        }
        leftMaxNode.parent.right = null;
        leftMaxNode.parent = node.parent;
        if(node == node.parent.left){ // 被删除的是父节点的左子树
            node.parent.left = leftMaxNode;
        } else {
            node.parent.right = leftMaxNode;
        }

        leftMaxNode.left = node.left;
        leftMaxNode.right = node.right;
        node.parent = node.left = node.right = null;

    }
}

public TreeNode<E> getNode(E data) {
    // 从根节点往后搜索
    TreeNode<E> current = root;
    while (current != null) {
        int cmp = data.compareTo(current.data);
        if (cmp > 0) {
            current = current.right;
        } else if (cmp < 0) {
            current = current.left;
        } else {
            return current;
        }
    }
    return null;
}

红黑树的改进思路

红黑树在 BST 的基础上增加了颜色属性（红或黑）和平衡规则，通过插入 / 删除后的变色和旋转操作，确保树的高度始终为O(logn)，从而保证所有操作的时间复杂度稳定在O(logn)。

红黑树的五大核心特性

红黑树的节点除了 BST 的data、left、right、parent外，多了一个color属性（红 / 黑）。其必须满足以下规则：

  1. 颜色约束：每个节点要么是红色，要么是黑色。
  2. 根节点规则：根节点必须是黑色。
  3. 叶子节点规则：所有叶子节点（NIL 节点，空节点）必须是黑色。
  4. 红色节点规则：若一个节点是红色，则其两个子节点必须是黑色（不允许连续两个红色节点）。
  5. 黑色平衡规则：从任一节点到其所有叶子节点的路径中，黑色节点的数量必须相同（称为 “黑色高度”）。

红黑树

特性的作用

  • 规则 4 避免了 “红色链” 过长，规则 5 保证了各路径的黑色节点数均衡。
  • 两者结合，使得红黑树的最长路径长度不超过最短路径的 2 倍，从而保证树高为O(logn)。

红黑树的基本操作：变色与旋转

当插入或删除节点破坏红黑树的规则时，需通过变色和旋转恢复平衡。

1. 变色

将节点的颜色从红改为黑，或从黑改为红（通常用于调整黑色高度或避免连续红色节点）。

  • 例：若父节点和叔叔节点均为红色，可将两者改为黑色，祖父节点改为红色（避免连续红节点）。

2. 旋转

旋转分为左旋和右旋，用于调整节点的位置关系，不改变 BST 的有序性，仅调整树的结构以平衡高度。

（1）左旋（逆时针旋转）

将节点x旋转为其右孩子y的左孩子，y的左孩子成为x的右孩子。

左旋前：       左旋后：
  x           y
   \         /
    y   →   x
   /         \
  a           a

作用：将右子树的高度转移到左子树，减少右偏。

（2）右旋（顺时针旋转）

将节点y旋转为其左孩子x的右孩子，x的右孩子成为y的左孩子。

右旋前：       右旋后：
    y           x
   /           \
  x     →       y
   \           /
    a         a

作用：将左子树的高度转移到右子树，减少左偏。

红黑树的插入操作

插入的新节点默认是红色（若设为黑色，会直接破坏黑色平衡规则，调整成本更高）。插入后需根据父节点的颜色和叔叔节点的状态，分情况处理：

插入场景与处理策略

情况 1：新节点是根节点
  • 直接将其改为黑色（满足规则 2）。
情况 2：父节点是黑色
  • 新节点为红色，父节点为黑色，无连续红节点，无需调整（满足所有规则）。
情况 3：父节点是红色，叔叔节点也是红色
  • 问题：父节点（红）+ 新节点（红）→ 违反规则 4（连续红节点）。
  • 处理：
    1. 父节点和叔叔节点改为黑色；
    2. 祖父节点改为红色；
    3. 以祖父节点为新节点，递归向上调整（可能影响更高层的平衡）。
情况 4：父节点是红色，叔叔节点是黑色（或不存在）

  • 问题：连续红节点，且叔叔节点无法通过变色分担（叔叔为黑）。

  • 处理：根据新节点、父节点、祖父节点的位置关系，结合旋转 + 变色解决：

    | 子节点位置 | 父节点位置 | 操作步骤 |
    | ——————— | ———————— | —————————————————————————————— |
    | 父节点的左孩子 | 祖父节点的左孩子 | 1. 祖父节点右旋； 2. 父节点与祖父节点交换颜色（父变黑，祖父变红）。 |
    | 父节点的右孩子 | 祖父节点的左孩子 | 1. 父节点左旋（转为上一种情况）； 2. 按上一种情况处理。 |
    | 父节点的右孩子 | 祖父节点的右孩子 | 1. 祖父节点左旋； 2. 父节点与祖父节点交换颜色。 |
    | 父节点的左孩子 | 祖父节点的右孩子 | 1. 父节点右旋（转为上一种情况）； 2. 按上一种情况处理。 |

插入示例

插入节点10到红黑树中，假设父节点8为红，祖父节点15为黑，叔叔节点20为黑：

  1. 新节点10是父节点8的右孩子，父节点8是祖父节点15的左孩子 → 符合 “情况 4-2”；
  2. 先对父节点8左旋，将10变为8的父节点；
  3. 对祖父节点15右旋，10成为新的祖父节点；
  4. 交换10与15的颜色（10变黑，15变红），最终满足所有规则。

红黑树的删除操作

删除操作比插入更复杂，需先按 BST 的规则删除节点，再通过变色和旋转恢复红黑树规则。核心是处理 “删除黑色节点导致黑色平衡被破坏” 的场景，具体分为：

  • 被删节点是红色：直接删除，不影响平衡；
  • 被删节点是黑色：需通过 “借调兄弟节点的黑色” 或 “合并节点” 恢复黑色平衡（过程类似插入，但涉及更多旋转组合）。

红黑树与其他平衡树的对比

平衡树类型 核心平衡策略 优势 劣势 适用场景
红黑树 颜色规则 + 有限旋转 旋转操作少，插入删除效率高 平衡精度低于 AVL 树 集合类（TreeMap）、数据库索引
AVL 树 左右子树高度差≤1 严格平衡，查询效率略高 旋转操作多，插入删除效率低 查询密集场景

红黑树的应用场景

  • Java 集合：TreeMap、TreeSet底层基于红黑树实现，保证元素有序且操作高效。
  • Linux 内核：进程调度的 CFS（完全公平调度器）用红黑树管理进程优先级。
  • 数据库：部分索引结构（如 SQLite 的 B 树变体）借鉴红黑树的平衡思想。

总结

红黑树通过 “颜色约束” 和 “旋转操作” 实现自平衡，确保树高始终为O(logn)，从而在查询、插入、删除操作中保持O(logn)的稳定效率。其设计兼顾了平衡精度和操作成本，是实际应用中最广泛的平衡树结构之一