本文共 3712 字，大约阅读时间需要 12 分钟。

Trie

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

trie中的键通常是字符串，但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trie中的键是一串位元，可以用于表示整数或者内存地址。

基本性质

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

优点：

1. 可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。
2. 跟哈希表比较：
   最坏情况时间复杂度比hash表好
   没有冲突，除非一个key对应多个值（除key外的其他信息）
   自带排序功能（类似Radix Sort），中序遍历trie可以得到排序。

缺点：

1. 虽然不同单词共享前缀，但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。
2. 每个结点的子树的根节点的组织方式有几种。
   如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。
   如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表减少字符宽度以减少字母集个数。
   对字符集使用bitmap，再配合链接法。
3. 如果数据存储在外部存储器等较慢位置，Trie会较hash速度慢（hash访问O(1)次外存，Trie访问O(树高)）。
4. 长的浮点数等会让链变得很长。可用bitwise trie改进。

模板

k叉

/* *  INIT: init(); *  注: tree[i][tk] > 0时表示单词存在，当然也可赋予它更多含义 */const int tk = 26, tb = 'a';    //  tk叉; 起始字母为tb;const int N = 1010;             //  N: 最大结点个数int top, tree[N][tk + 1];void init() {
       top = 1;    memset(tree[0], 0, sizeof(tree[0]));    return;}// 查找字符串，失败返回0int search(char *s) {
       for (int rt = 0; rt == tree[rt][*s - tb];) {
           if (*(++s) == 0) {
               return tree[rt][tk];        }    }    return 0;}void insert(char *s, int rank = 1) {
       int rt, nxt;    for (rt = 0; *s; rt = nxt, ++s) {
           nxt = tree[rt][*s - tb];        if (0 == nxt) {
               tree[rt][*s - tb] = nxt = top;            memset(tree[top], 0, sizeof(tree[top]));            top++;        }    }    // 1表示存在，0表示不存在，也可以赋予其其他含义    tree[rt][tk] = rank;}// 只做标记，假定s一定存在void delt(char *s) {
       int rt = 0;    for (; *s; ++s) {
           rt = tree[rt][*s - tb];    }    tree[rt][tk] = 0;    return;}// 最长前缀，返回相同的位数int prefix(char *s) {
       int rt = 0, lv;    for (lv = 0; *s; ++s, ++lv) {
           rt = tree[rt][*s - tb];        if (rt == 0) {
               break;        }    }    return lv;}

左儿子右兄弟

/* *  左孩子右兄弟 *  INIT: init(); */const int N = 1010;int top;struct trie {
       char c;    int l, r, rk;} tree[N];void init() {
       top = 1;    memset(tree, 0, sizeof(tree[0]));}// 失败返回0int search(char *s) {
       int rt;    for (rt = 0; *s; ++s) {
           for (rt = tree[rt].l; rt; rt = tree[rt].r) {
               if (tree[rt].c == *s) {
                   break;            }        }        if (rt == 0) {
               return 0;        }    }    return tree[rt].rk;}// rk: 权或者标记void insert(char *s, int rk = 1) {
       int i, rt;    for (rt = 0; *s; ++s, rt = i) {
           for (i = tree[rt].l; i; i = tree[i].r) {
               if (tree[i].c == *s) {
                   break;            }        }        if (i == 0) {
               tree[top].r = tree[rt].l;            tree[top].l = 0;            tree[top].c = *s;            tree[top].rk = 0;            tree[rt].l = top;            i = top++;        }    }    tree[rt].rk = rk;    return;}// 假定s已经存在，只做标记void delt(char *s) {
       int rt;    for (rt = 0; *s; ++s) {
           for (rt = tree[rt].l; rt; rt = tree[rt].r) {
               if (tree[rt].c == *s) {
                   break;            }        }        tree[rt].rk = 0;    }    return;}// 最长前缀int profix(char *s) {
       int rt = 0, lv;    for (lv = 0; *s; ++s, ++lv) {
           for (rt = tree[rt].l; rt; rt = tree[rt].r) {
               if (tree[rt].c == *s) {
                   break;            }        }        if (rt == 0) {
               break;        }    }    return lv;}

bit-wise Trie

类似于普通的Trie，但是字符集为一个bit位，所以孩子也只有两个。

虽然是按bit位存储和判断，但因为cache-local和可高度并行，所以性能很高。跟红黑树比，红黑树虽然纸面性能更高，但是因为cache不友好和串行运行多，瓶颈在存储访问延迟而不是CPU速度。

压缩Trie

压缩分支条件：

1. Trie基本不变
2. 只是查询
3. key跟结点的特定数据无关
4. 分支很稀疏

若允许添加和删除，就可能需要分裂和合并结点。此时可能需要对压缩率和更新（裂，并）频率进行折中。

转载地址：https://blog.csdn.net/weixin_43820352/article/details/108493803 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！