零基础数据结构与算法——第三章：高级数据结构-高级树

3.1 树（上）

3.1 树（下）

3.2 堆（Heap）

3.3 哈希表（Hash Table）

3.4 图（Graph）

3.5 高级树结构

在前面的章节中，我们已经学习了基本的树结构，如二叉树和二叉搜索树。在本节中，我们将介绍几种更加高级和专业的树结构，它们在特定场景下有着非常高效的性能。

3.5.1 字典树（Trie）

字典树，也称为前缀树（Prefix Tree）或单词查找树，是一种树形数据结构，用于高效地存储和检索字符串集合。

字典树的基本概念

字典树的主要特点：

1. 根节点不包含字符，除根节点外每个节点都只包含一个字符。
2. 从根节点到某一节点的路径上的字符连接起来，为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。
4. 叶子节点或中间某些节点可以是单词的结尾。
   

字典树的生活例子

电话簿：想象一个电话簿，按照人名的首字母组织。当你要查找"张三"时，你首先找到"张"字开头的部分，然后在其中查找"三"。

词典：当你在词典中查找一个单词时，你通常会按照单词的前缀来缩小搜索范围。

输入法自动补全：当你在手机上输入文字时，输入法会根据你已经输入的字符，预测你可能要输入的完整单词或短语。

字典树的实现

class TrieNode {
    private TrieNode[] children;
    private boolean isEndOfWord;
    
    public TrieNode() {
        children = new TrieNode[26]; // 假设只包含小写字母a-z
        isEndOfWord = false;
    }
    
    public TrieNode getChild(char ch) {
        return children[ch - 'a'];
    }
    
    public void setChild(char ch, TrieNode node) {
        children[ch - 'a'] = node;
    }
    
    public boolean hasChild(char ch) {
        return children[ch - 'a'] != null;
    }
    
    public boolean isEndOfWord() {
        return isEndOfWord;
    }
    
    public void setEndOfWord(boolean isEndOfWord) {
        this.isEndOfWord = isEndOfWord;
    }
}

class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    // 插入单词
    public void insert(String word) {
        TrieNode current = root;
        
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            
            if (!current.hasChild(ch)) {
                current.setChild(ch, new TrieNode());
            }
            
            current = current.getChild(ch);
        }
        
        current.setEndOfWord(true);
    }
    
    // 搜索单词
    public boolean search(String word) {
        TrieNode node = searchNode(word);
        return node != null && node.isEndOfWord();
    }
    
    // 检查是否有以给定前缀开头的单词
    public boolean startsWith(String prefix) {
        return searchNode(prefix) != null;
    }
    
    // 辅助方法：查找节点
    private TrieNode searchNode(String str) {
        TrieNode current = root;
        
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            
            if (!current.hasChild(ch)) {
                return null;
            }
            
            current = current.getChild(ch);
        }
        
        return current;
    }
    
    // 主方法：测试字典树
    public static void main(String[] args) {
        Trie trie = new Trie();
        
        // 插入单词
        trie.insert("apple");
        trie.insert("app");
        trie.insert("application");
        trie.insert("banana");
        
        // 搜索单词
        System.out.println("搜索 'apple': " + trie.search("apple"));       // 输出: true
        System.out.println("搜索 'app': " + trie.search("app"));           // 输出: true
        System.out.println("搜索 'appl': " + trie.search("appl"));         // 输出: false
        System.out.println("搜索 'orange': " + trie.search("orange"));     // 输出: false
        
        // 检查前缀
        System.out.println("前缀 'app': " + trie.startsWith("app"));       // 输出: true
        System.out.println("前缀 'ban': " + trie.startsWith("ban"));       // 输出: true
        System.out.println("前缀 'ora': " + trie.startsWith("ora"));       // 输出: false
    }
}

字典树的应用场景

1. 自动补全：输入法、搜索引擎的搜索建议功能。

2. 拼写检查：检查单词是否拼写正确。

3. 前缀匹配：查找具有特定前缀的所有单词。

4. IP路由：在网络路由中使用前缀树来存储路由表。

5. 单词游戏：如Scrabble，快速检查单词是否有效。

字典树的优缺点

优点：

• 查找、插入和删除操作的时间复杂度为O(m)，其中m是键的长度。
• 可以有效地存储大量具有相同前缀的键。
• 支持前缀匹配查询。

缺点：

