【数据结构与算法体系】树

一、二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一棵二叉树，且满足：对于任意节点，其左子树中所有节点的值小于该节点的值，右子树中所有节点的值大于该节点的值。BST支持高效的动态集合操作——查找、插入和删除的平均时间复杂度为O(log N)，但最坏情况（树退化为链表）为O(N)。

BST的查找操作从根节点开始：如果目标值等于当前节点则返回；如果目标值小于当前节点，进入左子树继续查找；如果大于，进入右子树。插入操作类似：找到合适的位置（一个空的子节点位置）后创建新节点。删除操作最复杂，需要分三种情况：被删除节点是叶子节点（直接删除）、被删除节点只有一个子节点（用子节点替代）、被删除节点有两个子节点（找到后继节点——右子树的最小节点，用其值替换被删除节点，然后删除后继节点）。

class BSTNode {
    int key;
    BSTNode left, right;
}

// 查找
BSTNode search(BSTNode root, int key) {
    if (root == null || root.key == key) return root;
    return key < root.key ? search(root.left, key) : search(root.right, key);
}

// 插入（递归）
BSTNode insert(BSTNode root, int key) {
    if (root == null) return new BSTNode(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root; // 键已存在则忽略
}

// 删除
BSTNode delete(BSTNode root, int key) {
    if (root == null) return null;
    if (key < root.key) {
        root.left = delete(root.left, key);
    } else if (key > root.key) {
        root.right = delete(root.right, key);
    } else {
        // 找到要删除的节点
        if (root.left == null) return root.right;  // 情况1和2a
        if (root.right == null) return root.left;  // 情况2b
        // 情况3：有两个子节点
        BSTNode successor = findMin(root.right);
        root.key = successor.key;
        root.right = delete(root.right, successor.key);
    }
    return root;
}

BSTNode findMin(BSTNode node) {
    while (node.left != null) node = node.left;
    return node;
}

BST的实用价值在于中序遍历可以得到有序序列（O(N)时间输出所有键的升序排列）。Java的TreeMap和TreeSet底层使用红黑树（一种自平衡BST），提供了O(log N)保证的操作和有序遍历能力。

二、AVL树

AVL树（以发明者Adelson-Velsky和Landis命名）是最早的自平衡二叉搜索树，它规定任意节点的左右子树高度差（平衡因子）不超过1。当插入或删除操作导致某节点的平衡因子变为2或-2时，通过旋转（Rotation）恢复平衡。

四种旋转情形：

LL情形（左子树的左子节点插入导致失衡）：对失衡节点进行右旋（Right Rotate）。想象以失衡节点为支点，将其左子节点向上提升，原左子节点的右子树成为原失衡节点的左子树。

RR情形（右子树的右子节点插入导致失衡）：对失衡节点进行左旋（Left Rotate），是LL的镜像。

LR情形（左子树的右子节点插入导致失衡）：先对失衡节点的左子节点进行左旋（转化为LL），再对失衡节点进行右旋。即“双旋”。

RL情形（右子树的左子节点插入导致失衡）：先对失衡节点的右子节点进行右旋（转化为RR），再对失衡节点进行左旋。

class AVLNode {
    int key, height;
    AVLNode left, right;
}

int height(AVLNode node) {
    return node == null ? 0 : node.height;
}

int balanceFactor(AVLNode node) {
    return height(node.left) - height(node.right);
}

AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    return x;
}

AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = Math.max(height(x.left), height(x.right)) + 1;
    y.height = Math.max(height(y.left), height(y.right)) + 1;
    return y;
}

