1. 什么是字典树

Trie树,又称字典树、前缀树,是一种树形结构,典型的应用场景是在一个海量数据集中快速查找某一个数据,类似功能的高效数据结构还有哈希表,不过哈希表受制于哈希函数的选取以及哈希表的容量,性能可能会有波动,而字典树就不会有这个问题。

字典树的优点是:最大程度上减少查找时无谓的字符比较,以减少时间复杂度。

下面具体介绍什么是字典树,以存储字符串为例。

首先字典树中每个节点只存储一个字符,但与二叉树相比,存储字符串的字典树节点有26个子节点,因为总共有26个英文字母,字典树的根节点不存储数据,然后根节点向下伸展出26个子节点分别表示一个字符串中第一个字符分别是26个字母的场景,然后这26个子节点又分别向下伸展26个子节点表示字符串的第二个字符。可以看出字典树所耗费的空间是非常大的,基本上是指数级增长,这也说明了字典树的一个性质:空间换时间。

一颗字典树

2. 字典树的操作

现在讨论字典树的各种操作,前面说字典树最主要的作用就是海量数据集查找,所以插入和查找是最重要的两个操作。

插入。首先假设有一个空字典树,root向下的26个指针全都指向NULL。现在要插入"apple",首先取出第一个字符'a',然后在字典树第一层找'a'所对应的节点是否存在,如果不存在则建立节点'a'。接下来以节点'a'为基准查找字符'p'是否存在,依此类推向下查找建立直到建立出一条'a' 'p' 'p' 'l' 'e'的路径,最终在'e'处设一个标志表示'a' 'p' 'p' 'l' 'e'是一条完整的路径,即存入了"apple"

查找。可以想到查找操作相当之简单,依次在树里查找对应的字母即可。可知在字典树中查找一个字符串的时间复杂度为O(S),S为这个字符串的长度。

3. 字典树实现

#define R 26  // 26个小写字母

typedef struct prefixTreeNode {
    struct prefixTreeNode* links[R];  // 每个节点26个分叉
    int isEnd;  // 0 or 1
} Node;

void nodeInit(Node** pRoot) {
    *pRoot = (Node *)malloc(sizeof(Node));
    for (int i = 0; i < R; i++) {
        (*pRoot)->links[i] = NULL;
    }
    (*pRoot)->isEnd = 0;
}

void prefixTreeInsert(Node* root, char* str) {
    Node* cur = root;

    while (*str) {  // 取出str中每个字符
        if (cur->links[*str - 'a'] == NULL) {  // 如果这个字符不存在
            nodeInit(&(cur->links[*str - 'a']));
        }
        cur = cur->links[*str - 'a'];  // cur前进到下一层 
        str++;
    }
    cur->isEnd = 1;
}

int prefixTreeSearch(Node* root, char* str) {
    Node* cur = root;

    while (*str) {
        if (cur->links[*str - 'a'] == NULL) {
            return 0;
        }
        else {
            cur = cur->links[*str - 'a'];
            str++;
        }
    }
    return cur->isEnd == 1;
}

4. 字典树应用

字典树在现实中的应用还是很多的,最常见的比如在有道上查一个单词,输入appl下面就会自动显示appl开头的单词例如apple。这可以看作前缀查询,即在海量数据集中查找以appl为前缀的数据,这种场景下哈希表就没什么用武之地了。

在网络中也有类似的应用。路由器收到一个报文后会根据目的IP在路由表中查找下一跳地址,而查找规则就是最长匹配原则,即要匹配的是路由表中最长的网段条目,那么就完全可以用前缀树来快速查表了。

Last modification:September 8th, 2019 at 08:18 pm