乐趣区

关于数据结构与算法:字典树

jiezi

1. 字典树

Trie 树，即字典树，又称单词查找树或键树，是一种树形构造，是一种哈希树的变种。

典型利用是用于统计和排序大量的字符串（但不仅限于字符串），所以常常被搜索引擎零碎用于文本词频统计。

Trie 的核心思想是空间换工夫。它能最大限度地缩小无谓的字符串比拟，利用字符串的公共前缀来升高查问工夫的开销，查问效率比哈希树高。

2. 字典树的性质

  1. 除了根节点外，每一个节点都只蕴含一个字符
  2. 每个节点的所有子节点蕴含的字符都不雷同
  3. 从根节点到某个节点，门路上的字符连接起来，为该节点对应的字符串

3. 结构字典树 

public class Trie {
    static class TrieNode {
        // 示意以后节点的值
        char value;

        // 示意以后节点是否是终止节点（这里不是指叶子节点，是指是否为单词的结尾）boolean flag;

        // 示意以后节点的子节点的数组，不思考大小写共有 26 个字母，所以初始化大小为 26
        TrieNode[] nextNodes = new TrieNode[26];

        public TrieNode() {}

        public TrieNode(char value) {this.value = value;}
    }

    /**
     * 插入一个新单词
     *
     * @param root 根节点
     * @param str 要插入的新单词
     */
    public void insert(TrieNode root, String str) {if (root == null || str == null || str.length() == 0) {return;}
        for (int i = 0; i < str.length(); i++) {
            // index 示意以后字符在字符表中的地位
            int index = str.charAt(i) - 'a';
            // 如果该分支不存在，则创立一个新节点
            if (root.nextNodes[index] == null) {root.nextNodes[index] = new TrieNode(str.charAt(i));
            }
            // 把该节点赋给 root，进入树的下一层
            root = root.nextNodes[index];
        }
        // 设置以后节点为终止节点
        root.flag = true;
    }
}

4. 查找单词是否在字典树中存在 

    /**
     * 查找一个单词是否存在
     *
     * @param root 根节点
     * @param str 要查找的单词
     */
    public boolean search(TrieNode root, String str) {if (root == null || str == null || str.length() == 0) {return false;}
        for (int i = 0; i < str.length(); i++) {
            // index 示意以后的字符在中的字符表中的地位
            int index = str.charAt(i) - 'a';
            // 如果该分支不存在，则阐明不存在该字符
            if (root.nextNodes[index] == null) {return false;}
            // 把以后节点赋给 root，进入树的下一层
            root = root.nextNodes[index];
        }
        // 如果以后节点是终止节点，则阐明存在，否则不存在
        return root.flag;
    }
退出移动版