数据结构基础17———非线性数据结构之Trie字典树

想象一下我们查字典时的操作:

image.png

可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子,1 - 4 - 8 - 12表示的就是字符串 caa 。

Trie 的结构非常好懂,我们用表示结点 u 的 c字符指向的下一个结点,或着说是结点 代表的字符串后面添加一个字符 形成的字符串的结点。( c 的取值范围和字符集大小有关,不一定是 0 -26 )

有时需要标记插入进 Trie 的是哪些字符串,每次插入完成时在这个字符串所代表的节点处打上标记即可。

异或相关
将数的二进制表示看做一个字符串,就可以建出字符集为{0,1}的 Trie 树。

在树的构建过程中我们都会定义一个节点放到右边还是左边,而这个规则不仅仅可以单纯的用于值的大小比较,也可以自定义规则(如:基于节点值的前缀或后缀进行以及基数等延伸)。结合我们之前学习过的散列表,同样的方法我们也可以放到树中,通过对要放入的内容进行hash作为Key放到对应的节点中。而前缀树也可视为Hash树的一种实现

施工,暂缓

详细讲解需要前置讲字符串匹配BM,RK算法,hash树

深入要讲KMP算法,AC自动机,SAM等等一大堆。

简单的讲类比生活中的查字典就可以了又没啥讲的...

字典树,英文名 Trie。顾名思义,就是一个像字典一样的树。

更新时间:2020-02-13 15:37:33

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础17非线性数据结构之trie字典树
最后更新:2020-02-13 15:37:33

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×