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

简介: 提到数据结构中的树(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

目录
相关文章
|
10月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
266 0
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
157 3
 算法系列之数据结构-Huffman树
|
6月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
505 19
|
8月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
193 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
8月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
183 12
|
8月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
164 10
|
11月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
342 64
|
8月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
259 3
|
10月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
279 5
|
10月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
392 16