开发者社区> yanglbme> 正文

心中有“树”!图文并茂介绍数据结构中常见的树(一)

简介: 提到数据结构中的树(Tree) ,大家应该都不陌生,相关书籍中都有大段篇幅的介绍,刷 Leetcode 的时候会遇到很多相关问题。很多人往往会用 “手写红黑树” 来形容面试难度很高。
+关注继续查看

提到数据结构中的树(Tree) ,大家应该都不陌生,相关书籍中都有大段篇幅的介绍,刷 Leetcode 的时候会遇到很多相关问题。很多人往往会用 “手写红黑树” 来形容面试难度很高。


那么,除了红黑树之外,还有哪些常见的树结构?它们被用在什么领域?又解决了什么问题?接下来,我们就用几篇文章,来给大家做一个简单的介绍。


大家好,我是不会写代码的纯序员——Chunel Feng。各位绅士们,很高兴我们又在这里见面了。


刷 leetcode 的童鞋,肯定写过二叉树的遍历、递归、查询等逻辑,笔试的时候 6 的飞起,人均 sp。但很多童鞋可能也会有这样一种感觉:这些东西只能应付面试,不实用,工作了好好几年了,根本没用过。


其实,我们在工作中接触到的很多东西,底层的本质就是一棵树型结构,只是有前人为我们造好了屏蔽实现细节的轮子,才让我们的工作变得如此丝滑。举两个常见的例子:C++里的 std::set 和 std::map 结构,底层就是一颗树;常见的数据库存储引擎,底层也是树型结构。


27.png


那么,常用的数据结构里还有哪些常见树呢?它们又会被应用在哪里?用于解决什么样的问题? 下面,我们就从以上几个问题入手,来介绍一下我所知道的一些 Tree 方面的知识,希望对大家有所帮助。


在开始之前,首先说明,本文偏科普和综述,并不会对每种树做非常详细的介绍,也不会上什么类似红黑树旋转的代码。主要目的是让大家知道有这些内容,如果今后有需要用到的地方,自己查缺补漏即可。本人水平有限,如果有描述的错误或遗漏,也欢迎大家随时补充和交流。


下面我们正式开始:


二叉树


BST 搜索二叉树 Binary Search Tree


树,最常见的用法,就是用于数值查找。通过在建树的时候,将大于 root 的值放到右边、小于 root 的值放到左边,即可在查询的时候,减少比较次数,实现加速查询。


28.png


但是,随着数据的插入越来越多,树的结构会造成扭曲(不平衡)。比如,往 bst 中插入一个递增数组的时候,普通的 BST 会退化成一个链表,从而严重影响查询性能。


AVL 平衡二叉树 Height-Balanced Binary Search Tree


于是,AVL 平衡二叉树诞生了。AVL 的名字,取自于作者 Adelson-VelskiiLandis 的首字母缩写(纯序员暗自感慨,如果是第一位作者独立发明的话,那数据结构课上就又多了个话题)。


29.png


AVL 树通过在插入过程中的旋转逻辑,使得树的自身高度差严格控制在 1 之内,从而解决了退化成 list 的问题。但是,频繁的旋转增加了树构建的成本。


RBT 红黑树 Red Black Tree


为了降低树构建时的成本,红黑树诞生了。红黑树通过将节点设定成 Red or Black,和同一条边中 Black 节点的数量相同等约束条件,在保证了树基本平衡的情况下,优化了自旋转流程。


红黑树可以有效的平衡建树时的旋转次数和查找时的退化问题,并且也在实际编程中得到了广泛的应用。比如 C++中的 std::map 和 Java 里的 TreeMap 的底层就是一颗红黑树,nginx 和 epoll 源码中也有所使用。


30.png


字典树


Trie 前缀树


Trie 树是常见的字典树,通常被用于字符串查询和排序。它的形式,是在根节点的所有路径中,有序的依次存入一个对应字符。这样做,一方面可以降低海量字符串存储所占用的空间,另一方面也使得字符串得以有序的排列,同时也可以记录重复出现次数。


31.png


这算是搜索引擎里最最最简单的样例吧,记住哦,面试中经常问的。想继续往搜索引擎方面了解一些的童鞋,可以看一下 FST(Finite State Transducers,有限状态转移机),这个就不属于【树】的范畴了,我们不在这里讨论了。


Radix 压缩前缀树,也叫基数树


样子跟前面提到的 Trie 树有点相似。相比于 Trie 中一个一个往下追加的流程,Radix 在插入的时候通过分裂机制使得仅包含一条链路的字符【压缩】到一起。从而在保持原有查询、排序功能的前提下,进一步降低了数据的存储占用量。顺便说一句,Radix 树中的节点,还适合用于存放类似 .*? 这种正则匹配相关的信息。


32.png


一图胜千言,看到上面这个图,我想大家应该都懂了。Radix 树有一个常见的应用,就是文件路径查找或匹配,这一点做前后端交互的朋友应该有所涉及。


/usr/local/include/         (14KB)/usr/local/bin/             (25KB)/usr/study/book/            (3MB)/usr/study/.video/          (380GB)...


比如,我电脑中的文件夹分类吧,用 Radix 树存储的话,就比 Trie 节省了很多空间,因为 /usr,/local,/study这几个信息,明显是可以合并到一个节点中的。


Suffix tree 后缀树


上面聊到的两种字典树,都属于前缀树,其实还有后缀树。后缀树是对一个长字符串的详尽描述(注意,是一个 string 对应一棵后缀树,不是海量 string 放到一棵树上)。树的每条路径记录了一个后缀信息,后缀下标用于记录从第 x 个字符开始计算,从而简化的查询流程。主要用途有:字符串匹配,查找最长公共子串,查找最长重复子串等


33.png


这个讲起来有点复杂,有兴趣的朋友可以去 B 站搜索:轻松掌握 suffix tree[1] ,讲的非常通俗易懂,墙裂推荐。


本章小节


本章是这个系列的第一篇内容,主要是聊了我写这个系列的文章的出发点和目的,也简单介绍了几种类型的树,并梳理了他们的使用场景和异同,希望对大家有所帮助。

在这个系列接下来的几篇文章中,我们还会继续给大家介绍一些常见的树结构,比如lsm 树,kd 树、哈夫曼树等等。


引用链接


[1] 轻松掌握 suffix tree: https://www.bilibili.com/video/BV1c741137GD?spm_id_from=333.999.0.0

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
19812 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
29196 0
阿里云服务器安全组设置内网互通的方法
虽然0.0.0.0/0使用非常方便,但是发现很多同学使用它来做内网互通,这是有安全风险的,实例有可能会在经典网络被内网IP访问到。下面介绍一下四种安全的内网互联设置方法。 购买前请先:领取阿里云幸运券,有很多优惠,可到下文中领取。
22540 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
16465 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
20710 0
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23586 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14901 0
+关注
73
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载