什么是树?了解哪些树结构?
导读
「什么是树?了解哪些树结构?」的回答要点集中在下面几节,建议先记住结论再看推导过程。
核心解析
从定义上来说,树,就是由节点和边组成,且不存在环的一种数据结构。
从实现上来讲,树一般通过链表来实现。
从结构上分,树可分为二叉树和多叉树。一般我们在写算法的时候,使用二叉树和字典树比较多。
除此之外,
- B*树一般用于数据库的索引,特点是由多个子树,高度很低,可以减少磁盘IO;
- 霍夫曼树一般通过哈夫曼编码做数据的无损压缩;(这个是大学数据结构的必修内容,但是面试一般不考)
- 红黑树和平衡二叉树因为是有序的,所以经常用于二分查找,红黑树相对于平衡二叉树的优点是,不要求树完全平衡,这就会降低数据更新时候的时间复杂度。Java中的HashMap就会通过红黑树来进行查找;
- 字典树一般是针对一组字符串进行维护的数据结构,它可以将共同前缀的字符串进行优化,节省存储空间,同时可以快速查询某个字符串是否出现。(在LeetCode Hard中比较常见)
树的分类如下所示:

- 注意:上图中的字典树就是Tire树,
平衡二叉树(AVL树):一种自平衡的二叉搜索树,其中任何节点的两个子树的高度差都不超过1。
红黑树:一种自平衡的二叉搜索树,它通过节点颜色(红色或黑色)和特定的性质来维持大致平衡,以确保操作的时间复杂度保持在对数级别。
B树和B+树:常用于数据库和文件系统中的多路搜索树,它们通过保持树的平衡和低高度来优化磁盘访问。
前缀树(Trie树):一种用于快速检索字符串集合的树形数据结构,节点路径形成的字符串可以快速定位。
延伸阅读
二叉查找树的演变和区别?
什么是字典树?
什么是前缀树?
要点小结
- 从定义上来说,树,就是由节点和边组成,且不存在环的一种数据结构。
- 除此之外, 1. B树一般用于数据库的索引,特点是由多个子树,高度很低,可以减少磁盘IO
由站内小编编辑整理