19-看图理解数据结构与算法系列(Radix树)
Radix树
Radix树,即基数树,也称压缩前缀树,是一种提供key-value存储查找的数据结构。与Trie不同的是,它对Trie树进行了空间优化,只有一个子节点的中间节点将被压缩。同样的,Radix树的插入、查询、删除操作的时间复杂度都为O(k)。
Radix树特点
- 一般由根节点、中间节点和叶子节点组成。
- 每个节点可以包含一个或多个字符。
- 树的叶子结点数即是数据条目数。
- 从根节点到某一节点经过路径的字符连起来即为该节点对应的字符串。
- 每个节点的所有子节点字符串都不相同。
插入操作
对romane、romanus、romulus、rubens、ruber、rubicon、rubicundus七个字符串进行插入,开始插入romane,此时树为空,直接创建一个“romane”节点,并将该节点结束标记设为true,随即完成romane的插入。
接着插入romanus,此时根节点已经不为空,于是从根节点开始逐个字符进行比较,发现两者前缀“roman”相同,需要分割原来的“romane”节点,先创建一个新的公共前缀“roman”节点,
然后将原来的“romane”节点设为“e”,“e”是“romane”除去公共前缀“roman”后剩下的字符,并将新的公共前缀节点指向“e”子节点,子节点索引为“e”。
接着继续创建一个新的“us”节点,“us”是“romanus”除去公共前缀“roman”后剩下的字符,
最后将公共前缀“roman”节点指向“us”子节点,索引为“u”,并将“us”节点结束标记设为true。
往下插入romulus,从根节点开始逐个字符进行比较,发现两者前缀“rom”相同,需要分割原来的“roman”节点,先创建一个新的公共前缀“rom”节点,
然后将原来的“roman”节点设为“an”,“an”是“roman”除去公共前缀“rom”后剩下的字符,并将新的公共前缀节点指向“an”子节点,子节点索引为“a”。
接着继续创建一个新的“ulus”节点,“ulus”是“romulus”除去公共前缀“rom”后剩下的字符,
最后将公共前缀“rom”节点指向“ulus”子节点,索引为“u”,并将“ulus”节点结束标记设为true。
继续插入rubens,从根节点开始逐个字符进行比较,发现两者前缀“r”相同,需要分割原来的“rom”节点,先创建一个新的公共前缀“r”节点,
然后将原来的“rom”节点设为“om”,“om”是“rom”除去公共前缀“r”后剩下的字符,并将新的公共前缀节点指向“om”子节点,子节点索引为“o”。
接着继续创建一个新的“ubens”节点,“ubens”是“rubens”除去公共前缀“r”后剩下的字符,
最后将公共前缀“r”节点指向“ubens”子节点,索引为“u”,并将“ubens”节点结束标记设为true。
继续插入ruber,从根节点开始逐个字符进行比较,发现比较完“r”后根节点已经没有值可以比较了,于是开始找“r”节点的子节点,
根据第二个字符“u”找到对应的子节点,即“ubens”节点,
剩余的“uber”字符串继续与该节点进行逐一比较,发现两者前缀“ube”相同,需要分割原来的“ubens”节点,先创建一个新的公共前缀“ube”节点,
然后将原来的“ubens”节点设为“ns”,“ns”是“ubens”除去公共前缀“ube”后剩下的字符,并将新的公共前缀节点指向“ns”子节点,索引为“n”,此外,原来指向“ubens”节点的“u”索引指向“ube”节点。
接着继续创建一个新的“r”节点,“r”是“ruber”除去公共前缀“r”和“ube”后剩下的字符,
最后将公共前缀“ube”节点指向“r”子节点,索引为“r”,并将“r”节点结束标记设为true。
类似地,将rubicon插入树中,结果如下。
继续插入rubicundus,结果如下。
查询操作
假如查找ruok,从根节点开始比较,“r”相等且根节点已经没有值可以继续比较,
于是根据“u”索引找下一个子节点,在“ub”子节点中继续逐一字符比较,
发现没法匹配上“uok”,不存在“ruok”,于是查找结束。
假如查找rubicon,从根节点开始比较,“r”相等且根节点已经没有值可以继续比较,
于是根据“u”索引找下一个子节点,在“ub”子节点中继续逐一字符比较,
比较完该节点后继续根据“i”索引找子节点,在“ic”节点中继续逐一字符比较,
比较完该节点后继续根据“o”索引找子节点,在“on”节点中继续逐一字符比较,此时“rubicon”已经完成所有字符的比较,而且“on”节点的结束标记为true,也就是说存在“rubicon”字符串,查找结束。
假如查找roman,从根节点开始比较,“r”相等且根节点已经没有值可以继续比较,
于是根据“o”索引找下一个子节点,在“om”子节点中继续逐一字符比较,
比较完该节点后继续根据“a”索引找子节点,在“an”节点中继续逐一字符比较,此时“roman”已经完成所有字符的比较,但“an”节点的结束标记为false,所以“roman”字符串不存在,查找结束。
作者:超人汪小建
链接:https://juejin.im/post/5bdf8f6de51d4505525b1118
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
最新文章
- React-Native性能优化点
- javascript base64 字符转换
- linux查看系统版本和系统位数
- 【原】iOS学习之Swift之语法2(精简版)
- winform下自绘提示框风格窗体
- mysql主主复制(双主复制)配置步骤
- 用mtrace检查内存泄漏
- Sersync实现触发式文件同步 替代inotify和rsync
- maxscript,#号和$号
- 爱重启的windows,伤不起
- ASP.NET Web – AJAX 回送
- javascript 事件 第23节
- iOS多Targets管理
- C# WinForm判断Win7下是否是管理员身份运行
- 黑马程序员:Java基础总结----枚举
- call, apply,bind 方法解析
- 浅谈python模块的导入操作
- linux常用命令汇总(更新中...)
- su: authentication failure 解决方法
- ui自动化:python+appium----环境搭建
热门文章
- 人工智能-深度学习(3)TensorFlow 实战一:手写图片识别
- 2017 JUST Programming Contest 3.0 D. Dice Game
- Struts2 表单提交与execute()方法的结合使用
- 配置Oracle监听器
- 关于通过spring-web的ServletRequestUtils工具类对获取getParameter传参的默认转换基本数据类型的学习
- Java核心技术梳理-异常处理
- Myeclipse 6.0代码
- Selenium--Python环境部署
- 将Jenkins的测试结果整合到Testlink
- 内存管理总结-autoreleasePool