数据结构之「字典树」

字典树

字典树，又称前缀树或 trie树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

字典树的性质

1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

用字典树结构存储《**JVM JAVA PHP HTML HTTP **》字符串。

字典树的实现

字典树的结构

public class Trie {
    //26 个字母
    private int SIZE = 26;
    //字典树的根
    private TrieNode root;
    //初始化字典树
    Trie() {
        root = new TrieNode();
    }

    //字典树节点
    private class TrieNode {
        //由根至该节点组成的字符串模式出现的次数
        private int num;
        //所有的孩子节点
        private TrieNode[] children;
        //是不是最后一个节点
        private boolean isEnd;
        //节点的值
        private char val;

        TrieNode() {
            num = 1;
            children = new TrieNode[SIZE];
            isEnd = false;
        }
    }
}

字典树的插入

//在字典树中插入一个单词
public void insert(String str) {
    //参数校验
    if (str == null || str.length() == 0) {
        return;
    }
    TrieNode node = root;
    char[] letters = str.toCharArray();
    //循环整个单词插入
    for (int i = 0, len = str.length(); i < len; i++) {
        int pos = letters[i] - 'a';
        //假如不存在就新建一个节点
        if (node.children[pos] == null) {
            node.children[pos] = new TrieNode();
            node.children[pos].val = letters[i];
        } else {
            //否则通过这个节点数加一
            node.children[pos].num++;
        }
        node = node.children[pos];
    }
    //最后一个节点
    node.isEnd = true;
}

字典树的查找

//在字典树中查找一个完全匹配的单词.
public boolean find(String str) {
    //参数校验
    if (str == null || str.length() == 0) {
        return false;
    }
    TrieNode node = root;
    char[] letters = str.toCharArray();
    //循环查找是否存在
    for (int i = 0, len = str.length(); i < len; i++) {
        int pos = letters[i] - 'a';
        if (node.children[pos] != null) {
            node = node.children[pos];
        } else {
            return false;
        }
    }
    return node.isEnd;
}

总结

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

字典树也常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。

最后编辑于：2019.04.17 11:01:22