详解字典树Trie结构及其Python代码实现(字典树原理)

编辑：rootadmin

推荐整理分享详解字典树Trie结构及其Python代码实现(字典树原理)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:字典树算法,字典树算法,字典树模板,字典树算法,字典树的作用,字典树的作用,什么是字典树,什么是字典树,内容如对您有帮助，希望把文章链接给更多的朋友！

字典树（Trie）可以保存一些字符串->值的对应关系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不过 Trie 的 key 只能是字符串。Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ，其中 k 为 key 的长度，与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的，但在计算 hash 的时候就肯定会是 O(k) ，而且还有碰撞之类的问题；Trie 的缺点是空间消耗很高。至于Trie树的实现，可以用数组，也可以用指针动态分配，我做题时为了方便就用了数组，静态分配空间。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。Trie树中每个单词都是通过character by character方法进行存储，相同前缀单词共享前缀节点.可以看到,每条路径组成一个单词.上面这颗树存了to/tea/ted/ten/inn这些词.

Trie树的基本性质可以归纳为：（1）根节点不包含字符，除根节点意外每个节点只包含一个字符。（2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。（3）每个节点的所有子节点包含的字符串不相同。

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

基本思想（以字母树为例）：1、插入过程对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。2、查询过程同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。

应用（1）词频统计比直接用hash节省空间（2）搜索提示输入前缀的时候提示可以构成的词（3）作为辅助结构如后缀树，AC自动机等的辅助结构

实现虽然Python没有指针,但是可以用嵌套字典来实现树结构.对于非ascii的单词,统一用unicode编码来插入与搜索.

详解duck typing鸭子类型程序设计与Python的实现示例在程序设计中，鸭子类型（英语：ducktyping）是动态类型的一种风格。在这种风格中，一个对象有效的语义，不是由继承自特定的类或实现特定的接口，

Python的Django中将文件上传至七牛云存储的代码分享最近在写的一个django小项目需要实现用户上传图片的功能，使用到了七牛云存储，特此记录下来。这里我使用的七牛pythonSDK版本是7.0.3，函数使用上可能

使用Python的Flask框架来搭建第一个Web应用程序 1、初始化在这章，你将学到Flask应用程序的不同部分。同时，你将编写和运行你的第一个Flaskweb应用程序。所有的Flask应用程序都必须创建一个应用程序