• 空间消耗较大，特别是当存储的字符串集合没有太多共同前缀时。
• 不适合存储大量随机字符串。

3.5.2 线段树（Segment Tree）

线段树是一种二叉树，用于存储区间或线段，允许快速查询区间信息（如区间和、区间最大值、区间最小值等）。

线段树的基本概念

线段树的主要特点：

1. 每个节点代表一个区间。
2. 叶节点代表单个元素（长度为1的区间）。
3. 父节点的区间是子节点区间的并集。
4. 树的高度为O(log n)，其中n是元素的数量。

线段树的生活例子

学校成绩统计：假设你是一名老师，需要经常查询某个分数段内有多少学生。你可以使用线段树来存储学生的分数，然后快速查询特定分数范围内的学生数量。

股票价格分析：分析师需要频繁查询某个时间段内的股票最高价、最低价或平均价。线段树可以高效地支持这些查询。

气象数据分析：气象学家需要查询某个时间段内的最高温度、最低温度或平均温度。

线段树的实现（区间和查询）

class SegmentTree {
    private int[] tree;
    private int[] lazy;
    private int[] arr;
    private int n;
    
    public SegmentTree(int[] array) {
        arr = array;
        n = arr.length;
        // 分配4倍原数组长度的空间给线段树
        tree = new int[4 * n];
        lazy = new int[4 * n];
        build(0, 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 = 2 * node + 1;
        int rightChild = 2 * node + 2;
        
        // 递归构建左右子树
        build(leftChild, start, mid);
        build(rightChild, mid + 1, end);
        
        // 父节点的值是子节点值的和
        tree[node] = tree[leftChild] + tree[rightChild];
    }
    
    // 区间查询
    public int query(int left, int right) {
        return query(0, 0, n - 1, left, right);
    }
    
    private int query(int node, int start, int end, int left, int right) {
        // 如果当前节点有延迟更新，先处理
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            
            if (start != end) {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            
            lazy[node] = 0;
        }
        
        // 区间不重叠
        if (start > right || end < left) {
            return 0;
        }
        
        // 当前区间完全包含在查询区间内
        if (start >= left && end <= right) {
            return tree[node];
        }
        
        // 区间部分重叠，递归查询左右子树
        int mid = (start + end) / 2;
        int leftSum = query(2 * node + 1, start, mid, left, right);
        int rightSum = query(2 * node + 2, mid + 1, end, left, right);
        
        return leftSum + rightSum;
    }
    
    // 单点更新
    public void update(int index, int value) {
        update(0, 0, n - 1, index, value);
    }
    
    private void update(int node, int start, int end, int index, int value) {
        // 找到要更新的叶节点
        if (start == end) {
            arr[index] = value;
            tree[node] = value;
            return;
        }
        
        int mid = (start + end) / 2;
        int leftChild = 2 * node + 1;
        int rightChild = 2 * node + 2;
        
        if (index <= mid) {
            // 更新左子树
            update(leftChild, start, mid, index, value);
        } else {
            // 更新右子树
            update(rightChild, mid + 1, end, index, value);
        }
        
        // 更新父节点
        tree[node] = tree[leftChild] + tree[rightChild];
    }
    
    // 区间更新（延迟传播）
    public void updateRange(int left, int right, int value) {
        updateRange(0, 0, n - 1, left, right, value);
    }
    
    private void updateRange(int node, int start, int end, int left, int right, int value) {
        // 如果当前节点有延迟更新，先处理
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            
            if (start != end) {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            
            lazy[node] = 0;
        }
        
        // 区间不重叠
        if (start > right || end < left) {
            return;
        }
        
        // 当前区间完全包含在更新区间内
        if (start >= left && end <= right) {
            tree[node] += (end - start + 1) * value;
            
            if (start != end) {
                lazy[2 * node + 1] += value;
                lazy[2 * node + 2] += value;
            }
            
            return;
        }
        
        // 区间部分重叠，递归更新左右子树
        int mid = (start + end) / 2;
        updateRange(2 * node + 1, start, mid, left, right, value);
        updateRange(2 * node + 2, mid + 1, end, left, right, value);
        
        // 更新父节点
        tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
    }
    
    // 主方法：测试线段树
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        SegmentTree segTree = new SegmentTree(arr);
        
        // 查询区间和
        System.out.println("区间[1, 3]的和: " + segTree.query(1, 3));  // 输出: 15 (3+5+7)
        
        // 更新单个元素
        segTree.update(1, 10);
        System.out.println("更新后区间[1, 3]的和: " + segTree.query(1, 3));  // 输出: 22 (10+5+7)
        
        // 区间更新
        segTree.updateRange(2, 4, 2);
        System.out.println("区间更新后[2, 4]的和: " + segTree.query(2, 4));  // 输出: 25 ((5+2)+(7+2)+(9+2))
    }
}

