红黑树学习笔记

一、红黑树定义

红黑树是一种自平衡的二叉查找树，它通过在每个节点上增加一个颜色属性（红色或黑色）来确保树的高度平衡。为了保证树的平衡性，红黑树必须严格满足以下五条核心性质：

节点颜色限制：每个节点要么是红色，要么是黑色。这是红黑树最基础的颜色属性设定，用于辅助后续的平衡调整。
根节点必须是黑色：树的根节点强制为黑色。这一规则确保了从根节点出发的所有路径在黑色节点计数上有一个统一的基准起点。
所有叶子节点都是黑色：这里的叶子节点通常指的是空节点（NIL节点）。这一性质保证了树的边界条件一致，是维持黑色节点数量平衡的重要基础。
红色节点不能有红色子节点：每个红色节点的两个子节点都必须是黑色。换言之，从任意叶子到根的所有路径上，绝对不能出现两个连续的红色节点。这限制了树在局部区域过度延伸。
黑色高度一致：从任意一个节点出发，到达其所有叶子节点的每一条路径，都必须包含相同数目的黑色节点。这一性质是红黑树保持整体平衡的核心约束，确保了树的左右两侧不会严重失衡。

二、红黑树性质

红黑树通过上述五条性质的约束，保证了树的近似平衡。其最核心的推导性质是：从根节点到叶子节点的最长可能路径，不会超过最短可能路径的两倍长。

原因分析：

最短路径：根据性质5，所有路径的黑色节点数目相同。当路径上没有任何红色节点时，该路径仅由黑色节点组成，此时路径长度最短。
最长路径：根据性质4，不能有两个连续的红色节点。因此，最长路径的情况是红色和黑色节点交替出现。由于根节点是黑色且叶子是黑色，最长路径中红色节点的数量最多等于黑色节点的数量。
结论：最长路径（红黑交替）的长度最多是最短路径（全黑）长度的2倍。

时间复杂度分析：

因为红黑树的高度 h 被严格限制在 O(log n) 级别（n 为节点总数），所以在红黑树上进行查找、插入、删除等基础操作时，其最坏情况下的时间复杂度均被控制在 O(log n)。这避免了普通二叉搜索树在极端情况下退化为链表导致时间复杂度变为 O(n) 的问题。

三、旋转操作详解

旋转操作是红黑树维持平衡的核心物理手段，分为左旋和右旋。旋转操作只改变节点的父子关系，不改变二叉搜索树的中序遍历顺序（即不破坏数据的排序规则）。

左旋（Left Rotation）

原理：将某个节点 x 的右孩子 y 提升为 x 的父节点，x 成为 y 的左孩子，y 原本的左孩子变为 x 的右孩子。

步骤：

将 y 的左孩子挂载到 x 的右孩子位置。
将 y 的父指针指向 x 原来的父节点，并更新 x 原父节点的对应子节点指针。
将 x 的父指针指向 y，将 y 的左孩子指针指向 x。

右旋（Right Rotation）

原理：与左旋完全对称。将某个节点 x 的左孩子 y 提升为 x 的父节点，x 成为 y 的右孩子，y 原本的右孩子变为 x 的左孩子。

步骤：

将 y 的右孩子挂载到 x 的左孩子位置。
将 y 的父指针指向 x 原来的父节点，并更新 x 原父节点的对应子节点指针。
将 x 的父指针指向 y，将 y 的右孩子指针指向 x。

Java 代码实现

// 左旋操作
private void leftRotate(Node x) {
    // 1. 获取 x 的右孩子 y
    Node y = x.right;
    
    // 2. 将 y 的左孩子变成 x 的右孩子
    x.right = y.left;
    if (y.left != null) {
        y.left.parent = x;
    }
    
    // 3. 将 y 的父指针指向 x 的父节点
    y.parent = x.parent;
    if (x.parent == null) {
        // 如果 x 是根节点，则 y 成为新的根节点
        this.root = y;
    } else if (x == x.parent.left) {
        // 如果 x 是左孩子，将 y 挂载为左孩子
        x.parent.left = y;
    } else {
        // 如果 x 是右孩子，将 y 挂载为右孩子
        x.parent.right = y;
    }
    
    // 4. 将 x 作为 y 的左孩子
    y.left = x;
    x.parent = y;
}

