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

一、二叉树的遍历与Morris遍历

二叉树是计算机科学中最重要的数据结构之一，掌握各种遍历方式及其性质是理解树的基础。

递归遍历（前序、中序、后序）是二叉树遍历的标准方式。时间复杂度O(N)，空间复杂度O(log N)（递归栈）到O(N)（链状退化）。

迭代遍历使用显式栈模拟递归：

Morris遍历是由Joseph M. Morris提出的使用线索二叉树思想的无栈、O(1)额外空间遍历方法。核心思想：利用叶子节点的空指针（原为null）临时指向其后继节点（中序后继），遍历结束后恢复原状。

Morris中序遍历的步骤：

1. 初始化cur = root
2. 如果cur无左子树：访问cur，cur = cur.right
3. 如果cur有左子树：找到cur在中序下的前驱节点（cur左子树的最右叶子）。如果前驱的right为null：将前驱的right指向cur（建立线索），cur = cur.left。如果前驱的right已经指向cur（说明左子树已遍历完）：将前驱right恢复为null，访问cur，cur = cur.right。

void morrisInorder(TreeNode root) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.left == null) {
            System.out.print(cur.val + " "); // 访问
            cur = cur.right;
        } else {
            TreeNode predecessor = cur.left;
            while (predecessor.right != null && predecessor.right != cur) {
                predecessor = predecessor.right;
            }
            if (predecessor.right == null) {
                predecessor.right = cur; // 建立线索
                cur = cur.left;
            } else {
                predecessor.right = null; // 恢复原状
                System.out.print(cur.val + " "); // 访问
                cur = cur.right;
            }
        }
    }
}

Morris遍历的时间复杂度分析：每条边最多被遍历两次（建立线索时一次，恢复时一次），总时间复杂度O(N)。空间复杂度O(1)。在实际面试中，Morris遍历是少数几个能够惊艳面试官的主题——它展示了在不使用额外空间的情况下遍历二叉树的精妙技巧。

Morris遍历的变体：

• 前序Morris：在第一次到达节点时访问（建立线索时，而非恢复后）
• 后序Morris：最复杂——需要在”恢复线索”时，逆序访问cur.left到predecessor路径上的所有节点（通过反转链表再反转回来实现O(1)空间）

二、二叉搜索树（BST）的完整操作

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

查找（Search）：从根节点开始，比较目标值与当前节点。等于则返回；小于则进入左子树；大于则进入右子树。迭代实现比递归更高效（避免函数调用开销）：

BSTNode search(BSTNode root, int key) {
    while (root != null) {
        if (key == root.key) return root;
        root = (key < root.key) ? root.left : root.right;
    }
    return null;
}

插入（Insert）：像查找一样遍历到null位置，创建新节点插入。BST不保证平衡——插入顺序决定了树的形状。如果将[1, 2, 3, 4, 5]依次插入一颗空BST，将退化为右斜链表。

删除（Delete）：三种情况：

1. 被删除节点是叶子节点：直接删除
2. 被删除节点只有一个子节点：用其子节点替代
3. 被删除节点有两个子节点：找到后继节点（右子树的最小节点，即中序后继），用后继的值替换被删除节点，然后删除后继节点（后继必定只有最多一个子节点，退化为情况1或2）

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

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;
}

// 查找前驱
BSTNode predecessor(BSTNode root, int key) {
    BSTNode pred = null;
    while (root != null) {
        if (key <= root.key) {
            root = root.left;
        } else {
            pred = root;  // 当前节点是候选前驱
            root = root.right;
        }
    }
    return pred;
}

