Trie树的分析和理解

简介

　　在使用一些搜索引擎去搜一些东西的时候，我们经常会碰到一个有意思的事情。有时候我们在搜索框输入一部分内容的时候，会发现搜索框会显示一个下拉的列表，里面有一些以前面输入的内容为开头的一系列搜索字段。比如当输入search的时候，搜索框会显示如下的内容：

　　如图所示，这里显示一个比较神奇的东西，网站居然可以给我们有一个自动补全的提示，这样可以省略了一些手动的输入。 那么，是什么可以支持这种自动补全的功能呢？它为什么能够这么快呢？

 

Trie树

　　其实能够达到上述效果的后面是因为一个数据结构，就是Trie树，它也称为字典树。在上述示例中，当我们输入一部分字符串的时候，它能够根据我们输入的部分迅速的找到一些匹配的串。当然，除了上述的这个特点，它还有很多其他的特点。我们会详细的一一分析。

　　Trie树的典型结构如下图：

 

　　从最上面的那个节点开始，它是一个起始的根节点。而通过这个根节点它有若干个子节点。而从根节点到它的某些个子节点上有一个对应的值。比如说the，它表示从根节点到t节点，再到h节点，然后到e节点，在这个节点上有对应的值。 我们同时也看到，在一些节点上并没有对应的值，比如se, th等。这些节点虽然有对应的字符，但是它没有对应的值。

　　从上述的讨论中可以看到，Trie树其实是比较适合存储有很多相同前缀的字符串的。比如前面的字符串she就是shell的前缀。这样它的存储得到充分的利用。

 

Trie树结构

　　基于上述的讨论，我们可以构思一下Trie树的结构。因为从最开始的根节点起，理论上它的起始字符可以是任意的一个字符。那么它的可选项是比较大的。而在设定了第一个字符之后，它后续的字符也是面临同样的情况。也就是说，如果一级的可选字符为n个，那么第k级的所有可选范围就达到了n^k这么多。因此，在每个节点，我们都需要定义一个长度为n的数组，表示我们所有可能的选项。如果n和k比较大的话，它消耗的空间将是非常大的。

　　在前面的描述里我们还提到了一些对应的节点有详细的取值，而有的没有。这样，我们就可以定义一个如下类型的节点结构：

 

private static class Node {
    private Object val;
    private Node[] next = new Node[R];
}

　　在上述的定义里，R表示我们选择的字符集数量。可以根据需要来定义。 

　　我们定义的一个初步的Trie树类如下：

 

public class TrieST<T> {
    private static int R = 256;
    private Node root;
    private int n;

    private static class Node {
        private Object val;
        private Node[] next = new Node[R];
    }

    public TrieST() {}
}

　　这里我们假定字符集取值是0-256之间。 这正好代表了ASCII码的取值范围。

 

搜索

　　既然有了这么一个定义，我们来看查找一个元素的过程。以下图为例：

 

　　假设我们需要搜索字符串by，那么需要从根节点开始，一个字符一个字符的对应下去。比如说对应第一个字符的时候，如下图：

　　这表示我们已经找到了第一个对应的字符了。接着我们需要继续找下一个字符y：

　　这样我们就找到了对应的字符串by以及它对应的值4。当然，这里描述的是一种比较理想的情况。还存在着一些其他的情况。比如说对应的字符串在树里找不到的情况。比如说我们要搜索字符串bee。当我们找到第一个字符b之后，再找e发现没有匹配的字符了。也就是说对应的节点位置是null。那么，这代表了一种查找失败的情况。

　　还有一种查找失败的情况，比如我们查找字符串sell，在上图中确实可以找到sell这个串，可是这个串里对应的值为空。因此它也表示查找失败。

　　因此，综合来说，对元素的查找可以是一个递归的过程。每次判断当前字符串的位置以及树里头当前的节点。如果当前节点为null，则返回空。如果和当前位置的字符有匹配，则继续下一步，一直到字符串的最后一个元素能找到匹配的节点并有对应的值。这样，我们可以得到搜索的详细实现如下：

 

public T get(String key) {
    Node x = get(root, key, 0);
    if(x == null) return null;
    return (T)x.val;
}

private Node get(Node x, String key, int d) {
    if(x == null) return null;
    if(d == key.length()) return x;
    char c = key.charAt(d);
    return get(x.next[c], key, d + 1);
}

  get方法的时间复杂度相对比较简单，取决于当前匹配字符串的长度。 

 

添加元素

　　添加元素的过程其实也不复杂。也是根据字符串的位置从头一步步的往树里遍历。当碰到的当前节点为空的话，则创建一个新的节点。当从头到尾一直遍历到字符串末尾的时候，根据当前位置节点的情况来处理。如果当前节点为空，则创建一个新节点，并设置给定的值。而如果这个节点已经存在了，则更新这个节点的值为给定的值。

　　从实现的角度来说，也可以使用递归的方法。只是因为每次递归的时候需要将当前节点返回并赋值给上一个节点的某个元素。这种手法在递归的方法里应用比较多，也比较巧妙。详细的实现如下：

 

public void put(String key, T val) {
    root = put(root, key, val, 0);
}

private Node put(Node x, String key, T val, int d) {
    if(x == null) x = new Node();
    if(d == key.length()) {
        if(x.val == null)
            n++;
        x.val = val;
        return x;
    }
    char c = key.charAt(d);
    x.next[c] = put(x.next[c], key, val, d + 1);
    return x;
}

  

前缀匹配搜索

    Trie树里的一个最典型的应用就是给定一个字符串，查找处所有以这个字符串为前缀的所有串。这就和最开始我们提到的示例那样。如果要实现这部分功能，我们需要首先找到那个以给定字符串作为前缀的节点。当找到这个节点之后，再把它里面所有的子节点都列出来。

