数据结构第28节 字典树

字典树（Trie，也称前缀树）是一种用于存储字符串的树形数据结构。它将字符串中的字符作为树的边，每个节点代表一个可能的前缀。字典树非常适合处理大量字符串的搜索、插入和删除操作，尤其是在查找具有相同前缀的字符串时非常高效。

基本概念：

• 根节点：通常不包含任何数据，它的子节点包含字符串的第一个字符。
• 内部节点：代表字符串的中间字符。
• 叶子节点：代表字符串的结束字符，通常会附加一个标志表示该路径是一个完整的单词。

案例分析与实现：

假设我们要实现一个简单的字典树来存储英文单词，比如 “cat”, “cattle”, “dog”, “dodge” 和 “do”。

步骤1: 定义节点类

class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}

步骤2: 实现字典树类

public 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++) {
            int index = word.charAt(i) - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    // 搜索单词是否存在于字典树中
    public boolean search(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current != null && current.isEndOfWord;
    }
}

步骤3: 使用字典树

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("cattle");
        trie.insert("dog");
        trie.insert("dodge");
        trie.insert("do");

        System.out.println("Search cat: " + trie.search("cat")); // 应输出 true
        System.out.println("Search dog: " + trie.search("dog")); // 应输出 true
        System.out.println("Search do: " + trie.search("do"));   // 应输出 true
        System.out.println("Search dodge: " + trie.search("dodge")); // 应输出 true
        System.out.println("Search dodger: " + trie.search("dodger")); // 应输出 false
    }
}

这个简单的字典树实现了插入和搜索功能。在实际应用中，你可能还需要实现删除、获取所有前缀单词等功能。字典树在拼写检查、自动完成、IP路由选择等领域有着广泛的应用。

当然，我们可以继续扩展字典树的功能，添加删除操作以及遍历字典树以列出所有单词或特定前缀下的单词。以下是完善后的代码：

步骤4: 添加删除功能

为了正确地删除一个单词，我们需要从字典树中移除该单词的路径，但要注意不要移除其他单词的公共前缀。这需要我们递归地检查并删除空闲的节点。

// 删除单词
public boolean delete(String key) {
    return delete(root, key, 0);
}

private boolean delete(TrieNode node, String key, int depth) {
    if (node == null) return false;

    if (depth == key.length()) {
        if (!node.isEndOfWord) return false;

        node.isEndOfWord = false;
        // 如果当前节点没有孩子，则可以删除
        if (isEmpty(node)) {
            node = null;
            return true;
        }
        return false;
    }

    int index = key.charAt(depth) - 'a';
    boolean shouldDeleteCurrentNode = delete(node.children[index], key, depth + 1);

    if (shouldDeleteCurrentNode) {
        node.children[index] = null;
        // 如果当前节点没有任何孩子并且不是单词的结尾，那么删除它
        if (isEmpty(node) && !node.isEndOfWord) {
            return true;
        }
    }
    return false;
}

private boolean isEmpty(TrieNode node) {
    for (int i = 0; i < node.children.length; i++) {
        if (node.children[i] != null) return false;
    }
    return true;
}

步骤5: 遍历字典树

遍历字典树可以让我们打印出所有的单词，或者找到具有特定前缀的所有单词。

// 打印具有给定前缀的所有单词
public void printWordsWithPrefix(String prefix) {
    TrieNode node = get(prefix);
    if (node == null) {
        System.out.println("No words found with the given prefix.");
        return;
    }
    printWords(node, prefix);
}

private void printWords(TrieNode node, String currentString) {
    if (node.isEndOfWord) {
        System.out.println(currentString);
    }

    for (int i = 0; i < node.children.length; i++) {
        if (node.children[i] != null) {
            printWords(node.children[i], currentString + (char)(i + 'a'));
        }
    }
}

// 查找具有给定前缀的节点
private TrieNode get(String key) {
    TrieNode current = root;
    for (int i = 0; i < key.length(); i++) {
        int index = key.charAt(i) - 'a';
        if (current.children[index] == null) {
            return null;
        }
        current = current.children[index];
    }
    return current;
}

现在，我们可以在主函数中使用这些方法：