// 查找后继
BSTNode successor(BSTNode root, int key) {
    BSTNode succ = null;
    while (root != null) {
        if (key < root.key) {
            succ = root;  // 当前节点是候选后继
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return succ;
}

前驱/后继的查找算法不需要知道根节点引用：前驱 = 节点左子树的最右叶子（如果有左子树），否则是”从根到该节点的路径上最后一个右拐的祖先”（最近的”该节点处于其右子树”的祖先）。后继对称。

三、AVL树——最严格的平衡树

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

AVL树的高度上界：可以证明，高度为h的AVL树至少拥有F_{h+2}-1个节点（F为斐波那契数）。这意味着 h ≤ 1.44 log₂(N+2)，因此AVL树的操作严格O(log N)。

四种旋转情形：

• LL（左-左）：在左子树的左子节点插入导致。右旋失衡节点。
• RR（右-右）：在右子树的右子节点插入导致。左旋失衡节点。
• LR（左-右）：在左子树的右子节点插入导致。先左旋左子节点（转为LL），再右旋失衡节点。
• RL（右-左）：在右子树的左子节点插入导致。先右旋右子节点（转为RR），再左旋失衡节点。

class AVLNode {
    int key, height;
    AVLNode left, right;
    AVLNode(int key) { this.key = key; this.height = 1; }
}

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

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

void updateHeight(AVLNode node) {
    node.height = 1 + Math.max(height(node.left), height(node.right));
}

AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;
    x.right = y;
    y.left = T2;
    updateHeight(y);
    updateHeight(x);
    return x;
}

AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;
    y.left = x;
    x.right = T2;
    updateHeight(x);
    updateHeight(y);
    return y;
}

AVLNode insert(AVLNode node, int key) {
    // 1. 标准BST插入
    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; // 重复键
    
    // 2. 更新高度
    updateHeight(node);
    
    // 3. 检查平衡并旋转
    int balance = balanceFactor(node);
    
    // LL: 平衡因子>1且插入的键在左子树的左边
    if (balance > 1 && key < node.left.key) return rightRotate(node);
    // RR: 平衡因子<-1且插入的键在右子树的右边
    if (balance < -1 && key > node.right.key) return leftRotate(node);
    // LR: 平衡因子>1且插入的键在左子树的右边
    if (balance > 1 && key > node.left.key) {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }
    // RL: 平衡因子<-1且插入的键在右子树的左边
    if (balance < -1 && key < node.right.key) {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }
    return node;
}

注意：上述insert函数的”判断插入键在左/右”是通过比较key与子节点键值确定的，这在处理重复键时已返回，因此此处是安全的。但更健壮的实现应该保存旧的平衡因子，或在子节点中获取实际平衡因子的符号。

AVL删除：先进行标准BST删除，然后从被删除节点的父节点向上回溯，逐层更新高度并检查平衡因子，执行必要的旋转。删除可能需要O(log N)次旋转（插入最多2次旋转）。这是AVL相比红黑树的主要劣势——写入密集场景下旋转次数更多。

四、红黑树——工业界的默认平衡树

红黑树（Red-Black Tree）是Java TreeMap、Linux CFS调度器、epoll事件管理、C++ std::map、nginx定时器等众多系统的底层数据结构。它通过五个性质保证近似平衡：

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

性质4和5共同保证：最长路径（红黑交替）的长度不超过最短路径（全黑）的两倍。证明：设bh为树的黑高。最短路径全黑，长度=bh。最长路径红黑交替（每两个黑节点之间最多有一个红节点），长度=2×bh。因此树的高度 h ≤ 2 × bh ≤ 2 log₂(N+1)，即O(log N)。

插入操作及其修复：

新节点始终着红色（避免破坏黑高）。修复的核心是处理”红父节点”的违规（性质4），根据叔节点的颜色分三类情况。

情况1：叔节点为红色——父节点和叔节点变黑，祖父节点变红，问题递归上移至祖父节点。

情况2：叔节点为黑色且当前节点为父节点的”内侧子节点”（LR或RL型）——对父节点旋转将问题转化为情况3。

情况3：叔节点为黑色且当前节点为父节点的”外侧子节点”（LL或RR型）——对祖父节点旋转并重新着色父节点和祖父节点，问题解决。

插入最多2次旋转（情况2一次+情况3一次），然后必然结束。这与AVL的O(log N)次旋转形成对比。

删除操作及修复：更复杂。删除红色节点无影响。删除黑色节点会破坏黑高。根据兄弟节点的颜色和兄弟子节点的颜色，分多种情况处理。最多需要3次旋转（与插入不同，删除的修复可能更复杂）。Java TreeMap的deleteEntry方法包含了110+行的删除修复实现。

