三、树形结构的深度剖析

3.1 平衡二叉搜索树——红黑树（Red-Black Tree）
红黑树是Java中TreeMap、TreeSet以及C++ STL中std::map的底层实现。其核心性质保证了树的高度控制在 2×log₂(n+1) 内。

红黑树的五大性质：

每个节点是红色或黑色

根节点是黑色

所有叶子节点（NIL）是黑色

红色节点的两个子节点必须是黑色（不存在两个连续的红色节点）

从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高相同）

左旋与右旋操作

// 左旋（以节点x为支点）
private void leftRotate(Node x) {
    Node y = x.right;        // y是x的右子节点
    x.right = y.left;        // 将y的左子树交给x的右子树

    if (y.left != nil) {
        y.left.parent = x;
    }

    y.parent = x.parent;     // 将y的父节点指向x的父节点

    if (x.parent == nil) {
        root = y;            // x是根节点，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) {
    Node x = y.left;
    y.left = x.right;

    if (x.right != nil) {
        x.right.parent = y;
    }

    x.parent = y.parent;

    if (y.parent == nil) {
        root = x;
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }

    x.right = y;
    y.parent = x;
}

插入后的修复算法

private void fixAfterInsertion(Node x) {
    x.color = RED;

    // 核心：父节点是红色时才需要修复
    while (x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 父节点是祖父节点的左孩子
            Node y = rightOf(parentOf(parentOf(x)));  // 叔叔节点

            if (colorOf(y) == RED) {
                // Case 1：叔叔是红色（颜色翻转）
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                // 叔叔是黑色
                if (x == rightOf(parentOf(x))) {
                    // Case 2：x是右孩子（左旋父节点）
                    x = parentOf(x);
                    leftRotate(x);
                }
                // Case 3：x是左孩子（右旋祖父节点 + 变色）
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rightRotate(parentOf(parentOf(x)));
            }
        } else {
            // 对称情况：父节点是祖父节点的右孩子
            // ... 镜像代码
        }
    }
    root.color = BLACK;
}

3.2 B树与B+树——数据库索引的基石
B树（Balanced Tree）是一种多路平衡查找树，每个节点可以存储多个键值和子节点指针。

B树性质（以阶数m表示）：
每个节点最多有 m 个子节点

根节点至少有 2 个子节点（除非是叶子节点）

非根非叶节点至少有 ⌈m/2⌉ 个子节点

所有叶子节点在同一层

B+树 vs B树：

为什么数据库用B+树而不是二叉搜索树？

磁盘I/O次数：树高更矮（m=1000时，百万数据树高仅2-3层）

预读特性：节点大小匹配磁盘页（通常4KB或16KB）

范围查询：叶子节点链表提供极佳性能

// B+树节点的简化表示
class BPlusTreeNode {
    private int[] keys;              // 键值数组
    private Object[] values;         // 值数组（仅叶子节点）
    private BPlusTreeNode[] children; // 子节点数组（仅内部节点）
    private BPlusTreeNode next;      // 叶子节点链表指针
    private boolean isLeaf;          // 是否为叶子
    private int keyCount;            // 当前键值数量
}

3.3 线段树（Segment Tree）
线段树用于区间查询和区间更新，典型应用：区间和、区间最值、区间GCD。

class SegmentTree {
    private int[] tree;
    private int[] arr;
    private int n;

    public SegmentTree(int[] arr) {
        this.arr = arr;
        this.n = arr.length;
        // 线段树需要4倍空间
        this.tree = new int[4 * n];
        build(1, 0, n - 1);
    }

    // 构建线段树（递归）
    private void build(int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = (start + end) / 2;
        int leftChild = node * 2;
        int rightChild = node * 2 + 1;

        build(leftChild, start, mid);
        build(rightChild, mid + 1, end);

        // 合并（这里以求和为例）
        tree[node] = tree[leftChild] + tree[rightChild];
    }

    // 区间查询 [l, r]
    public int query(int l, int r) {
        return query(1, 0, n - 1, l, r);
    }