　　因此它的详细过程分为两个步骤，一个是首先查找这个前缀对应的节点。然后就是收集节点下面所有合法的子节点。而收集所有子节点的过程也是一个递归的过程。每次遍历当前节点的时候，先遍历它所有的next数组，如果有后续的节点，则继续递归。如果有合法的节点，则将它加入到一个队列里。这部分的代码详细实现如下：

 

public Iterable<String> keysWithPrefix(String prefix) {
    Queue<String> q = new LinkedList<String>();
    Node x = get(root, prefix, 0);
    collect(x, prefix, q);
    return q;
}

private void collect(Node x, String pre, Queue<String> q) {
    if(x == null) return;
    if(x.val != null)
        q.add(pre);
    for(char c = 0; c < R; c++)
        collect(x.next[c], pre + c, q);
}

public Iterable<String> keys() {
    return keysWithPrefix("");
}

 

前缀串的模糊匹配

　　和前面的特性稍微有点不一样，假设我们需要匹配的串里包含有一些通配符。比如说'.'符号的时候，我们需要将所有的子节点都作为匹配当前节点的一个选项，然后再将这些元素继续向后匹配。详细的代码实现如下：

 

public Iterable<String> keysThatMatch(String pat) {
    Queue<String> q = new LinkedList<String>();
    collect(root, "", pat, q);
    return q;
}

public void collect(Node x, String pre, String pat, Queue<String> q) {
    int d = pre.length();
    if(x == null) return;
    if(d == pat.length() && x.val != null) q.add(pre);
    if(d == pat.length) return;

    char next = pat.charAt(d);
    for(char c = 0; c < R; c++)
        if(next == '.' || next == c)
            collect(x.next[c], pre + c, pat, q);
}

  

最长前缀

　　Trie树里还有一种比较常见的应用就是给定一个字符串，求和它匹配的最长前缀。对于这个过程，我们可以这么来看。给定一个字符串来说，它最小的可能是没有字符串和它匹配。也就是说它的第一个元素在树里都找不到匹配的。最长的可能就是它在树里找到一个完整的匹配。那么，要找到这个完整的匹配，我们需要去从树的根节点开始，每次去和串匹配。当中间匹配到某个部分的时候，我们就设置当前匹配的长度为某个值length。如果碰到节点为空或者匹配到串的末尾了，直接返回这个length的长度。这是一种递归的思路。

　　还有一种循环遍历的思路，就是从根节点开始进行遍历比较，当碰到节点为空或者到达串末尾的时候退出。它们的详细实现如下：

 

public String longestPrefixOf(String s) {
    int length = search(root, s, 0, 0);
    return s.substring(0, length);
}

private int search(Node x, String s, int d, int length) {
    if(x == null) return length;
    if(x.val != null) length = d;
    if(d == s.length()) return length;
    char c = s.charAt(d);
    return search(x.next[c], s, d + 1, length);
}

private int search(Node x, String s) {
    int i = 0, length = 0;
    while(x != null && i < s.length()) {
        char c = s.charAt(i);
        x = x.next[c];
        if(x != null && x.val != null)
            length = i;
        i++;
    }

    return length;
}

 

删除元素

    删除元素的过程相对来说比较复杂。首先需要像前面搜索的过程那样找到需要删除的节点。然后将该节点的值设置为空。当然，事情并不是这么简单。我们不能将节点设置为空就完事了。还要看它的子节点和父节点的情况。当它还有非空的子节点的时候，可以直接返回。如果它所有的子节点都为空的时候，我们也需要删除当前的节点。但是这样也可能是的它的父节点也面临同样的情况，我们因此也需要进一步的将它的父节点依次删除。

　　所以这里在实现的时候要判断，当已经到达当前字符串的结尾时，需要设置当前节点的值为空。当然，判断当前节点是否为空也是一个重要的判断条件，如果当前节点为空，则直接返回null。在没有到达当前节点的情况，则需要递归的去调用方法删除子节点里的元素。这是一个递归的实现，递归方法的每一层都是返回当前递归层所访问的节点。也有可能是null。还有一个很重要的部分就是当递归结束后要开始回溯的时候，我们要根据当前的情况来决定返回的值。

　　假如当前节点的值为非空，则直接返回这个节点。如果它的所有子节点里有非空的元素，也直接返回这个节点。只有它所有子节点都为空的时候，返回null。这样就在回溯的时候实现了每一级都是空的时候删除这个节点。详细的代码实现如下：

 

public void delete(String key) {
    root = delete(root, key, 0);
}

private Node delete(Node x, String key, int d) {
    if(x == null) return null;
    if(d == key.length())
        x.val = null;
    else {
        char c = key.charAt(d);
        x.next[c] = delete(x.next[c], key, d + 1);
    }

    if(x.val != null) return x;
    for(char c = 0; c < R; c++)
        if(x.next[c] != null) return x;
    return null;
}

　　这部分的代码实现比较简短，但是运用的思路还是比较灵活，值得仔细体会。 

 

总结

    Trie树是一种比较独特的数据结构。它对于字符串的搜索有比较高的效率。尤其在字符的取值范围比较有限而且长度并不大的情况下表现非常理想。大多数情况下，它的查找和插入元素的复杂度只是和给定串的长度有关。当然，因为它要考虑到每一个节点的所有可能取值。在元素取值范围比较大而且串比较长的时候它的空间消耗会非常大，这样就会变得不适用。在某些情况下，另外一个数据结构Tenary Search Tree会更加合适一些。关于Tenary search tree的讨论，我们会在后面的文章里涉及。

　　另外，从树的节点个数角度来考虑，也可以将Trie树当做一个k叉树，只是在很多情况下，它的多部分节点都是空的。

 

参考材料

Algorithms