树
1. 树与二叉树
1.1. 基本概念
- 节点
- 根节点
- 叶子节点
- 父节点
- 子节点
- 兄弟节点
- 高低相关
- 高度
- 深度
- 层
1.2. 如何存储二叉树
- 二叉树
- 满二叉树
- 完全二叉树
- 存储方案
- 链式存储
- 数组存储
完全二叉树的优势在于其方便于用数组存储。
用数组存储的完全二叉树中,若 X 节点在 a[i] ,那么它的左子节点在 a[2*i] ,右子节点在 a[2*i] + 1 。
为了方便,将根节点放在 a[1] 。
1.3. 遍历(递归)
- 前序遍历
- 先输出自身,再遍历左子树,接者遍历右子树
- 中序遍历
- 先遍历左子树,再输出自身,接者遍历右子树
- 后序遍历
- 先遍历左子树,再遍历右子树,接着输出自身
实际上,二叉树的前、中、后序遍历就是一个递归的过程
2. 二叉查找树(BSTBST)
二叉查找树要求,在树中的任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,而右子树节点的值都大于这个节点的值。
2.1. 二叉查找树的增删改查
-
查找
- 如果要查找的数据比根节点的值小,那就在左子树中递归查找;如果要查找的数据比根节点的值大,那就在右子树中递归查找。
-
插入
- 如果要插入的数据比节点的数据大,并且节点的右子树为空,就将新数据直接插到右子节点的位置;如果不为空,就再递归遍历右子树,查找插入位置。同理,如果要插入的数据比节点数值小,并且节点的左子树为空,就将新数据插入到左子节点的位置;如果不为空,就再递归遍历左子树,查找插入位置。
-
删除
- 第一种情况是,如果要删除的节点没有子节点,我们只需要直接将父节点中,指向要删除节点的指针置为 null。
- 第二种情况是,如果要删除的节点只有一个子节点(只有左子节点或者右子节点),我们只需要更新父节点中,指向要删除节点的指针,让它指向要删除节点的子节点就可以了。
- 第三种情况是,如果要删除的节点有两个子节点,这就比较复杂了。我们需要找到这个节点的右子树中的最小节点,把它替换到要删除的节点上。然后再删除掉这个最小节点,因为最小节点肯定没有左子节点(如果有左子结点,那就不是最小节点了),所以。左子树最大节点也可以。
-
其他操作
- 查找最大节点—直接向右遍历到底
- 查找最小节点—直接向左遍历到底
- 查找前驱节点—找到当前节点,对其左子树进行向右遍历到底
- 查找后继节点—找到当前节点,对其右子树进行向左遍历到底
-
中序遍历二叉查找树,可以输出有序序列,时间复杂度是 O(n),故又名“二叉排序树”
2.2. 支持重复数据的二叉查找树
在实际的软件开发中,很多时候在二叉查找树中存储的,是一个包含很多字段的对象。可以使用对象的某个字段作为键值(key)来构建二叉查找树。对象中的其他字段叫作卫星数据。
那如果存储的两个对象键值相同,这种情况该怎么处理呢?
第一种方法,二叉查找树中每一个节点不仅会存储一个数据,通过链表和支持动态扩容的数组等数据结构,把值相同的数据都存储在同一个节点上。
第二种方法,每个节点仍然只存储一个数据。在查找插入位置的过程中,如果碰到一个节点的值,与要插入数据的值相同,我们就将这个要插入的数据放到这个节点的右子树,也就是说,把这个新插入的数据当作大于这个节点的值来处理。
当要查找数据的时候,遇到值相同的节点,不停止查找操作,而是继续在右子树中查找,直到遇到叶子节点,才停止。这样就可以把键值等于要查找值的所有节点都找出来。对于删除操作,需要先查找到每个要删除的节点,然后再按删除操作的方法,依次删除。
2.3. 时间复杂度
二叉查找树时间复杂度极不稳定,最差退化成链表,查找时间复杂度 O(n) 。
二叉查找树是一个完全二叉树的时候,时间复杂度其实都跟树的高度成正比,也就是 O(height)。借助等比数列的求和公式,我们可以计算出,L 的范围是 [ l o g 2 ( n + 1 ) , l o g 2 n + 1 ] [log_2(n+1), log_2n +1] [log2(n+1),log2n+1]。完全二叉树的层数小于等于 l o g 2 n + 1 log_2n +1 log2n+1,也就是说,完全二叉树的高度小于等于 l o g 2 n log_2n log2n。
2.4. 二叉查找树与散列表
二叉查找树最大的特点就是,支持动态数据集合的快速插入、删除、查找操作。散列表也是支持这些操作的,并且散列表的这些操作比二叉查找树更高效,时间复杂度是 O(1)。既然有了这么高效的散列表,使用二叉树的地方是不是都可以替换成散列表呢?有没有哪些地方是散列表做不了,必须要用二叉树来做的呢?
- 散列表中的数据是无序存储的,如果要输出有序的数据,需要先进行排序。而对于二叉查找树来说,我们只需要中序遍历,就可以在 O(n) 的时间复杂度内,输出有序的数据序列。
- 散列表扩容耗时很多,而且当遇到散列冲突时,性能不稳定,尽管二叉查找树的性能不稳定,但是在工程中,我们最常用的平衡二叉查找树的性能非常稳定,时间复杂度稳定在 O(logn)。
- 笼统地来说,尽管散列表的查找等操作的时间复杂度是常量级的,但因为哈希冲突的存在,这个常量不一定比 logn 小,所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高。
- 散列表的构造比二叉查找树要复杂,需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定。
- 为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间。
- 综合这几点,平衡二叉查找树在某些方面还是优于散列表的,所以,这两者的存在并不冲突。我们在实际的开发过程中,需要结合具体的需求来选择使用哪一个。