红黑树 vs AVL树：

维度	AVL树	红黑树
平衡条件	严格（高度差≤1）	宽松（最长≤2倍最短）
高度	~1.44 log N	~2 log N
查找	稍快（树更矮）	略慢
插入旋转次数	最多O(log N)	最多2次
删除旋转次数	最多O(log N)	最多3次
适用场景	读多写少	读写混合/写多

Java的TreeMap选择红黑树正是因为它在读写混合的实际场景中综合性能最优。C++的std::map同样选择红黑树。

语言实现差异：

• Java TreeMap：Entry<K,V>包含key, value, left, right, parent, color（boolean）
• C++ std::map：节点包含parent, left, right, color (enum) + value。使用header节点作为end()标记
• Linux内核rbtree：节点仅包含parent（最低位存储颜色）、左右子节点。极致压缩——通过将颜色位编码在parent指针的最低有效位中（利用对齐保证），省掉了一个字段

五、B树与B+树——为磁盘而生

B树是多路搜索树，专为磁盘/SSD存储而优化。B树的每个节点占据一个磁盘页（Page，通常4KB或16KB），节点内存储多个键值和子节点指针。

度为t的B树（t ≥ 2）：

• 每个节点（除根节点）至少t-1个键（半满/最小占用原则），最多2t-1个键（满）
• 有k个键的节点恰好有k+1个子节点
• 所有叶子节点在同一层（完美平衡）

选择t使得节点大小 ≈ 磁盘页大小。例如，如果键+值+指针每个条目128字节，页大小4KB，则2t-1 ≈ 4096/128 ≈ 32，t ≈ 16。这意味着每个节点有17到33个子节点，树的高度 log_17(N) 非常低——十亿条记录只需约log_17(10^9) ≈ 7层（即7次磁盘I/O）。

B树的操作：

插入：找到对应的叶子节点。如果节点未满，直接插入。如果节点已满（2t-1个键），在插入前分裂——将中间键提升到父节点，剩余键分成两个各含t-1个键的新节点。如果父节点也满，递归向上分裂。根节点分裂时树的高度+1。

删除：比插入更复杂。确保在删除路径上的每个节点至少有t个键（而非最小t-1），这样删除后仍满足t-1的下界。通过从富有的兄弟节点”借用”键或与兄弟节点”合并”来维持这个性质。

B+树是B树的变体，是MySQL InnoDB、PostgreSQL等数据库和大多数文件系统的默认索引结构。

关键区别：

1. 所有实际数据（或数据引用）只存储在叶子节点中。内部节点仅存储键作为导航器（Search Key）。
2. 叶子节点之间通过指针连接成有序链表，支持高效的范围查询。
3. 内部节点的键是”分隔键”——用于指引搜索方向，不一定是叶子中实际存在的键（虽然通常在插入时选择叶子节点的最小键）。

B+树在MySQL InnoDB中的实际应用：

InnoDB的索引组织表（Index-Organized Table）以B+树为载体，主键索引（聚簇索引）的叶子节点直接存储完整数据行。二级索引（非聚簇索引/辅助索引）的叶子节点存储主键值。通过二级索引查找时，先在二级索引B+树中找到主键值，再回到主键索引B+树中查找完整行——即”回表”。

因此InnoDB最佳实践：

• 必须设主键：否则InnoDB会自动生成6字节的rowid作为隐藏主键，浪费空间
• 主键尽量短：因为二级索引叶子节点存储了主键值。长主键意味着所有二级索引都变胖
• 主键尽量自增单调：顺序插入避免了B+树的页分裂（Page Split），减少碎片
• 覆盖索引：如果查询列都在二级索引中，可以”Using index”跳过回表（覆盖索引查询，Extra = Using index）

B+树的优势总结：所有数据的存储级数相同（都在叶子层），查找时间稳定；叶子链表使范围查询极为高效（O(log N + K)访问K个连续元素）；内部节点不存储数据，内存中可以缓存更多内部节点（提高缓存命中率）。

六、Trie（前缀树）及其工程优化

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

