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) 快。加上哈希函数的耗时,也不一定就比平衡二叉查找树的效率高。
  • 散列表的构造比二叉查找树要复杂,需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题,而且这个问题的解决方案比较成熟、固定。
  • 为了避免过多的散列冲突,散列表装载因子不能太大,特别是基于开放寻址法解决冲突的散列表,不然会浪费一定的存储空间。
  • 综合这几点,平衡二叉查找树在某些方面还是优于散列表的,所以,这两者的存在并不冲突。我们在实际的开发过程中,需要结合具体的需求来选择使用哪一个。