AVLNode insert(AVLNode node, int key) {
    if (node == null) return new AVLNode(key);
    
    if (key < node.key) node.left = insert(node.left, key);
    else if (key > node.key) node.right = insert(node.right, key);
    else return node; // 重复键
    
    node.height = 1 + Math.max(height(node.left), height(node.right));
    int balance = balanceFactor(node);
    
    // LL
    if (balance > 1 && key < node.left.key) return rightRotate(node);
    // RR
    if (balance < -1 && key > node.right.key) return leftRotate(node);
    // LR
    if (balance > 1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    // RL
    if (balance < -1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

AVL树由于平衡条件严格（高度差≤1），查找性能最优。但在频繁插入删除的场景中，维护严格平衡需要较多的旋转操作。红黑树通过放宽平衡条件（最长路径不超过最短路径的两倍）减少了旋转次数，成为更实用的选择。

三、红黑树

红黑树（Red-Black Tree）是Java TreeMap、Linux CFS调度器、epoll事件管理、C++ std::map等众多系统的底层数据结构。它是一棵自平衡二叉搜索树，通过以下五个性质保证平衡：

每个节点是红色或黑色。
根节点是黑色。
每个叶子节点（NIL，空节点）是黑色。
如果一个节点是红色，则它的两个子节点都是黑色（不能有两个连续的红色节点）。
从任意节点到其所有后代叶子节点的路径上，黑色节点的数量相同（黑高一致）。

性质4和5共同保证了：最长路径（红黑交替）的长度不超过最短路径（全黑）的两倍。因此红黑树的高度最多为2 log₂(N+1)，确保了O(log N)的操作复杂度。

插入修复：新插入的节点着红色（尽量不破坏黑高）。如果插入节点的父节点是黑色，无需任何修复。如果父节点是红色（违反性质4），需要根据叔节点的颜色分情况处理：（1）叔节点为红色——父节点和叔节点变黑，祖父节点变红，问题上移到祖父节点递归处理。（2）叔节点为黑色且当前节点为父节点的“内侧”子节点（如父节点是祖父节点的左孩子，当前节点是父节点的右孩子）——对父节点旋转将其转为外侧情况。（3）叔节点为黑色且当前节点为“外侧”子节点——对祖父节点旋转并重新着色。最多进行2次旋转即可完成插入修复（不像AVL树可能需要O(log N)次旋转）。

删除修复比插入更复杂，但核心思想一致：通过旋转和着色，保持红黑树的五个性质。删除修复最多需要3次旋转。

红黑树与AVL树的对比：AVL树更严格平衡，查找稍快；红黑树插入删除的旋转次数更少（常数次 vs 对数次），写入密集型场景下性能更优。Java的TreeMap选择红黑树正是因为它在读写混合场景下的综合性能最优。

四、B树与B+树

B树（B-Tree）是为磁盘存储优化的多路搜索树，广泛应用于数据库和文件系统中。B树的“B”通常被认为代表Balanced（平衡）或Bayer（发明者）。

B树的关键特性：每个节点可以包含多个键（而不是BST的1个键）。一个度为t的B树具有以下性质：（1）除根节点外，每个节点至少有t-1个键（半满以上）。（2）每个节点最多有2t-1个键（满节点）。（3）节点有n个键时，恰好有n+1个子节点。例如，t=100时每个节点可存储99到199个键，200到400个子节点。这意味着树的高度极低——存储十亿个键只需要log₁₀₀(10⁹) ≈ 4到5层。由于每次磁盘I/O读取一个整个节点（节点大小通常等于磁盘页大小，如4KB或16KB），极低的高度意味着极少的磁盘I/O次数。

B+树是B树的变体，是MySQL InnoDB存储引擎的默认索引结构。B+树与B树的区别：（1）所有实际数据只存储在叶子节点中，非叶子节点（内部节点）只存储键作为索引。（2）叶子节点之间通过指针连接成有序链表，支持高效的范围查询——找到起始键后，沿着叶子节点的链表顺序扫描即可，不需要回到上层节点。（3）内部节点的键可以重复出现在叶子节点中。B+树的这些设计使得它对范围查询（如SELECT * FROM t WHERE id BETWEEN 100 AND 200）和顺序扫描（全表扫描）极为高效。

B+树在数据库中的实际应用：InnoDB中，主键索引（聚簇索引）的叶子节点直接存储完整的数据行；二级索引（非聚簇索引）的叶子节点存储的是主键值，查询需要“回表”（通过主键再到主键索引中查一次获取完整行）。因此InnoDB强烈建议使用自增主键，因为顺序插入避免了页分裂，减少了碎片。

五、Trie（前缀树）

Trie（前缀树/字典树，发音为“try”）是用于高效存储和查找字符串集合的树形数据结构。每个节点代表一个字符串前缀，边代表一个字符。从根到某个节点的路径连接成的字符串即是该节点对应的前缀。节点标记为“终止节点”表示从根到该节点的字符串属于集合。

Trie的优势：（1）查找时间复杂度为O(L)，L为查询字符串的长度，与集合的大小无关。（2）前缀查找极其高效——查找所有以某个前缀开始的字符串只需走到前缀对应的节点，然后遍历其子树。（3）Trie自然支持按字典序遍历所有字符串。

class TrieNode {
    TrieNode[] children = new TrieNode[26]; // 假设只有小写字母
    boolean isEnd;
}

class Trie {
    TrieNode root = new TrieNode();
    
    void insert(String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) {
                cur.children[idx] = new TrieNode();
            }
            cur = cur.children[idx];
        }
        cur.isEnd = true;
    }
    
    boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEnd;
    }
    
    boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }
    
    private TrieNode findNode(String s) {
        TrieNode cur = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (cur.children[idx] == null) return null;
            cur = cur.children[idx];
        }
        return cur;
    }
}