Trie的基本操作：查找/插入时间复杂度为O(L)，L为字符串长度，与集合大小完全无关。前缀查找极其高效——查找所有以某前缀开始的字符串，只需走到前缀节点，然后遍历其子树即可。Trie天然支持按字典序遍历所有字符串（前序遍历即得）。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
    int prefixCount; // 以此为前缀的字符串数量（可选，用于自动补全的popularity）
    int wordCount;   // 以此结束的字符串数量
}

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.prefixCount++;
        }
        cur.isEnd = true;
        cur.wordCount++;
    }
    
    boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEnd;
    }
    
    boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }
    
    // 自动补全：返回所有以给定前缀开始的字符串（简化实现——需要完整遍历子树）
    List<String> autocomplete(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode node = findNode(prefix);
        if (node == null) return result;
        collect(node, prefix, result);
        return result;
    }
    
    private void collect(TrieNode node, String prefix, List<String> result) {
        if (node.isEnd) result.add(prefix);
        for (char c = 'a'; c <= 'z'; c++) {
            TrieNode child = node.children[c - 'a'];
            if (child != null) collect(child, prefix + c, result);
        }
    }
    
    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的内存问题与压缩优化：

标准Trie的内存开销极大——每个节点有|Σ|（字母表大小，如26或256）个子节点指针。即使只有少量分支，也要全部分配指针数组。

• Radix Tree（压缩Trie/Patricia Trie）：将没有分叉的路径（单子节点链）压缩为一个节点，存储完整子串而非单个字符。例如”ice”→”iceberg”→”iceland”中，从”ice”到”iceberg”和”iceland”的分叉前共享的”ice”部分被存储为一个边标签。Linux内核的页缓存（Radix Tree）和路由表（FIB trie）使用它。

• Ternary Search Tree（TST，三叉搜索树）：每个节点只有三个子节点指针——左（字符小于当前节点）、等于（字符等于当前节点）、右（字符大于当前节点）。将Trie的空间从 O(|T| × |Σ|) 降为 O(|T|)（|T|为树节点数）。查找性能稍逊于标准Trie（平均O(log |Σ| + L)），但内存效率极高。

• Double-Array Trie：将Trie压缩为两个整数数组（BASE数组记录转移基址，CHECK数组记录前驱状态）。由Aho和Ullman在1980年代提出，日本MeCab分词器、Mozc输入法中使用。压缩率高，但构建复杂且不支持动态更新。

Trie的工程应用：

• 搜索引擎的自动补全：Trie + 每个节点缓存Top K最热门搜索词 + 热度衰减
• IP路由表（最长前缀匹配）：路由器FIB使用压缩Trie（Patricia Trie）进行IP前缀匹配
• 拼写检查：字典存储为Trie，可以用编辑距离+DFS在Trie中高效搜索近邻词
• T9手机输入法：按键序列映射为Trie路径，高效预测单词
• Boggle/Scrabble拼字游戏：Trie存储合法词表，DFS + Trie快速验证候选词
• 基因序列匹配：后缀Trie用于快查序列中的子串

七、线段树与树状数组

线段树（Segment Tree）是一种用于区间查询和区间更新操作的二叉树。每个节点存储一个区间[L, R]的聚合信息（如区间和、最大值、最小值、GCD等）。线段树叶子节点代表单个元素，内部节点代表子区间的合并。

线段树的构建、单点更新、区间查询时间复杂度均为O(log N)。区间更新使用惰性标记（Lazy Propagation）——在当前节点标记”此区间需要被更新”，等到确实需要访问子区间时才将更新下推。

class SegmentTree {
    long[] tree;    // 线段树数组
    long[] lazy;    // 惰性标记数组
    int n;
    
    SegmentTree(int[] arr) {
        n = arr.length;
        tree = new long[4 * n];
        lazy = new long[4 * n];
        build(arr, 1, 0, n - 1);
    }
    
    void build(int[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(arr, 2 * node, start, mid);
            build(arr, 2 * node + 1, mid + 1, end);
            tree[node] = tree[2 * node] + tree[2 * node + 1]; // 区间和
        }
    }
    
