最近想看一看gin源码,听说gin底层基于压缩字典树,于是想先复习一下字典树知识。

Trie(字典树)用于字符串的快速检索,其每个节点都有若干个字符指针,若在插入或者检索字符串时扫描到一个字符c,就沿着当前节点的c字符指针,走向该指针指向的节点。

初始化

一颗空Trie仅包含一个根节点,该点的字符指针均指向空。

以一个装小写字母的Trie举例:

1
int trie[SIZE][26], tot = 1;

插入

直接上代码吧,感觉挺容易理解的。

1
2
3
4
5
6
7
8
9
10
void insert(char* str) {
int len = strlen(str), p = 1; //p是指针
for (int k = 0; k < len; ++k) {
int ch = str[k] - 'a';
if (trie[p][ch] == 0)
trie[p][ch] = ++tot; //tot是地址,从1开始递,如果字符ch没有出现过就给它新建个节点,地址tot自增
p = trie[p][ch];//指针指向下一个字符的地址
}
end[p] = true;//尾判定
}

检索

1
2
3
4
5
6
7
8
bool search(char* str) {
int len = strlen(str), p = 1;
for (int k = 0; k < len; k++) {
p = trie[p][str[k] - 'a'];
if (p == 0) return false; //夭折了,直接返回false
}
return end[p];
}

注意这里的end[p] = true用于尾判定,当进行到str末尾时,令尾字符的end设置成true,表示已经结尾。

比如有字符串abcde, 如果没有尾判定机制,查询abc的时候就会返回true

删除

直接找顺着找到尾字符,把end[p]设置成false即可

代码都懒得打了

压缩字典树(基数树)

比如一个数1000101010101010010101010010101010,遇到0就插入左节点,遇到1就插入右节点,在插入的过程中构造树节点,在删除的过程中删除树节点。

需要注意的是,使用一个比特位进行判断,会使树的高度过高,非叶节点过多,在实际使用中,我们一般是使用多个比特位作为树节点的判断,但是比特位过多会使节点的子节点槽过多,增大节点的体积。所以一般选用2个或者4个比特位作为树节点。