// 右旋操作
private void rightRotate(Node x) {
    // 1. 获取 x 的左孩子 y
    Node y = x.left;
    
    // 2. 将 y 的右孩子变成 x 的左孩子
    x.left = y.right;
    if (y.right != null) {
        y.right.parent = x;
    }
    
    // 3. 将 y 的父指针指向 x 的父节点
    y.parent = x.parent;
    if (x.parent == null) {
        // 如果 x 是根节点，则 y 成为新的根节点
        this.root = y;
    } else if (x == x.parent.left) {
        // 如果 x 是左孩子，将 y 挂载为左孩子
        x.parent.left = y;
    } else {
        // 如果 x 是右孩子，将 y 挂载为右孩子
        x.parent.right = y;
    }
    
    // 4. 将 x 作为 y 的右孩子
    y.right = x;
    x.parent = y;
}

四、插入操作详解

红黑树的插入操作是在普通二叉搜索树插入的基础上，增加颜色标记和平衡修复过程。新插入的节点默认被涂为红色（因为插入红色节点不会破坏性质5的黑色高度一致性，只会可能破坏性质4）。

1. 被插入的节点是根节点

处理策略：直接将此节点涂为黑色。

说明：满足性质2（根节点必须是黑色），插入结束。

2. 被插入节点的父节点是黑色

处理策略：直接将新节点涂为红色，无需其他操作。

说明：新节点为红色，父节点为黑色，不违反性质4；路径上的黑色节点数量未改变，不违反性质5。树依然合法。

3. 被插入节点的父节点是红色

此时违反了性质4（不能有两个连续的红色节点），需要进行修复。设当前插入节点为 cur，父节点为 parent，祖父节点为 grandpa，叔叔节点为 uncle。

情况 3.1：叔叔节点也是红色

处理策略：

将父节点设为黑色。
将叔叔节点设为黑色。
将祖父节点设为红色。
将祖父节点设为新的"当前节点"，向上递归继续检查修复。

说明：通过变色解决了局部的双红冲突，但祖父节点变红可能导致更上层的冲突，因此需要向上迭代。

情况 3.2：叔叔节点是黑色，且当前节点是其父节点的右孩子

处理策略：

将父节点作为新的当前节点。
以新的当前节点为支点进行左旋。

说明：这是典型的"右-右"或"右-左"形态的过渡状态，通过左旋将其转化为情况 3.3 的形态。

情况 3.3：叔叔节点是黑色，且当前节点是其父节点的左孩子

处理策略：

将父节点设为黑色。
将祖父节点设为红色。
以祖父节点为支点进行右旋。

说明：通过变色和右旋，彻底解决了双红冲突，且右旋后原本红色的父节点占据了祖父节点的位置，保证了黑色高度不变，修复结束。（注：若初始为右孩子，则对应左旋，逻辑完全对称）。

五、红黑树插入完整Java实现

public class RedBlackTree {
    // 定义节点颜色常量
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    // 节点内部类
    private static class Node {
        int key;            // 节点存储的值
        Node left;          // 左子节点
        Node right;         // 右子节点
        Node parent;        // 父节点
        boolean color;      // 节点颜色

        Node(int key) {
            this.key = key;
            this.color = RED; // 新插入的节点默认设为红色
        }
    }

    private Node root; // 树的根节点

    /**
     * 对外暴露的插入方法
     */
    public void insert(int key) {
        Node newNode = new Node(key);
        Node parent = null;
        Node current = this.root;

        // 1. 标准的二叉搜索树插入过程，寻找插入位置
        while (current != null) {
            parent = current;
            if (key < current.key) {
                current = current.left;
            } else if (key > current.key) {
                current = current.right;
            } else {
                return; // 假设不允许重复键，直接返回
            }
        }

        // 2. 建立父子关系
        newNode.parent = parent;
        if (parent == null) {
            this.root = newNode; // 插入的是根节点
        } else if (key < parent.key) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }

