MENU

字典树(1):字典树入门

一:背景

字典树,又称前缀树(英文名: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,表示该结点已无路径覆盖)。

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

三:完整代码

/**
 *
 * author : 刘毅(Limer)
 * date   : 2017-08-08
 * mode   : C++
 */

#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);
}

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;
}

四:不足及改进

我们发现,每个结点,其内部都有一个指针数组,在稀疏树下,大多空间被浪费。

因此针对上面问题,人们提出了两种改进结构:二数组字典树三数组字典树。具体可阅本系列第二篇。

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论

12 条评论
  1. 被大风吹跑 被大风吹跑

    文章挺好的,另外请问博主的图是用什么软件画的,我一直画这种图都是word手撸,,感觉太麻烦了

    1. @被大风吹跑http://ngwin.com/picpick ,这个软件挺好用的,有免费版的

    2. 被大风吹跑 被大风吹跑

      @刘毅谢谢博主了,原来这软件还可以画图,我一直当作离线截图工具用的。。@(笑尿)

  2. 博主,没有找到你的二数组字典树和三数组字典树呀。其它文章讲的很好,非常容易理解。

    1. @松鼠先生@(乖)还没写

    2. @刘毅有空写一下了,帮助下我这种基础比较差的。

    3. @松鼠先生#(喜极而泣)忙,看情况

  3. Kevin Kevin

    remove()函数,最下面的return语句,应该是return true; ^_^

    1. Kevin Kevin

      @Kevin 也不对,应该是t->end--; 下面加一个return true;

    2. @Kevin写的太粗心了,已改正

    3. Kevin Kevin

      @刘毅已经很不错了@(哈哈) 你的博客思路很清晰,每一篇我都会关注,向你学习@(大拇指)

  4. themebetter博客导航已收录贵站,期待博主分享更多的精彩内容。