文档章节

字典树

o
 osc_fmg49rzg
发布于 2019/03/22 08:19
字数 802
阅读 11
收藏 0

1.概念

1)Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构,如小写英文字母的字典树是一个26叉树,数字的字典树是一个10叉树

2)Trie树利用字符串的公共前缀来节约存储空间,字典树存放具有公共前缀的字符串们非常节省空间,相反,对于大量没有公共前缀的字符串,用字典树存就会很消耗内存

3)一个保存了8个key的trie结构,"A", "to", "tea", "ted", "ten", "i", "in", and "inn".如下图所示

2.字典树的三个性质

1)根节点不包含字符,除根节点意外每个节点只包含一个字符

2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串

3)每个节点的所有子节点包含的字符串不相同

3.字典树的实现

3.1基本原理

字母树的插入(Insert)、删除( Delete)和查找(Find)都非常简单,用一个一重循环即可,即第i 次循环找到前i 个字母所对应的子树,然后进行相应的操作。实现这棵字母树,我们用最常见的数组保存(静态开辟内存)即可,当然也可以开动态的指针类型(动态开辟内存)。至于节点对儿子的指向,一般有三种方法:

1)对每个结点开一个字母集大小的数组,对应的下标是儿子所表示的字母,内容则是这个儿子对应在大数组上的位置,即标号;

2)对每个结点挂一个链表,按一定顺序记录每个儿子是谁;

3)使用左儿子右兄弟表示法记录这棵树。

3.2代码实现

struct TrieNode {
    TrieNode* childs[26];//最多26个儿子
    string word;//截止到自己这里是否形成的单词,如果只是前缀,则word为空
    int count = 0;//所存单词的个数
    TrieNode() :word("") {
        for (auto& child : childs)
            child = NULL;
    }
};
class Trie {
public:
    TrieNode* root;
    /** Initialize your data structure here. */
    Trie() {
        root = new TrieNode();
    }
    //三五法则
    Trie(const Trie& rhs) {
        root = new TrieNode(*rhs.root);
    }
    //三五法则
    Trie& operator = (const Trie& rhs)
    {
        if (this != &rhs)
        {
            TrieNode* temp = new TrieNode(*rhs.root);//先new再delete,为什么,如果内存不足,new不出来抛出异常,在这就停住了
            delete root; //就不会执行delete root,root还可以保持原值
            root = temp;
        }
        return *this;
    }

    //必须要自定义析构函数,因为构造函数new了
    ~Trie() {
        delete root;
    }

    /** Inserts a word into the trie. */
    void insert(string word)
    {
        TrieNode* temp = root;
        for (char c : word)
        {
            int i = c - 'a';
            if (temp->childs[i] == NULL)
                temp->childs[i] = new TrieNode();
            else
                temp = temp->childs[i];
        }
        if(temp->word.empty())
            temp->word = word;
        ++temp->count;
    }

    /** Delete a word in the trie. */
    bool del(string word)//这个del函数只能删单词,不会删那些前缀的节点
    {
        TrieNode* temp = root;
        for (char c : word)
        {
            int i = c - 'a';
            if (temp->childs[i] != NULL)
                temp->childs[i] = temp->childs[i];
            else
                return false;
        }
        if (--temp->count == 0)
            temp->word = "";
    }

    /** Returns if the word is in the trie. */
    bool search(string word)
    {
        TrieNode* temp = root;
        for (char c : word)
        {
            int i = c - 'a';
            if (temp->childs[i] != NULL)
                temp = temp->childs[i];
            else
                return false;
        }
        return temp->word.size() == word.size();
    }
};

参考资料:

http://www.cnblogs.com/grandyang/p/4491665.html

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

树莓派4b + Ubuntu20.04 Server 安装Java8

安装环境: 树莓派4b + Ubuntu20.04 Server 32位 1. 下载jdk https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 2. 解压 tar -zxvf jdk-8u251-linux-arm32-vf......

SummerGao
34分钟前
9
0
项目实战:Qt+OpenCV图像处理与识别算法平台

若该文为原创文章,未经允许不得转载 原博主博客地址:https://blog.csdn.net/qq21497936 原博主博客导航:https://blog.csdn.net/qq21497936/article/details/102478062 本文章博客地址:h...

红模仿_红胖子
37分钟前
7
0
北京智源大会 | AI + 医疗的下一个十年:从公共卫生预警到人类基因密码破解 道翰天琼认知智能api机器人接口。

医疗事关人身安全,要求极高,容错率极低,因此,知识壁垒和技术壁垒都很高。过去,AI系统更多的是服务于终端,辅助医生诊断、决策。但是,医疗很复杂,直接切入终端问题很多。未来十年,AI+...

jackli2020
41分钟前
11
0
源于HystrixCommandStartStream和RollingCommandMaxConcurrencyStream 的 RxJava demo

其实,最近在工作之余看Hystrix源代码已经有一个多月了, 除了对 HystrixCommandProperties ,HystrixCommand 和AbstractCommand 几个类比较了解以外,其余看山不是山,比较懵, 主要是因为H...

专业写BUG的程序员
44分钟前
16
0
聊聊Java中的异常及处理

前言 在编程中异常报错是不可避免的。特别是在学习某个语言初期,看到异常报错就抓耳挠腮,常常开玩笑说编程1分钟,改bug1小时。今天就让我们来看看什么是异常和怎么合理的处理异常吧! 异常...

良许Linux
47分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部