        // 3. 插入后调整红黑树性质
        insertFixUp(newNode);
    }

    /**
     * 插入后的红黑树平衡修复方法
     */
    private void insertFixUp(Node node) {
        // 当父节点存在且父节点为红色时，才需要修复
        while (node.parent != null && node.parent.color == RED) {
            Node grandpa = node.parent.parent; // 获取祖父节点
            
            // 父节点是祖父节点的左孩子
            if (node.parent == grandpa.left) {
                Node uncle = grandpa.right; // 获取叔叔节点
                
                // 情况1：叔叔节点是红色
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;   // 父节点变黑
                    uncle.color = BLACK;         // 叔叔节点变黑
                    grandpa.color = RED;         // 祖父节点变红
                    node = grandpa;              // 将祖父节点作为当前节点，向上继续修复
                } 
                // 情况2和3：叔叔节点是黑色或为空
                else {
                    // 情况2：当前节点是父节点的右孩子，先左旋转化为情况3
                    if (node == node.parent.right) {
                        node = node.parent;
                        leftRotate(node);
                    }
                    // 情况3：当前节点是父节点的左孩子
                    node.parent.color = BLACK;   // 父节点变黑
                    grandpa.color = RED;         // 祖父节点变红
                    rightRotate(grandpa);        // 对祖父节点进行右旋
                }
            } 
            // 父节点是祖父节点的右孩子（与上述逻辑完全对称）
            else {
                Node uncle = grandpa.left;
                
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    grandpa.color = RED;
                    node = grandpa;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rightRotate(node);
                    }
                    node.parent.color = BLACK;
                    grandpa.color = RED;
                    leftRotate(grandpa);
                }
            }
        }
        // 循环结束后，确保根节点始终为黑色
        this.root.color = BLACK;
    }

    // 左旋方法
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != null) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.left = x;
        x.parent = y;
    }

    // 右旋方法
    private void rightRotate(Node x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != null) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.left) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }
        y.right = x;
        x.parent = y;
    }
}

六、红黑树核心知识点总结对照表

分类	核心知识点	详细说明/修复策略
定义性质	颜色与根节点	节点非红即黑；根节点必须是黑色
定义性质	叶子与双红限制	所有NIL叶子为黑色；不能有两个连续的红色节点
定义性质	黑色高度一致	任意节点到其所有叶子的路径包含相同数目的黑色节点
推导性质	路径长度限制	最长路径 ≤ 2 × 最短路径
推导性质	时间复杂度	查找、插入、删除的最坏时间复杂度均为 O(log n)
插入修复	根节点插入	直接将新节点涂为黑色
插入修复	父节点为黑色	新节点涂红即可，无需调整
插入修复	父红叔红	父、叔变黑，祖父变红，祖父作为当前节点向上迭代
插入修复	父红叔黑(外侧)	父变黑，祖父变红，以祖父为支点进行反向旋转（如父在左则右旋）
插入修复	父红叔黑(内侧)	以父节点为支点进行同向旋转，转化为"外侧"情况后继续处理

七、学习要点归纳

深刻理解五大性质：红黑树的所有操作都是为了维护这五条性质，特别是性质4（无双红）和性质5（黑色高度一致），它们是推导最长路径不超过两倍以及所有修复策略的根本依据。
掌握旋转的本质：左旋和右旋只是改变了节点的物理拓扑结构，并没有改变二叉搜索树的逻辑顺序。旋转的目的是将"内侧"的冲突转化为"外侧"的冲突，以便通过一次旋转彻底解决。
明确插入默认颜色：新节点必须插入为红色。如果插入为黑色，会直接破坏性质5（黑色高度一致），导致整棵树的所有路径都需要重新计算和修复，代价极其高昂。
理清修复的对称性：红黑树的插入修复逻辑高度对称。当父节点是祖父的左孩子时，对应的叔叔在右侧，需要右旋；反之亦然。掌握一侧的逻辑后，另一侧只需镜像处理即可。
代码实现的边界处理：在编写Java代码时，务必注意空指针异常（NullPointerException）。在访问叔叔节点、祖父节点或进行旋转时，必须先判断节点是否为 null，尤其是处理根节点变更时，要同步更新树的根引用。