字典树,又称前缀树(英文名:Trie Tree),为 Edward Fredkin 发明。

举个例子,给出一些单词,(and,as,at,cn,com),则其字典树如下:

从上图可以发现,它有 3 个基本性质:

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

字典树是一个很重要的数据结构,其主要应用为:

  1. 词频统计:例如,给定一个由 10 万个单词组成的库,现要你判断一个单词是否有在库中出现,若出现,求出共出现多少次。
  2. 前缀匹配:以上图为例,如果想获取所有以 "a" 开头的字符串,那么从图中可以很明显的看到是:(and,as,at)。因此利用这个特性,可以巧妙地实现搜索提示功能,如输入一个网址,可以自动列出可能的选择。当没有完全匹配的搜索结果,可以列出前缀最相似的可能。

算法过程分析

共实现三个对外接口:

  1. void add(char * s),将字符串 s 添加至字典树;
  2. int query(char * s),查询字符串 s 是否存在。若存在,返回其存在的次数;若不存在,返回 0;
  3. bool remove(char * s),删除字符串 s。字符串 s 若存在,则直接删除,返回真;若不存在,则返回假。

结点结构如下:

#define TREE_WIDTH 26

struct Node
{
    int path;
    int end;
    char ch;
    Node * next[TREE_WIDTH];
    Node(char ch = ' ')
    {
        this->ch = ch;
        this->path = this->end = 0;
        for (int i = 0; i < TREE_WIDTH; i++)
            this->next[i] = nullptr;
    }
};

本文只讨论小写 26 个英文字母的字典集合,故 TREE_WIDTH 设为 26。

变量 end 的作用,标记该结点是否是单词结尾。变量 path 则用来记录结点被路径覆盖的次数。

请注意,下述代码针对的是动态数据集,即一系列添加,查询,删除三种混合操作。因此对于已无路径覆盖的结点,我们并不会释放其内存,这也是引入 path 的原因(当 path = 0,表示该结点已无路径覆盖)。

两个变量的具体使用如下图:

完整代码

#include <iostream>

#define TREE_WIDTH 26

using namespace std;

struct Node
{
    int path;
    int end;
    char ch;
    Node * next[TREE_WIDTH];
    Node(char ch = ' ')
    {
        this->ch = ch;
        this->path = this->end = 0;
        for (int i = 0; i < TREE_WIDTH; i++)
            this->next[i] = nullptr;
    }
};

class TrieTree
{
private:
    Node * root;
public:
    TrieTree();
    ~TrieTree();
    void destroy(Node * t);
    void add(char * s);
    int query(char * s);
    bool remove(char * s);
};

TrieTree::TrieTree()
{
    root = new Node;
}

TrieTree::~TrieTree()
{
    destroy(root);
    root = nullptr;
}

void TrieTree::destroy(Node * t)
{
    for (int i = 0; i < TREE_WIDTH; i++)
        if (t->next[i])
            destroy(t->next[i]);
    delete t;
}

void TrieTree::add(char * s)
{
    Node * t = root;
    while (*s)
    {
        if (t->next[*s - 'a'] == nullptr)
            t->next[*s - 'a'] = new Node(*s);
        t->next[*s - 'a']->path++;
        t = t->next[*s - 'a'];
        s++;
    }
    t->end++;
}

int TrieTree::query(char * s)
{
    Node * t = root;
    while (*s)
    {
        if (t->next[*s - 'a'] == nullptr || t->next[*s - 'a']->path == 0)
            return 0;
        t = t->next[*s - 'a'];
        s++;
    }
    return t->end;
}

bool TrieTree::remove(char * s)
{
    if (query(s))
    {
        Node * t = root;
        while (*s)
        {
            t->next[*s - 'a']->path--;
            t = t->next[*s - 'a'];
            s++;
        }
        t->end--;
        return true;
    }

    return false;
}

int main()
{
    TrieTree tree;

    tree.add("strawberry");
    tree.add("grandfather");
    tree.add("policeman");
    tree.add("breakfast");
    tree.add("mutton");
    tree.add("bus");
    tree.add("bus");
    tree.add("bustop");
    tree.add("computer");

    // test "query"
    cout << tree.query("bud") << endl; // 0
    cout << tree.query("bus") << endl; // 2

    // test "remove"
    tree.remove("bustop");
    cout << tree.query("bustop") << endl; // 0
    tree.remove("bus");
    cout << tree.query("bus") << endl;    // 1
    tree.remove("bus");
    cout << tree.query("bus") << endl;    // 0

    return 0;
}

不足之处

字典树中的每个结点,其内部都有一个指针数组,若取数组长度为 128,则在树完全展开后需要的内存是非常恐怖的,这也就是字典树在实际工程中需谨慎使用的原因。

其它

文章开源在 Github - blog-articles,点击 Watch 即可订阅本博客。 若文章有错误,请在 Issues 中提出,我会及时回复,谢谢。

如果您觉得文章不错,或者在生活和工作中帮助到了您,不妨给个 Star,谢谢。

(文章完)

文章作者:刘毅 (Ethson Liu)
发布日期:2019-09-13
原文链接:https://ethsonliu.com/2019/09/trie-tree.html
版权声明:文章版权归本人所有,欢迎转载,但必须保留此段声明,且在文章页面明显位置给出原文链接,否则保留追究法律责任的权利。