预计阅读时间:10分钟
二叉搜索树(BST)是一种特殊的二叉树,它满足以下两个特性:
- 每个节点的值必须大于(或等于) 其左子树的所有节点的值。
- 每个节点的值必须小于(或等于) 其右子树的所有节点的值。
一、二叉搜索树优点
二叉搜索树,支持快速查找、插入、删除操作和其他操作。
1. 查找操作
查找过程如下:取根节点,如果根节点等于我们要查找的数据,直接返回。如果大于根节点的值,那就往左子树递归查找。如果小于根节点的值,那就往右子树递归查找。
2. 插入操作
插入过程类似于查找:首先,取根节点,比较待插入节点和根节点的值,如果大于根节点则往右子树递归查找插入位置,如果是空位置则直接插入。如果小于根节点的值则往左子树递归查找插入位置,如果是空位置则直接插入。
3. 删除操作
删除过程比较复杂(为了维持二叉搜索树的特性):首先当然得查找到该待删除的节点。然后删除该节点,此时有三种情况:
(1) 该节点是叶子节点。可以直接删除该节点,即将该节点置为NULL!
(2) 该节点有一个节点(左子节点或右子节点)。为了维持二叉搜索树的特性,我们可以将待删除节点父节点直接指向待删除节点的子节点。因为对于一棵树的根节点,该根节点的左子树中的所有节点都小于该根节点的值,该根节点的右子树中的所有节点都大于该根节点(二叉搜索树定义 )。 因此我们可以删除某个拥有一个子节点的节点,可以直接让该子节点代替待删除的节点的位置,仍然满足二叉搜索树特性。
(3) 该节点有两个子节点。因为有两个子节点,无法像情况2一样。我们需要找该节点右子树中的最小节点,代替待删除节点的位置,然后再删除这个最小节点。最小节点一定没有左子节点,因此我们可以用情况1或2来删除该最小节点。这样我们的二叉搜索树就成功删除了节点,并且保持了自身的特性。
4. 其他操作
二叉搜索树还支持快速获得最大节点和最小节点、输出有序的数据序列(通过中序遍历)。
二、二叉搜索树的效率
前面说二叉搜索树支持快速查找、插入、删除和其他操作。快速具体有多快?
例如上面图,我们要查找任何一个节点,需要的步骤总数都小于等于树的深度(该树深度为4)。对于一颗有n个节点的二叉树,如果是一颗完全二叉树,则此时树的深度是最小的,深度为 。如果是一颗链树(树退化成了链表,如下图),则此时树的深度是最大的,就等于节点的个数n。其他任意的二叉树的深度都介于这两种树的深度之间。因此,我们在二叉搜索树中,查找一个节点的步骤数是随二叉搜索树节点对数增长的。对数增长是很慢的,比线性增长慢很多。
二叉搜索树的插入、搜索就是在查找的基础上,多了几个附加操作,步骤数整体还是对数增长。
即,二叉树的查找、插入、删除操作的时间复杂度都是级别的。输出有序序列需要遍历整个二叉搜索树,时间复杂度是级别。
三、二叉搜索树的存储结构
二叉搜索树属于二叉树,因此存储结构与二叉树是一样的。有两种存储方式:
1. 数组存储
数组存储适用于完全二叉树,否则将浪费大量空间。如下图:
图中空表示没有节点,可以看出对于非完全二叉树来说,用数组存储需要更多空间,并且许多空间白白浪费掉了(这些空间用来填充成完全二叉树,以便编号公式有效)。对于n个节点的二叉树,需要个存储单元。因此一般完全二叉树都用数组存储,既节约空间(不需要保存指针),访问任何一个节点的速度更快,直接下标访问。子节点编号证明:
- 首先证明:完全二叉树中任何一层的最左节点的编号为n,则其左子节点编号为2n+1,其右子节点编号为2n+2(编号从0开始)。
完全二叉树每一层的节点数为。因为任意第层的最左节点的编号等于前面的层节点总数,编号从0开始。因此第层最左节点的编号也就等于。第层左子节点的编号等于。。得证!
- 再证明:完全二叉树任意节点编号n,则其左子节点为2n+1,其右子节点编号为2n+2(编号从0开始)。
任取一个节点N,编号为n。设N所在层L的最左节点为M,编号为m。 显然,L层中位于N左边的节点为个。N的左子节点NL位于L+1层,第L+1层中在NL前面的节点数为。由证明1得,L+1层的最左节点为。那么NL的编号为。得证!
2. 链式存储
对于一棵树不是完全二叉树时,使用数组存储可能浪费空间多,并且数组分配大小空间是固定的,不利于动态扩展,因此我们一般采用链式存储。每个节点不仅存储数据,还要存储左右子节点的指针,这种结构称为二叉链表结构,如果为了便于访问父节点,也可以将父节点指针保存在节点中,这时为三叉链表结构。
两种结构的优劣比较
- 数组存储方式空间需要事先确定,当超出空间需要重新分配,链式存储不需要。
- 对于非完全二叉树,可能浪费空间比较多;对于完全二叉树,数组效率更高。
- ......等。