数据结构学习笔记之字典树（trie）

定义

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字典树

Trie树查找每个条目的复杂度和字典中条目的个数无关，而是和查找的条目的长度有关。常用的场景有通讯录、最长公共前缀等等。
由上图可知对于 Trie的定义可以使用一个数据域和一个字符数组完成，一般情况下数组的长度设置为26即可，但是不同的语言和不同的场景，可能为导致数组的程度难以确定，比如是否考虑大小写、是否包含其他字符等，而且使用数组的方式可能会包含多个空闲位置，导致内存资源的浪费，所以我们使用以下方式定义动态的 Trie。

class Node{
  //某些条目比如对于abc， abcd，在字典树中如果是通过叶子节点来来判定是否到达条目的结尾，那就不存在abc了。
  //可以给每个节点多增加一个标识，用来标识当前节点是否是一个条目的结尾。
  boolean isWord;
  //数据  e 和对应的子节点
  Map<E, Node> next;
}

基本使用
（1）构建字典树

    //向字典树中添加一个元素
    public void add(String word){
        Node cur = root;
        // 遍历 word，将每个字符添加到对应的节点中
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            // 如果字符对应的节点不存在，则添加节点
            cur.next.putIfAbsent(c, new Node());
            // 获取 该节点的下一个节点，重复操作
            cur = cur.next.get(c);
        }
        // 如果word存在，则不更新，如果不存在，则标识当前的节点为字符串的尾部。
        if(!cur.isWord && size ++ >= 0) cur.isWord = true;
    }

（2）查询字符

    //从 trie 中查找元素
    public boolean search(String word){
        Node cur = root;
        // 遍历字符串，去字典树中寻找是否有对应的路径可以表示
        for (int i = 0; i < word.length(); i++) {
            Node node = cur.next.get(word.charAt(i));
            if(node == null) return false;
            cur = node;
        }
        return cur.isWord;
    }

扩展
Tire的删除操作、压缩字典树、 Tnernay Search Trie、后缀树。

数据结构学习笔记之字典树（trie）

代码地址