Trie树的定义与算法

Trie 树的定义

前缀树，也称字典树、键树，是一种树性结构，是哈希树的变种。
用途：用于统计和排序大量字符串(但不限于字符串)，经常用于搜索引擎系统的文本词频统计。
优点：利用字符串的公共前缀来减少查询时间吗最大限度减少无谓的字符串比较。
核心思想：利用空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

前缀树的三个基本性质

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

与哈希查询的比较

哈希树的讲解：Merkle tree
Trie树的复杂度是 $O(L)$ 其中 $L$ 为字符串的长度，效率还是很高的。
hash的效率一般是 $O(1)$
hash 不支持动态查询，也就是必须等用户输入一个单词完毕后才能进行查询查找。
Trie 树支持动态查询，但是相对hash空间浪费比较严重。

Trie的数据结构

初始化

1
2
3
4
5
6
7
8
9


public class TrieNode {
	int count;
	int prefix;
	TrieNode[] nextNode=new TrieNode[26];
	public TrieNode(){
		count=0;
		prefix=0;
	}
}

插入新结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


//插入一个新单词
	public static void insert(TrieNode root,String str){
		if(root==null||str.length()==0){
			return;
		}
		char[] c=str.toCharArray();
		for(int i=0;i<str.length();i++){
			//如果该分支不存在，创建一个新节点
			if(root.nextNode[c[i]-'a']==null){
				root.nextNode[c[i]-'a']=new TrieNode();
			}
			root=root.nextNode[c[i]-'a'];
			root.prefix++;//注意，应该加在后面
			}
		
		//以该节点结尾的单词数+1
		root.count++;
	}

查询以str开头的单词数量，查询单词str的数量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


//查找该单词是否存在，如果存在返回数量，不存在返回-1
	public static int search(TrieNode root,String str){
		if(root==null||str.length()==0){
			return -1;
		}
		char[] c=str.toCharArray();
		for(int i=0;i<str.length();i++){
			//如果该分支不存在，表名该单词不存在
			if(root.nextNode[c[i]-'a']==null){
				return -1;
			}
			//如果存在，则继续向下遍历
			root=root.nextNode[c[i]-'a'];	
		}
		
		//如果count==0,也说明该单词不存在
		if(root.count==0){
			return -1;
		}
		return root.count;
	}
	
	//查询以str为前缀的单词数量
	public static int searchPrefix(TrieNode root,String str){
		if(root==null||str.length()==0){
			return -1;
		}
		char[] c=str.toCharArray();
		for(int i=0;i<str.length();i++){
			//如果该分支不存在，表名该单词不存在
			if(root.nextNode[c[i]-'a']==null){
				return -1;
			}
			//如果存在，则继续向下遍历
			root=root.nextNode[c[i]-'a'];	
		}
		return root.prefix;
	}

c++写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


class Trie {
public:
    int count;//以当前单词结尾单词数量
    int prefix;//以该处节点之前的字符串为前缀的单词数量。
    Trie* nextNode[26];//26个子树
    Trie() {
        count = 0;
        prefix = 0;
        for(int i=0;i<26;i++)
            nextNode[i] = nullptr;
    }
    
    void insert(string word) {
        if(word.length()==0)
            return;
        Trie* p = this;
        for(int i=0;i < word.length();i++){
            if(p->nextNode[word[i]-'a']==nullptr){
                p->nextNode[word[i]-'a']= new Trie();
            }
            p = p->nextNode[word[i]-'a'];
            p->prefix++;
        }
        p->count++;
    }
    
    bool search(string word) {
        if(word.length()==0)
            return false;
        Trie* p = this;
        for(int i=0;i<word.length();i++){
            if(p->nextNode[word[i]-'a']==nullptr){
                return false;
            }
            p = p->nextNode[word[i]-'a'];
        }

        if(p->count==0){
            return false;
        }
        return true;
    }
    
    bool startsWith(string prefix) {
        if(prefix.length()==0)
            return false;
        Trie* p = this;
        for(int i=0;i<prefix.length();i++){
            if(p->nextNode[prefix[i]-'a']==nullptr){
                return false;
            }
            p = p->nextNode[prefix[i]-'a'];
        }
        if(p->prefix==0){
            return false;
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

参考资料：Trie树