Trie在工程中有广泛应用：搜索引擎的自动补全（Autocomplete）——用户输入前缀后，在Trie中定位到对应节点，遍历其子树获取热门搜索建议（通常结合Top K和频率信息）。IP路由表的最长前缀匹配——路由器的FIB（转发表）使用压缩Trie（Patricia Trie / Radix Tree）存储IP前缀。拼写检查——Trie可以快速判断一个单词是否在词典中，结合编辑距离可以给出修正建议。T9输入法——手机按键映射为Trie，实现智能输入预测。

Trie的内存开销较大（每个节点的指针数组，即使是稀疏的），在实际应用中有多种压缩优化：Radix Tree（压缩连续的无分叉路径为一个节点）、Ternary Search Tree（每个节点只有三个子节点指针，空间效率高但查找慢）、Double-Array Trie（将Trie压缩为两个数组，是日语分词等NLP应用的经典实现）。

六、Java TreeMap红黑树源码分析

Java的TreeMap底层是一棵红黑树。每个Entry包含：key, value, left, right, parent, color（布尔值，true表示黑色）。TreeMap的核心源码要点：

put操作：按照BST规则找到插入位置，新节点设为红色。调用fixAfterInsertion()进行旋转和着色修复。该修复循环至多log N次迭代，当父节点为黑色或到达根时停止。

get操作：标准的BST查找。每次比较key与当前节点（使用Comparator或Comparable），决定向左或向右。由于红黑树的高度为O(log N)，get时间复杂度为O(log N)。

ceiling/floor操作：查找大于等于/小于等于给定key的最小/最大键。在O(log N)时间内完成。

successor操作：查找中序遍历的下一个节点。如果节点有右子树，后继是右子树的最小节点；否则，后继是从该节点向上回溯找到的第一个“当前节点是父节点的左孩子”的父节点。红黑树的有序性使得TreeMap可以高效地实现范围查询（subMap(), headMap(), tailMap()）。

七、面试常见追问

问题一：红黑树 vs AVL树在实际中如何选择？

AVL树由于更严格的平衡（高度差≤1），查找操作略快于红黑树。但在插入和删除密集的场景中，AVL树每次操作可能需要进行O(log N)次旋转，而红黑树最多只需要O(1)次旋转（插入最多2次，删除最多3次）。因此，对于读多写少的场景（如字典、配置管理），AVL树更合适；对于读写混合或写频繁的场景（如Java的TreeMap在通用场景中使用），红黑树综合更优。Java标准库选择红黑树，C++的std::map也使用红黑树，说明红黑树在实际应用中的综合表现更受认可。

问题二：为什么数据库索引使用B+树而不是红黑树？

核心原因是磁盘I/O特性。B+树的每个节点可以存储数百个键（节点大小对应磁盘页，如16KB），使得树的高度极低——十亿条数据也只需4到5层。红黑树是二叉树，高度为log₂(10⁹) ≈ 30层，需要约30次磁盘I/O（如果节点不在内存中）。B+树的4次I/O vs 红黑树的30次I/O，性能差距巨大。此外，B+树的叶子节点链表支持高效的范围查询——找到起始点后顺序扫描即可，红黑树的范围查询需要一直在树上回溯。

问题三：Trie在实际应用中如何优化内存？

标准Trie的每个节点有26或52个子节点指针（字母表大小），空间浪费严重。优化方法：（1）压缩Trie（Radix Tree）：将没有分叉的路径合并为一个节点，存储完整的子串而非单个字符。（2）三叉搜索树（Ternary Search Tree）：每个节点只存一个字符和三个子指针（小于、等于、大于），将Trie的空间从O(N×字母表大小)降到O(N)。（3）Double-Array Trie：用两个整数数组表示Trie（Base数组和Check数组），日本的MeCab分词器等工具使用它。（4）Bitmap + 动态数组：对于稀疏的子节点，用一个bitmap记录哪些字符有子节点，再用一个紧凑数组存储实际存在的子节点指针。