Trie-Tree(字典树)

写这篇博文的目的是为了记录一下字典树的实现,关于Trie-Tree(字典树)原理,我写在了源码中的README中,有兴趣的同学可以看一看。

关于源码,源码只是实现了字符串取值为[a-z]的数据结构,也就是说字典树的每个结点最多有26个子树,这里我采用数组的方式来实现。程序实现了插入,查询是否存在,获取所有字符串出现次数,获取以某一前缀开始的所有子串以及获取以某一字符串为前缀的所有字符串个数这五个功能,感兴趣的同学可以在此基础上进行进一步扩展。

节点结构

下面是每个树结点结构,关于每个字段的含义,我都以注释的形式做了说明

private class TrieTreeNode {

    private int duplicateNum;    // 这个单词的重复次数
    private int prefixNum;       // 以当前结点之前字符串为前缀的字符串个数
    private TrieTreeNode[] childNodes;    // 子树
    private boolean isLeaf;      // 是否是完整的字符串

    public TrieTreeNode() {
        duplicateNum = 0;
        prefixNum = 0;
        childNodes = new TrieTreeNode[26];   // 26个子树
        isLeaf = false;
    }
}

插入

先上代码

private void insert(TrieTreeNode root, String str) {  
    char[] chars = str.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        int index = chars[i] - 'a';

        if (root.childNodes[index] == null) {
            root.childNodes[index] = new TrieTreeNode();
        }

        root.childNodes[index].prefixNum++;

        if (i == chars.length - 1) {
            root.childNodes[index].isLeaf = true;
            root.childNodes[index].duplicateNum++;
        }

        root = root.childNodes[index];
    }
}

代码实现其实很简单,在插入的时候首先根据具体字符定位到具体某一个子树,如果没有这个子树则创建这个子树,然后更新以此结点之前所有结点构成字符串为前缀的字符串出现次数,最后判断如果该字符是字符串最后一个字符,则把该节点标记为叶子结点。

查询是否存在

还是先上代码

private boolean search(TrieTreeNode root, String str) {  
    char[] chars = str.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        int index = chars[i] - 'a';
        if (root.childNodes[index] == null) {
            return false;
        }

        root = root.childNodes[index];
    }
    return true;
}

搜索一个字符串是否存在的思路很简单,即根据字符数组沿着树向下遍历,如果出现子树为空的情况,则说明该子串不存在,如果遍历完成,则说明该字符串存在。需要注意的是,这里的实现并没有判断最后一个结点是否是叶子结点,这样导致的后果就是如果存在字符串以该字符串为前缀,那么也算该字符串存在。当然如果觉得这样不对,可以通过简单的判断来实现更为精确的查找。

获取指定前缀的所有字符串

依旧先上代码

private void preTraversal(Map<String, Integer> map, TrieTreeNode root, String prefix) {

    if (root.isLeaf) {
        map.put(prefix, root.duplicateNum);
    }

    for (int i = 0; i < root.childNodes.length; i++) {
        if (root.childNodes[i] != null) {
            char ch = (char)(i + 'a');
            preTraversal(map, root.childNodes[i], prefix + ch);
        }
    }
}

拿到所有字符串的方法是对Trie-Tree进行前序遍历,上面就是对Trie-Tree进行前序遍历的方法。通过这个方法可以实现两个功能,一个是可以拿到所有字符串出现的次数,另一个是拿到指定前缀的各个字符串出现的次数。

获取指定前缀的字符串出现次数

代码

private int getNumOfPrefix(TrieTreeNode root, String prefix) {  
    char[] chars = prefix.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        int index = chars[i] - 'a';
        if (root.childNodes[index] == null)
            return 0;

        root = root.childNodes[index];
    }

    return root.prefixNum;
}

最后是获取指定前缀的所有字符串出现次数的实现。由于我们在构建Trie-Tree的时候就已经保存了这个次数——prefixNum,所以只需要根据指定前缀沿着Trie-Tree向下遍历找到指定结点就可以得到这个结果了。在遍历的过程中如果发现某一个子树为空,则说明指定前缀的字符串不存在,故返回0。

最后附上源码下载地址

参考

字典树原理

Shaohang Zhao

Read more posts by this author.