    void rangeUpdate(int node, int start, int end, int l, int r, long val) {
        // 惰性标记下推
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[2 * node] += lazy[node];
                lazy[2 * node + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
        if (start > r || end < l) return; // 不相交
        if (start >= l && end <= r) {     // 完全覆盖
            tree[node] += (end - start + 1) * val;
            if (start != end) {
                lazy[2 * node] += val;
                lazy[2 * node + 1] += val;
            }
            return;
        }
        int mid = (start + end) / 2;
        rangeUpdate(2 * node, start, mid, l, r, val);
        rangeUpdate(2 * node + 1, mid + 1, end, l, r, val);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
    
    long rangeQuery(int node, int start, int end, int l, int r) {
        // 类似更新逻辑，先下推lazy标记，然后合并结果
    }
}

树状数组（Fenwick Tree / Binary Indexed Tree, BIT）：线段树的轻量级替代，只能处理前缀区间查询和单点更新（或差分数组+区间更新+单点查询）。优势在于代码极其简洁（10-20行），常数极小。

BIT的核心原理：将索引i的二进制表示中的最低位1作为该节点管理的区间长度。例如索引6（0b110）管理[5, 6]两个元素（lowbit=2），索引8（0b1000）管理[1, 8]八个元素（lowbit=8）。

class FenwickTree {
    int[] tree;
    int n;
    
    FenwickTree(int n) { this.n = n; tree = new int[n + 1]; }
    
    // 单点更新：在位置i增加delta
    void add(int i, int delta) {
        while (i <= n) {
            tree[i] += delta;
            i += i & -i; // i += lowbit(i)
        }
    }
    
    // 前缀和查询：arr[1..i]的和
    int prefixSum(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i; // i -= lowbit(i)
        }
        return sum;
    }
    
    // 区间查询：arr[l..r]的和
    int rangeSum(int l, int r) {
        return prefixSum(r) - prefixSum(l - 1);
    }
}

i & -i（lowbit操作）获取i的最低有效位表示的数值。例如：6的二进制是0b…0110，-6 = 0b…1010（补码），6 & -6 = 0b0010 = 2。

线段树 vs BIT的选择：

• BIT只能处理前缀聚合（前缀和、前缀最大值等）和可逆操作（如加法、乘法、异或——可以通过前缀差得到区间）。对于不可逆操作（如区间最小值），BIT无法实现区间查询。
• 线段树更通用——区间查询、区间更新、任意可结合的聚合操作（和、最小值、最大值、GCD等），但实现更复杂（4N空间，需惰性标记）。
• BIT空间仅N+1，代码仅20行。在BIT能覆盖的场景中（如数组的前缀和动态维护、逆序对计数），优先使用BIT。

八、后缀树与后缀数组

后缀树（Suffix Tree）是给定字符串所有后缀的压缩Trie。它可以在O(N)时间内构建（Ukkonen算法，虽然实现极其复杂），支持多种字符串操作：

• 判断模式串P是否在S中：O(|P|)时间，在后缀树中沿着P的字符路径走
• 统计P在S中的出现次数：O(|P|)时间，到达对应节点后查看该节点的子树中叶子数
• 寻找两个字符串的最长公共子串：构建”字符串1#字符串2$”的后缀树，然后寻找深度最大且其子树中同时含有来自S1和S2的叶子节点——O(N)时间
• 最长重复子串、最长回文子串等

后缀数组（Suffix Array）是后缀树的实用替代：将所有后缀按字典序排序后的起始索引数组。加上LCP（Longest Common Prefix）数组，后缀数组可以实现后缀树的大部分功能，但构建更简单（O(N log N)的倍增算法或DC3线性算法）且内存效率高（约为后缀树的1/5到1/10）。

// 后缀数组的O(N log² N)朴素构建
int[] buildSuffixArray(String s) {
    int n = s.length();
    Integer[] sa = new Integer[n];
    int[] rank = new int[n]; // 当前按2^k长度排序的rank
    for (int i = 0; i < n; i++) {
        sa[i] = i;
        rank[i] = s.charAt(i);
    }
    
    for (int k = 1; k < n; k <<= 1) {
        final int[] r = rank;
        final int K = k;
        Arrays.sort(sa, (a, b) -> {
            if (r[a] != r[b]) return r[a] - r[b];
            int ra = (a + K < n) ? r[a + K] : -1;
            int rb = (b + K < n) ? r[b + K] : -1;
            return ra - rb;
        });
        
        int[] tmp = new int[n];
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            int prevA = sa[i-1], curA = sa[i];
            int prevB = (prevA + K < n) ? r[prevA + K] : -1;
            int curB = (curA + K < n) ? r[curA + K] : -1;
            tmp[curA] = tmp[prevA] + (r[prevA] != r[curA] || prevB != curB ? 1 : 0);
        }
        rank = tmp;
    }
    return Arrays.stream(sa).mapToInt(i -> i).toArray();
}