public static void main(String[] args) {
    Trie trie = new Trie();
    trie.insert("cat");
    trie.insert("cattle");
    trie.insert("dog");
    trie.insert("dodge");
    trie.insert("do");

    System.out.println("Search cat: " + trie.search("cat"));
    System.out.println("Search dog: " + trie.search("dog"));
    System.out.println("Search do: " + trie.search("do"));
    System.out.println("Search dodge: " + trie.search("dodge"));
    System.out.println("Search dodger: " + trie.search("dodger"));

    trie.printWordsWithPrefix("d");
    trie.delete("cat");
    System.out.println("After deleting 'cat': Search cat: " + trie.search("cat"));
}

这样，我们就有了一个更完整的字典树实现，包括插入、搜索、删除和遍历功能。

在学生成绩管理系统中使用字典树（Trie）来实现增删改查（CRUD）操作是一种创新的方法，尤其是当需要对大量以文本形式存储的数据（如学生姓名）进行快速前缀搜索时。但是，传统的字典树并不直接支持数据的删除或修改操作，因为这些操作可能会影响树的结构。为了简化说明，我们将使用字典树来存储学生姓名，并使用一个额外的数据结构（如HashMap）来关联姓名与成绩，以便于更新和删除操作。

下面是一个使用Java实现的简化版学生成绩管理系统，其中使用字典树来存储学生姓名，并使用HashMap来存储姓名和成绩之间的对应关系。

首先，我们定义字典树的节点类TrieNode：

class TrieNode {
    private final int ALPHABET_SIZE = 26;
    TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    boolean isEndOfWord;

    public TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++) {
            children[i] = null;
        }
    }
}

然后，定义字典树类Trie：

public class Trie {
    private TrieNode root;

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

    public void insert(String key) {
        TrieNode current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
        current.isEndOfWord = true;
    }

    public boolean search(String key) {
        TrieNode current = root;
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if (current.children[index] == null) {
                return false;
            }
            current = current.children[index];
        }
        return current != null && current.isEndOfWord;
    }
}

接下来，创建StudentScoreManager类，用于管理学生姓名和成绩：

import java.util.HashMap;

public class StudentScoreManager {
    private Trie studentNames;
    private HashMap<String, Integer> scores;

    public StudentScoreManager() {
        studentNames = new Trie();
        scores = new HashMap<>();
    }

    public void addScore(String name, int score) {
        studentNames.insert(name);
        scores.put(name, score);
    }

    public void updateScore(String name, int score) {
        if (scores.containsKey(name)) {
            scores.put(name, score);
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public void deleteScore(String name) {
        if (scores.containsKey(name)) {
            scores.remove(name);
            // 删除字典树中的条目（这里简化处理，不实际删除）
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public int getScore(String name) {
        if (scores.containsKey(name)) {
            return scores.get(name);
        } else {
            throw new IllegalArgumentException("Student not found.");
        }
    }

    public boolean checkName(String name) {
        return studentNames.search(name);
    }
}

最后，在main方法中使用StudentScoreManager：

public static void main(String[] args) {
    StudentScoreManager manager = new StudentScoreManager();
    manager.addScore("Alice", 90);
    manager.addScore("Bob", 85);
    manager.addScore("Charlie", 92);

    System.out.println(manager.checkName("Alice")); // 输出 true
    System.out.println(manager.getScore("Bob")); // 输出 85
    manager.updateScore("Charlie", 95);
    System.out.println(manager.getScore("Charlie")); // 输出 95
    manager.deleteScore("Bob");
    System.out.println(manager.checkName("Bob")); // 输出 false
}

在这个示例中，addScore方法同时在字典树和HashMap中添加学生姓名和成绩；updateScore和deleteScore仅更新或删除HashMap中的成绩，而字典树保持不变（为了简单起见，没有实现在字典树中删除节点的功能）。getScore和checkName分别用于获取成绩和检查姓名是否存在。

需要注意的是，这种方法在删除操作上可能会导致字典树中存在“孤儿”节点，如果需要维护一个完全一致的字典树，那么删除操作需要更复杂的逻辑来重构树的结构。