树

「树」这种数据结构很像我们现实生活中的「树」，这里面每个元素我们叫做「节点」；用来连接相邻节点之间的关系，我们叫做「父子关系」。

关于「树」，还有三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）。它们的定义是这样的：

节点的高度：节点到子节点最长路径。
节点的深度：根节点到子节点所经历的边的个数。
节点的层数：节点的深度加一。
树的高度：根节点的高度。

「高度」这个概念，其实就是从下往上度量，比如我们要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

「深度」这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

「层数」跟深度的计算类似，不过，计数起点是 1，也就是说根节点位于第 1 层。

• 二叉树，又称为二叉搜索树，二叉有序树。指一棵空树或左子树所有节点均小于根节点的值，或右子树所有节点均大于根节点的值。
• 每个节点都有左右两个子节点，这种二叉树就叫做满二叉树。
• 叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫做完全二叉树。

树的遍历方式

• 前序遍历：根左右。
• 中序遍历：左根右。
• 后序遍历：左右根。

链表是特殊化的树，树是特殊化的图

图

• 图和树的区别是有环
• 图的属性有点和边。
• 图的分类：无向无权图、有向无权图、无向有权图
• 常见算法：最小生成树、最短路径、连通图个数、拓扑排序

堆

• 什么是堆：可以快速找到一堆数中最大值或最小值的数据结构
• 堆是一个完全二叉树
• 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值
• 常见堆有：二叉堆、斐波那契堆
• 根节点最大堆称为大根堆或大尖堆
• 根节点最小堆称为小根堆或小尖堆

应用场景：Top K 问题，即查找最大值或最小值

哈希表

• 什么是哈希表：哈希表又称为散列表，是根据 key value 进行访问的数据结构

应用场景：安全加密，唯一标识，数据校验，散列函数，负载均衡，数据分片，分布式存储

散列表与二叉查找树的对比

• 第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。

• 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。

• 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。

• 第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。

• 最后，为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

• 综合这几点，平衡二叉查找树在某些方面还是优于散列表的，所以，这两者的存在并不冲突。我们在实际的开发过程中，需要结合具体的需求来选择使用哪一个。

nick

微信支付

支付宝