后缀数组使用倍增法（Doubling），每次将排序的键长度翻倍：对长度为2^k的前缀排序，利用长度为2^(k-1)的排序结果作为双关键字（前一半rank + 后一半rank）。总排序次数为O(log N)，每次O(N log N)（使用标准排序）或O(N)（使用基数排序对两个关键字排序），总复杂度O(N log² N)或O(N log N)。

九、树的工程应用全景

数据库索引：MySQL InnoDB的B+树聚簇索引和辅助索引；PostgreSQL的GiST（通用搜索树，支持多维数据和不规则数据类型）+ SP-GiST（空间分区GiST）+ GIN（倒排索引）扩展了B树的范型。

文件系统：Ext4的HTree索引目录（B树变体，支持O(log N)文件名查找）；NTFS的MFT使用B+树管理文件记录；ZFS和Btrfs使用B树（或B+树）管理块分配和快照。

操作系统内核：

• Linux内核的红黑树是最核心的数据结构之一：CFS调度器使用红黑树按vruntime排序进程；VMA（Virtual Memory Area）管理使用红黑树（+双向链表）存储进程的虚拟地址空间区域；epoll的事件管理使用红黑树存储监控的fd。
• Linux的Radix Tree用于页缓存（Page Cache）索引——通过文件偏移量快速定位缓存页。
• FreeBSD的AVL树用于某些内核模块（如ZFS ARC缓存）。

网络与路由：

• IP路由表的FIB（Forwarding Information Base）使用压缩Trie（Patricia Trie）进行最长前缀匹配。
• DNS解析器缓存使用Trie按域名层级组织缓存条目。

编译器：抽象语法树（AST）是编译原理的核心——源代码经过词法分析和语法分析后生成的树形中间表示。符号表（Symbol Table）通常使用哈希表，但Block Scope的管理使用树形结构（每次进入新的作用域，创建子符号表并链接到父作用域符号表）。

NLP与搜索：拼音输入法使用Trie存储词组和频率信息；搜索引擎的倒排索引使用B树（或SkipList）按文档ID组织；前缀/中缀搜索使用Trie或后缀数组。

图形与游戏：BSP树（Binary Space Partitioning）用于3D渲染的可见性判定；四叉树（Quadtree）和八叉树（Octree）用于2D/3D空间划分（碰撞检测、视野管理）；行为树（Behavior Tree）用于游戏AI决策。

十、面试常见追问

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

AVL树更严格平衡（高度差≤1），查找操作略快于红黑树（树更矮，约1.44 log₂N vs 2 log₂N）。但在插入和删除密集的场景中，AVL树每次操作可能需要进行O(log N)次旋转（从插入/删除点向上传播的旋转），而红黑树最多仅需O(1)次旋转（插入最多2次，删除最多3次）。因此对于读多写少的场景（如字典、配置中心），AVL树更合适；对于读写混合或写频繁的场景（如Java TreeMap在通用场景中、Linux调度器进程频繁创建/退出），红黑树综合更优。Java和C++标准库均选择红黑树，说明在实际应用场景中红黑树的综合表现更受认可。但值得一提的是，在某些特定领域AVL树仍然流行——如某些数据库的元数据管理使用AVL树就是因为元数据的读取频率远高于更新频率。

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

