前言

树形结构是计算机科学中最重要的数据结构之一，它在查找、排序、索引等场景中发挥着不可替代的作用。本文将从最基础的二叉树开始，逐步深入到二叉查找树、平衡二叉树，最终解析红黑树的设计原理与 Java 实现，帮助你理解树形结构的演进逻辑与应用场景。

一、二叉树：树形结构的基石

1.1 什么是二叉树？

二叉树是一种每个节点最多拥有两个子节点的树形结构，这两个子节点分别被称为左子节点和右子节点。与线性结构（如数组、链表）相比，二叉树的非线性特性使其在数据检索时具有更高的效率潜力。

二叉树的基本性质：

• 第 i 层最多有 2^(i-1) 个节点
• 深度为 k 的二叉树最多有 2^k - 1 个节点
• 对于任意一棵二叉树，叶子节点数 = 度为 2 的节点数 + 1

1.2 二叉树的 Java 实现

public class TreeNode {
    int val;
    TreeNode left;  // 左子节点
    TreeNode right; // 右子节点

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

// 二叉树基本操作类
public class BinaryTree {
    private TreeNode root;

    // 前序遍历：根->左->右
    public void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // 中序遍历：左->根->右
    public void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.left);
            System.out.print(node.val + " ");
            inOrder(node.right);
        }
    }

    // 后序遍历：左->右->根
    public void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.val + " ");
        }
    }

    // 层序遍历（广度优先）
    public void levelOrder() {
        if (root == null) return;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");
            
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

1.3 二叉树的局限性

普通二叉树没有对节点值的排布规则，导致其查找效率不稳定（最好 O (logn)，最坏 O (n)）。例如，当所有节点都只有右子节点时，二叉树会退化为单链表，完全失去树形结构的优势。

二、二叉查找树（BST）：有序的二叉树

2.1 BST 的定义与特性

二叉查找树（Binary Search Tree）在二叉树基础上增加了节点值的排序规则：

• 左子树所有节点的值 < 当前节点的值
• 右子树所有节点的值 > 当前节点的值
• 左右子树也必须是二叉查找树

这一特性使得 BST 的中序遍历结果是严格递增的有序序列，为高效查找奠定了基础。

2.2 BST 的核心操作

public class BST {
    private TreeNode root;

    // 查找操作
    public TreeNode search(int val) {
        TreeNode current = root;
        while (current != null) {
            if (val == current.val) {
                return current; // 找到目标节点
            } else if (val < current.val) {
                current = current.left; // 向左子树查找
            } else {
                current = current.right; // 向右子树查找
            }
        }
        return null; // 未找到
    }

    // 插入操作
    public void insert(int val) {
        TreeNode newNode = new TreeNode(val);
        if (root == null) {
            root = newNode;
            return;
        }

        TreeNode parent = null;
        TreeNode current = root;
        // 找到插入位置
        while (current != null) {
            parent = current;
            if (val < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        // 插入新节点
        if (val < parent.val) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
    }

    // 删除操作（最复杂的操作）
    public boolean delete(int val) {
        TreeNode parent = null;
        TreeNode current = root;
        boolean isLeftChild = false;

        // 查找目标节点及其父节点
        while (current != null && current.val != val) {
            parent = current;
            if (val < current.val) {
                current = current.left;
                isLeftChild = true;
            } else {
                current = current.right;
                isLeftChild = false;
            }
        }

        if (current == null) return false; // 未找到目标节点

        // 情况1：叶子节点
        if (current.left == null && current.right == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // 情况2：只有一个子节点
        else if (current.right == null) {
            if (current == root) {
                root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } else if (current.left == null) {
            if (current == root) {
                root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        // 情况3：有两个子节点（找中序后继替换）
        else {
            TreeNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            successor.left = current.left; // 继承左子树
        }
        return true;
    }

    // 获取中序后继（右子树的最小值）
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode successorParent = node;
        TreeNode successor = node;
        TreeNode current = node.right;

        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 如果后继不是直接右子节点，需要调整关系
        if (successor != node.right) {
            successorParent.left = successor.right;
            successor.right = node.right;
        }
        return successor;
    }
}

2.3 BST 的性能分析

• 理想情况下（平衡状态）：查找、插入、删除的时间复杂度均为O(logn)
• 最坏情况下（退化为单链表）：时间复杂度退化至O(n)

这种不稳定性促使人们设计出更可靠的平衡树形结构。

三、平衡二叉树：解决 BST 的失衡问题

3.1 什么是平衡二叉树？

平衡二叉树（Balanced Binary Tree）是一类左右子树高度差不超过 1的二叉查找树。最经典的实现是AVL 树（以发明者 Adelson-Velsky 和 Landis 命名）。

平衡因子：节点的左子树高度减去右子树高度（取值范围 {-1, 0, 1}）

3.2 AVL 树的核心：旋转操作

当插入或删除节点导致树失衡时，AVL 树通过旋转操作恢复平衡。旋转分为四种基本类型：

1.LL 旋转（左左旋转）：右单旋

private TreeNode llRotate(TreeNode node) {
    TreeNode leftChild = node.left;
    node.left = leftChild.right;  // 左孩子的右子树成为当前节点的左子树
    leftChild.right = node;       // 当前节点成为左孩子的右子树
    
    // 更新高度
    node.height = calculateHeight(node);
    leftChild.height = calculateHeight(leftChild);
    return leftChild;  // 左孩子成为新的根节点
}

2.RR 旋转（右右旋转）：左单旋

private TreeNode rrRotate(TreeNode node) {
    TreeNode rightChild = node.right;
    node.right = rightChild.left;  // 右孩子的左子树成为当前节点的右子树
    rightChild.left = node;        // 当前节点成为右孩子的左子树
    
    // 更新高度
    node.height = calculateHeight(node);
    rightChild.height = calculateHeight(rightChild);
    return rightChild;  // 右孩子成为新的根节点
}

3.LR 旋转（左右旋转）：先左后右双旋

private TreeNode lrRotate(TreeNode node) {
    node.left = rrRotate(node.left);  // 先对左孩子进行RR旋转
    return llRotate(node);            // 再对当前节点进行LL旋转
}

4.RL旋转（右左旋转）：先右后左双旋

private TreeNode rlRotate(TreeNode node) {
    node.right = llRotate(node.right);  // 先对右孩子进行LL旋转
    return rrRotate(node);              // 再对当前节点进行RR旋转
}

3.3 AVL 树的插入实现

public class AVLTree {
    private class AVLNode {
        int val;
        int height; // 节点高度
        AVLNode left;
        AVLNode right;

        public AVLNode(int val) {
            this.val = val;
            this.height = 1; // 新节点高度初始为1
        }
    }

    private AVLNode root;

    // 计算节点高度
    private int height(AVLNode node) {
        return node == null ? 0 : node.height;
    }

    // 计算平衡因子
    private int balanceFactor(AVLNode node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    // 更新节点高度
    private void updateHeight(AVLNode node) {
        node.height = 1 + Math.max(height(node.left), height(node.right));
    }

    // 插入节点
    public void insert(int val) {
        root = insert(root, val);
    }

    private AVLNode insert(AVLNode node, int val) {
        // 1. 执行普通BST插入
        if (node == null) {
            return new AVLNode(val);
        }

        if (val < node.val) {
            node.left = insert(node.left, val);
        } else if (val > node.val) {
            node.right = insert(node.right, val);
        } else {
            return node; // 不允许重复值
        }

        // 2. 更新当前节点高度
        updateHeight(node);

        // 3. 计算平衡因子，检查是否失衡
        int bf = balanceFactor(node);

        // 4. 根据失衡类型进行旋转
        // LL型：左左失衡
        if (bf > 1 && val < node.left.val) {
            return llRotate(node);
        }
        // RR型：右右失衡
        if (bf < -1 && val > node.right.val) {
            return rrRotate(node);
        }
        // LR型：左右失衡
        if (bf > 1 && val > node.left.val) {
            return lrRotate(node);
        }
        // RL型：右左失衡
        if (bf < -1 && val < node.right.val) {
            return rlRotate(node);
        }

        return node;
    }

    // 旋转方法（LL、RR、LR、RL）见上文
    private AVLNode llRotate(AVLNode node) { ... }
    private AVLNode rrRotate(AVLNode node) { ... }
    private AVLNode lrRotate(AVLNode node) { ... }
    private AVLNode rlRotate(AVLNode node) { ... }
}

3.4 AVL 树的优缺点

• 优点：严格保证平衡，查询效率稳定在 O (logn)
• 缺点：维护成本高，频繁插入删除时旋转操作过多，适用于查询密集场景

四、红黑树：平衡与性能的折中

4.1 红黑树的定义

红黑树是一种自平衡二叉查找树，它通过颜色规则（红或黑）和特定操作维持树的平衡，相比 AVL 树，它的旋转操作更少，插入删除性能更优。

红黑树的五大规则：

1. 每个节点不是红色就是黑色
2. 根节点必须是黑色
3. 所有叶子节点（NIL 节点）都是黑色
4. 如果一个节点是红色，它的两个子节点必须是黑色（不允许连续红节点）
5. 从任意节点到其所有后代叶子节点的路径，都包含相同数量的黑色节点

这些规则确保了红黑树的最长路径不超过最短路径的 2 倍，从而维持了近似平衡。

4.2 红黑树的核心操作

红黑树的平衡维护主要通过两种操作：旋转（与 AVL 树类似）和变色（改变节点颜色）。

4.2.1 节点结构定义

public class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        int val;
        Node left, right, parent;
        boolean color;

        public Node(int val) {
            this.val = val;
            this.color = RED; // 新节点默认红色
            this.left = null;
            this.right = null;
            this.parent = null;
        }
    }

    private Node root;
    private Node nil; // 哨兵节点，代表所有叶子节点和空指针

    public RedBlackTree() {
        nil = new Node(0);
        nil.color = BLACK;
        root = nil;
    }
}

4.2.2 插入后的修复

新节点默认红色，插入后可能违反规则 4（连续红节点），需要通过修复恢复平衡：

private void insertFixup(Node z) {
    while (z.parent.color == RED) { // 父节点为红色才可能违反规则
        if (z.parent == z.parent.parent.left) {
            Node y = z.parent.parent.right; // 叔节点
            
            // 情况1：叔节点为红色（变色解决）
            if (y.color == RED) {
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent; // 继续向上检查
            } else {
                // 情况2：叔节点为黑色，且当前节点是右孩子（先旋转为情况3）
                if (z == z.parent.right) {
                    z = z.parent;
                    leftRotate(z);
                }
                // 情况3：叔节点为黑色，且当前节点是左孩子（旋转+变色）
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                rightRotate(z.parent.parent);
            }
        } else {
            // 镜像情况（父节点是右孩子）
            Node y = z.parent.parent.left; // 叔节点
            
            if (y.color == RED) {
                // 情况1镜像
                z.parent.color = BLACK;
                y.color = BLACK;
                z.parent.parent.color = RED;
                z = z.parent.parent;
            } else {
                // 情况2镜像
                if (z == z.parent.left) {
                    z = z.parent;
                    rightRotate(z);
                }
                // 情况3镜像
                z.parent.color = BLACK;
                z.parent.parent.color = RED;
                leftRotate(z.parent.parent);
            }
        }
    }
    root.color = BLACK; // 确保根节点为黑色
}

// 左旋转
private void leftRotate(Node x) {
    Node y = x.right;
    x.right = y.left;
    
    if (y.left != nil) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    
    if (x.parent == nil) {
        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 y) { ... }

4.3 红黑树的性能分析

• 查找、插入、删除的时间复杂度均为O(logn)
• 相比 AVL 树，红黑树旋转次数更少（插入最多 2 次旋转，删除最多 3 次旋转）
• 空间复杂度 O (n)，主要用于存储节点和颜色信息

4.4 红黑树的应用场景

红黑树在 Java 中的应用非常广泛：

• TreeMap 和 TreeSet 的底层实现
• HashMap 在 JDK 1.8 中当链表长度超过 8 时转为红黑树
• ConcurrentHashMap 中的节点组织
• Linux 内核中的进程调度（CFS）

五、树形结构对比与总结

结构类型	平衡条件	查找效率	插入 / 删除效率	适用场景
二叉树	无	O(n)	O(n)	基础结构，无实际应用
二叉查找树	无（有序）	O(logn)~O(n)	O(logn)~O(n)	数据分布均匀且稳定的场景
AVL 树	左右子树高度差≤1	O(logn)	O(logn)	查询密集，插入删除少的场景
红黑树	红黑规则（近似平衡）	O(logn)	O(logn)	插入删除频繁的场景（如集合）

总结：从二叉树到红黑树的演进，本质上是对查找效率和维护成本的不断平衡。红黑树凭借其优秀的综合性能，成为 Java 集合框架中最常用的平衡树结构，理解它的设计思想对于深入掌握 Java 底层原理至关重要。

希望本文能帮助你建立对树形结构的系统认知，后续可以尝试实现一个完整的红黑树，或者研究 B 树、B + 树等多路平衡树的设计原理。