数据结构之二叉搜索树

568 阅读6分钟

预计阅读时间:10分钟

二叉搜索树(BST)是一种特殊的二叉树,它满足以下两个特性:

  • 每个节点的值必须大于(或等于) 其左子树的所有节点的值。
  • 每个节点的值必须小于(或等于) 其右子树的所有节点的值。

bst


一、二叉搜索树优点

二叉搜索树,支持快速查找、插入、删除操作和其他操作。

1. 查找操作

查找过程如下:取根节点,如果根节点等于我们要查找的数据,直接返回。如果大于根节点的值,那就往左子树递归查找。如果小于根节点的值,那就往右子树递归查找。

2. 插入操作

插入过程类似于查找:首先,取根节点,比较待插入节点和根节点的值,如果大于根节点则往右子树递归查找插入位置,如果是空位置则直接插入。如果小于根节点的值则往左子树递归查找插入位置,如果是空位置则直接插入。

3. 删除操作

删除过程比较复杂(为了维持二叉搜索树的特性):首先当然得查找到该待删除的节点。然后删除该节点,此时有三种情况:

(1) 该节点是叶子节点。可以直接删除该节点,即将该节点置为NULL!

(2) 该节点有一个节点(左子节点或右子节点)。为了维持二叉搜索树的特性,我们可以将待删除节点父节点直接指向待删除节点的子节点。因为对于一棵树的根节点,该根节点的左子树中的所有节点都小于该根节点的值,该根节点的右子树中的所有节点都大于该根节点(二叉搜索树定义 )。 因此我们可以删除某个拥有一个子节点的节点,可以直接让该子节点代替待删除的节点的位置,仍然满足二叉搜索树特性。

(3) 该节点有两个子节点。因为有两个子节点,无法像情况2一样。我们需要找该节点右子树中的最小节点,代替待删除节点的位置,然后再删除这个最小节点。最小节点一定没有左子节点,因此我们可以用情况1或2来删除该最小节点。这样我们的二叉搜索树就成功删除了节点,并且保持了自身的特性。

4. 其他操作

二叉搜索树还支持快速获得最大节点和最小节点、输出有序的数据序列(通过中序遍历)。


二、二叉搜索树的效率

前面说二叉搜索树支持快速查找、插入、删除和其他操作。快速具体有多快?

BST
例如上面图,我们要查找任何一个节点,需要的步骤总数都小于等于树的深度(该树深度为4)。对于一颗有n个节点的二叉树,如果是一颗完全二叉树,则此时树的深度是最小的,深度为\lfloor log_2(n) \rfloor+1 。如果是一颗链树(树退化成了链表,如下图),则此时树的深度是最大的,就等于节点的个数n。其他任意的二叉树的深度都介于这两种树的深度之间。
BST

因此,我们在二叉搜索树中,查找一个节点的步骤数是随二叉搜索树节点对数增长的。对数增长是很慢的,比线性增长慢很多。

二叉搜索树的插入、搜索就是在查找的基础上,多了几个附加操作,步骤数整体还是对数增长。

即,二叉树的查找、插入、删除操作的时间复杂度都是O(log(n))级别的。输出有序序列需要遍历整个二叉搜索树,时间复杂度是O(n)级别。


三、二叉搜索树的存储结构

二叉搜索树属于二叉树,因此存储结构与二叉树是一样的。有两种存储方式:

1. 数组存储

数组存储适用于完全二叉树,否则将浪费大量空间。如下图:

BST
图中空表示没有节点,可以看出对于非完全二叉树来说,用数组存储需要更多空间,并且许多空间白白浪费掉了(这些空间用来填充成完全二叉树,以便编号公式有效)。对于n个节点的二叉树,需要2^n-1个存储单元。因此一般完全二叉树都用数组存储,既节约空间(不需要保存指针),访问任何一个节点的速度更快,直接下标访问。

子节点编号证明:

  1. 首先证明:完全二叉树中任何一层的最左节点的编号为n,则其左子节点编号为2n+1,其右子节点编号为2n+2(编号从0开始)。

完全二叉树每一层的节点数为2^{n-1}。因为任意第k层的最左节点的编号等于前面的k-1层节点总数,编号从0开始。因此第k层最左节点的编号也就等于2^{k-2}-1。第k层左子节点的编号等于2^{k-1}-12×(2^{k-2}-1)+1=2^{k-1}-1。得证!

  1. 再证明:完全二叉树任意节点编号n,则其左子节点为2n+1,其右子节点编号为2n+2(编号从0开始)

任取一个节点N,编号为n。设N所在层L的最左节点为M,编号为m。 显然,L层中位于N左边的节点为n-m个。N的左子节点NL位于L+1层,第L+1层中在NL前面的节点数为2(n-m)。由证明1得,L+1层的最左节点为2m+1。那么NL的编号为(2m+1)+2(n-m)=2n+1。得证!


2. 链式存储

对于一棵树不是完全二叉树时,使用数组存储可能浪费空间多,并且数组分配大小空间是固定的,不利于动态扩展,因此我们一般采用链式存储。每个节点不仅存储数据,还要存储左右子节点的指针,这种结构称为二叉链表结构,如果为了便于访问父节点,也可以将父节点指针保存在节点中,这时为三叉链表结构。

BST

两种结构的优劣比较

  • 数组存储方式空间需要事先确定,当超出空间需要重新分配,链式存储不需要。
  • 对于非完全二叉树,可能浪费空间比较多;对于完全二叉树,数组效率更高。
  • ......等。