核心原因是磁盘I/O模型。B+树的每个节点对应一个磁盘页（通常4KB或16KB），可以存储数百个键值和子节点指针。以16KB页、每个键+指针占16字节为例，每个内部节点可存储约1000个键。这意味着十亿条记录仅需log_1000(10^9) ≈ 3层，即3次磁盘I/O即可定位任意记录。红黑树是二叉树，高度为log₂(10^9) ≈ 30层，每次比较可能访问不同的磁盘页，需要约30次磁盘I/O——即使把上层节点缓存到内存中，仍有大量节点分散在磁盘的不同位置。此外，B+树的叶子链表支持高效的范围查询（如SELECT … WHERE id BETWEEN a AND b）——找到起始键后沿着叶子链表顺序扫描即可。红黑树的范围查询需要始终在树中回溯寻找中序后继节点。数据库的查询模式以范围查询最为常见，B+树的叶子链表天然优化了这种模式。

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

标准Trie的内存开销是主要瓶颈——每个节点需要|Σ|（字母表大小）个子节点指针，对英文字母表是26或52个，对Unicode则是天文数字。优化方法：（1）压缩Trie（Radix Tree/Patricia Trie）：将分叉的单路径压缩为一个节点，存储完整子串而非单个字符——大幅减少节点数。（2）三叉搜索树（Ternary Search Tree, TST）：每个节点仅有三个子节点指针（<, =, >），将空间从O(|T|×|Σ|)降为O(|T|)，但查找时间从O(L)变为O(L log |Σ|)（在某些场景下可接受）。（3）Double-Array Trie：用两个整数数组（BASE和CHECK）替代指针，是日本NLP工具（如MeCab）的标准选择。（4）Bitmap + 紧凑数组：用一个Bitmap（如32位int）标记哪些字符分支有子节点，再用一个紧凑的ArrayList存储实际存在的子节点指针。（5）Burst Trie：在Trie节点中使用小型哈希表或数组代替完整数组，仅在节点超过阈值时转换为真正的Trie节点。选择优化方案时需要考虑：查找性能要求、内存限制、是否需要动态插入（某些方案如Double-Array Trie构建后不支持动态更新）。

问题四：线段树和树状数组（BIT）如何选择？

本质区别在于通用性 vs 简洁性。树状数组（BIT）只能处理前缀聚合和可逆运算（加法、异或、乘法，可以用前缀差得到区间结果）。对于不可逆的聚合操作（区间最小值、区间GCD，无法从前缀推导区间），BIT无法实现区间查询。但BIT的代码仅20行，且常数极小（每个操作仅需几次位运算和数组访问）。线段树通用性强——支持任意可结合的聚合操作（和、最小值、最大值、GCD、矩阵乘等），且可以支持区间更新（通过惰性标记）。但线段树的实现需要惰性标记设计（容易出错），空间4N。工程实践：当问题可以用BIT解决时（如动态前缀和、求逆序对数、区间加+单点查等），优先使用BIT。当需要区间更新+区间查询、或不可逆的聚合操作时，使用线段树。竞赛编程中BIT因其简洁性广受欢迎，面试中也更容易在限定时间内正确实现。

问题五：Morris遍历在实际工程中有哪些应用？

Morris遍历的主要价值在于其O(1)空间复杂度。在实际工程中的应用场景：（1）嵌入式系统或内存极受限环境——在几乎没有栈空间的设备上进行二叉树遍历（如某些MCU只有几百字节的RAM）。（2）大型树的非侵入式遍历——当需要遍历一棵极大的二叉树（如内存中数百GB的索引结构）但严禁修改树结构和分配额外内存时，Morris遍历使用叶子节点的null指针建立临时线索，遍历结束后恢复原状。（3）在只读数据结构上进行遍历——某些场景下树的节点是只读的（如在ROM中或共享内存中），不能使用额外的栈或队列，Morris遍历利用现有字段即可完成。（4）教学与思维训练——Morris遍历面试中展示的是对指针操作的精准掌控和对树结构的深层理解（最重要的是展示空间复杂度的渐进改进意识）。注意Morris遍历在实际工程中的使用并不广泛——因为它的常数因子比显式栈迭代更大（多趟遍历、反复建立和恢复线索），且调试困难。在大多数实际场景中，O(log N)的递归栈或显式栈的开销完全可以接受。