Trie树简介
2024-10-05 02:52:37
Trie树，
即字典树，
又称单词查找树或键树，
多叉树
基本性质
根节点不包含字符，除根节点外每一个节点都只包含一个字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同
本质：
利用字符串之间的**公共前缀**，将重复的前缀合并在一起
主要操作
构造trie 树
在Trie 树中查询一个字符串
存储
借助散列表存储
这种存储方法在公共前缀不多和字符串包含的字符集复杂（中英文，大小写）时会占用很多时间
可以稍微牺牲一些查询效率，将每个节点的数据结构换成其它数据结构，来存储一个节点的子节点指针（有序数组，跳表、红黑树）
应用场景：
不适合精确匹配查找，
适合公共前缀查找
搜索关键词提示功能
自动输入补全（IDE、浏览器、输入法）
单词纠错
核心思想
空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的最新文章
- Jdk与Tomcat配置与安装
- iOS开发之SQLite--C语言接口规范(三)——Binding Values To Prepared Statements
- 全国DNS服务器IP地址【电信、网通、铁通】
- 字符串匹配--Karp-Rabin算法
- HDU 1838 Chessboard
- Storm系列(十三)架构分析之Worker-维护ZMQ连接
- Install Oracle 11gR2 on Debian wheezy(转)
- 《JAVA与模式》之单例模式 [转]
- 20155215 2016-2017-2 《Java程序设计》第5周学习总结
- ASP.NET Core学习之一 入门简介
- ZooKeeper 01 - 什么是ZooKeeper + 部署ZooKeeper集群
- 用Pytorch训练MNIST分类模型
- noip第22课资料
- OpenStack 安装：基本环境准备
- 【手记】解决Resharper 2018.x起本机license server不能用的问题
- How to get the value of a form element : check box and radio button
- http 之 HTTP_X_FORWARDED_FOR
- SVN服务器搭建和使用以及冲突解决、用户密码修改
- JQ + CSS实现浪漫表白必备
- 转 dockerfile 介绍 及 编写