    private int query(int node, int start, int end, int l, int r) {
        // 完全无交集
        if (r < start || l > end) {
            return 0;  // 求和时返回0，最小值返回INF，最大值返回-INF
        }
        // 完全包含
        if (l <= start && end <= r) {
            return tree[node];
        }
        // 部分重叠
        int mid = (start + end) / 2;
        int leftSum = query(node * 2, start, mid, l, r);
        int rightSum = query(node * 2 + 1, mid + 1, end, l, r);
        return leftSum + rightSum;
    }

    // 单点更新
    public void update(int idx, int value) {
        update(1, 0, n - 1, idx, value);
    }

    private void update(int node, int start, int end, int idx, int value) {
        if (start == end) {
            arr[idx] = value;
            tree[node] = value;
            return;
        }
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(node * 2, start, mid, idx, value);
        } else {
            update(node * 2 + 1, mid + 1, end, idx, value);
        }
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    // 延迟更新（懒标记）—— 适用于区间增加
    private int[] lazy;  // 懒标记数组

    public void rangeAdd(int l, int r, int delta) {
        rangeAdd(1, 0, n - 1, l, r, delta);
    }

    private void rangeAdd(int node, int start, int end, int l, int r, int delta) {
        if (lazy[node] != 0) {
            // 将懒标记下推
            tree[node] += lazy[node] * (end - start + 1);
            if (start != end) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }

        if (r < start || l > end) return;

        if (l <= start && end <= r) {
            tree[node] += delta * (end - start + 1);
            if (start != end) {
                lazy[node * 2] += delta;
                lazy[node * 2 + 1] += delta;
            }
            return;
        }

        int mid = (start + end) / 2;
        rangeAdd(node * 2, start, mid, l, r, delta);
        rangeAdd(node * 2 + 1, mid + 1, end, l, r, delta);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }
}

时间复杂度：建树O(n)，每次查询/更新O(log n)。

3.4 前缀树（Trie / 字典树）
Trie树是处理字符串集合的利器，常用于自动补全、拼写检查、IP路由。

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;
    private int passCount;   // 经过该节点的单词数（用于词频统计）

    public TrieNode() {
        children = new TrieNode[26];  // 小写字母
        isEndOfWord = false;
        passCount = 0;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // 插入单词
    public void insert(String word) {
        TrieNode node = root;
        node.passCount++;
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                node.children[index] = new TrieNode();
            }
            node = node.children[index];
            node.passCount++;
        }
        node.isEndOfWord = true;
    }

    // 查找完整单词
    public boolean search(String word) {
        TrieNode node = searchPrefix(word);
        return node != null && node.isEndOfWord;
    }

    // 查找前缀是否存在
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private TrieNode searchPrefix(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            int index = c - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    // 删除单词（需要谨慎处理，不能简单删除节点）
    public boolean delete(String word) {
        if (!search(word)) return false;
        return deleteHelper(root, word, 0);
    }

    private boolean deleteHelper(TrieNode node, String word, int depth) {
        node.passCount--;
        if (depth == word.length()) {
            node.isEndOfWord = false;
            return node.passCount == 0;  // 如果passCount为0，可以删除该节点
        }
        int index = word.charAt(depth) - 'a';
        boolean shouldDeleteChild = deleteHelper(node.children[index], word, depth + 1);
        if (shouldDeleteChild) {
            node.children[index] = null;
            return node.passCount == 0;
        }
        return false;
    }

    // 获取以prefix为前缀的所有单词（自动补全）
    public List<String> getWordsWithPrefix(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode node = searchPrefix(prefix);
        if (node == null) return result;
        collectWords(node, new StringBuilder(prefix), result);
        return result;
    }

    private void collectWords(TrieNode node, StringBuilder current, List<String> result) {
        if (node.isEndOfWord) {
            result.add(current.toString());
        }
        for (int i = 0; i < 26; i++) {
            if (node.children[i] != null) {
                current.append((char)('a' + i));
                collectWords(node.children[i], current, result);
                current.deleteCharAt(current.length() - 1);
            }
        }
    }
}

空间优化：对于大量长字符串共享前缀的场景，Trie树非常高效；但对于短字符串或随机字符串，可能不如哈希表。
来源：
http://lemci.cn/