线段树的应用场景

1. 区间查询：快速查询区间和、区间最大值、区间最小值等。

2. 区间更新：修改区间内所有元素的值。

3. 计算几何：处理线段相交等问题。

4. 范围查询：数据库中的范围查询操作。

线段树的优缺点

优点：

• 支持高效的区间查询和更新操作，时间复杂度为O(log n)。
• 可以处理各种区间操作，如求和、最大值、最小值等。

缺点：

• 实现相对复杂。
• 空间消耗较大，需要4倍原数组的空间。

3.5.3 树状数组（Binary Indexed Tree/Fenwick Tree）

树状数组是一种支持单点更新和区间查询的数据结构，比线段树更简单高效，但功能相对有限。

树状数组的基本概念

树状数组的主要特点：

1. 使用数组实现，但概念上是一棵树。
2. 通过二进制索引实现高效操作。
3. 主要用于处理前缀和（区间和）问题。
4. 每个节点存储的是一段区间的和。

树状数组的生活例子

班级成绩统计：老师需要频繁地计算从第1个学生到第k个学生的总分，同时也需要不断更新某个学生的分数。

销售数据分析：分析师需要计算从1月到某个月的总销售额，同时也需要更新某个月的销售数据。

树状数组的实现

class BinaryIndexedTree {
    private int[] tree;
    private int n;
    
    public BinaryIndexedTree(int size) {
        n = size;
        tree = new int[n + 1]; // 树状数组的索引从1开始
    }
    
    // 构建树状数组
    public BinaryIndexedTree(int[] arr) {
        n = arr.length;
        tree = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            update(i + 1, arr[i]);
        }
    }
    
    // 更新操作：将索引i的值增加val
    public void update(int i, int val) {
        while (i <= n) {
            tree[i] += val;
            i += i & -i; // 将i的最低位1加到i上
        }
    }
    
    // 查询操作：计算前缀和（从1到i）
    public int query(int i) {
        int sum = 0;
        while (i > 0) {
            sum += tree[i];
            i -= i & -i; // 将i的最低位1从i中减去
        }
        return sum;
    }
    
    // 区间查询：计算区间[left, right]的和
    public int rangeQuery(int left, int right) {
        return query(right) - query(left - 1);
    }
    
    // 主方法：测试树状数组
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        BinaryIndexedTree bit = new BinaryIndexedTree(arr);
        
        // 查询前缀和
        System.out.println("前4个元素的和: " + bit.query(4));  // 输出: 16 (1+3+5+7)
        
        // 区间查询
        System.out.println("区间[2, 5]的和: " + bit.rangeQuery(2, 5));  // 输出: 24 (3+5+7+9)
        
        // 更新元素
        bit.update(2, 2);  // 将索引2的元素增加2
        System.out.println("更新后区间[2, 5]的和: " + bit.rangeQuery(2, 5));  // 输出: 26 ((3+2)+5+7+9)
    }
}

树状数组的应用场景

1. 前缀和查询：快速计算数组的前缀和。

2. 区间和查询：通过两次前缀和查询计算区间和。

3. 频率统计：统计元素出现的次数。

4. 逆序对计数：计算数组中的逆序对数量。

树状数组的优缺点

优点：

• 实现简单，代码量少。
• 操作效率高，时间复杂度为O(log n)。
• 空间效率高，只需要原数组大小的空间。

缺点：

• 功能相对有限，主要用于处理前缀和问题。
• 不支持区间更新（除非使用差分数组技巧）。
• 不如线段树灵活，不能处理最大值、最小值等区间操作。

3.5.4 高级树结构的比较

其中，m是字符串的长度，n是元素的数量，ALPHABET_SIZE是字符集的大小。

选择合适的高级树结构取决于具体的应用场景和需求。如果需要处理字符串集合，字典树是最佳选择；如果需要处理各种区间操作，线段树是最灵活的选择；如果只需要处理前缀和问题，树状数组是最简单高效的选择。