2023-06-13  阅读(287)
原文作者:Java 极客 原文地址:https://www.javajike.com/article/2425.html

引言

《菜鸟也能“种”好二叉树!》一文中提到了:为了方便查找,需要进行分层分类整理。而满足这种目标的数据结构之一就是树。

树的叶子节点可以看作是最终要搜寻的目标物;叶子节点以上的每一层,都可以看作是一个大类别、层中的每个节点都可以看作是一个小类别。

202306132118216601.png

202306132118222292.png

从上图可以看出,要定位目标物,就需要从最上面的大类依次向下定位目标物所属的小类。

定位的效率(时间复杂度)取决于两个因素:

  1. 非叶子节点的分岔数:分岔数越多,表示大类包含的小类数目也就越多,那么为了定位到底属于哪个小类,比较次数也就越多,从而时间开销也就越大。
  2. 树的高度(或称为深度):树越深(高),从根节点(最大类)到叶子节点(目标物)的路径也就越长,也就意味着时间开销越大。

研究问题都讲究由简到繁,那就让我们先来看看最简单的情形——分岔数最小的情形——二叉树。

二叉树的每层节点只有两个节点,这表示只有两个小类。定位属于哪个小类时,需要做比较。比较的次数越少、比较的方法越简单,效率也就越高。

比较次数再怎么少也得1次、最简单的比较方法就是比大小。为了满足这个目标,前辈们就对一般二叉树加了如下规则:

每个非叶子节点的左孩子的值不大于该节点本身的值;右孩子的值不小于该节点本身的值。

这样的二叉树就称为“二分查找树”。

二分查找树的数学思想

将二分查找树从根节点(最大类)到叶子节点(目标物)的路径扒出来,垂直放置之后就如下图左部所示。再倒”下来水平放置之后,就如下图右部所示。

202306132118227283.png

202306132118232004.png

由此可以看出,从最大类到目标物的查找过程,其实就是从大类不断逼近目标物的过程。

这个思想的本质其实就是数学的“逼近法”——不断缩小范围、直至不可再小,最终剩下的即为所求。

“逼近法”思想大量在数学中应用。牛顿当年发明微积分,其证明过程其实采用的也是“逼近法”。具体可以参见牛顿的旷世巨著《自然哲学的数学原理》第一编《物体的运动》的第1章《初量与终量的比值方法》的引理2。

202306132118237555.png

202306132118242476.png

牛顿

202306132118248017.png

202306132118256138.png

《自然哲学的数学原理》

二分查找法

基于二分查找树数据结构的搜索算法称为“二分查找法”。

二分查找树是一个递归定义,所以很容易得出递归版的二分查找法。

下面以链表形式存储的二分查找树为例,数组形式存储的,可以根据父子节点下标的线性关系(《菜鸟也能“种”好二叉树!》一文中的推论5.2.1),类似推导,在此就不赘述了。

202306132118261269.png

2023061321182680610.png

2023061321182729211.png

2023061321182798412.png

还是根据《史上最猛之递归屠龙奥义》一文中的老套路,转换成非递归版本:

2023061321182853513.png

2023061321182920914.png

整个算法的时间开销主要由do-while循环体的循环次数决定。很显然,在最坏情况下,循环次数等于二叉查找树的高度。假设树的节点总数为N,则根据《菜鸟也能“种”好二叉树!》一文中的结论,高度等于logN,从而时间复杂度等于O(logN)。

二分查找树的节点插入算法

向二分查找树插入新节点很简单,从根节点开始,根据定义逐层比较、进入对应子树下沉、直至叶子节点:

2023061321182973815.png

2023061321183036916.png

2023061321183090117.png

2023061321183161618.png

2023061321183205619.png

2023061321183266720.png

对应的递归版算法代码如下:

2023061321183318621.png

2023061321183388122.png

还是根据《史上最猛之递归屠龙奥义》一文中的老套路,转换成非递归版本:

2023061321183424423.png

2023061321183480824.png
可以看出,整个算法结构与二分查找树的搜索算法类似,时间复杂度也是O(logN)。

二分查找树的节点删除算法

直接删除节点,会破坏二叉树的结构,需要进行调整。

首先需要有节点补上被删节点的空缺。这个“补漏”有两个策略:

  1. 直接计算出到底哪个节点最终应该到这个位置
  2. 先用一个节点顶上,然后再进行下推调整

稍微想一想,就会知道第一种策略比较复杂,因为你需要在一开始就通盘考虑,复杂度很高;

第二种策略其实是一种局部性原理思想——先局部求解、再逐步递进到全局解。这种局部性原理思想在整个计算机科学中大量使用:比如虚拟内存管理、人工智能的爬山算法等等。

第二种策略其实我们在上一篇《二叉堆“功夫熊猫”的速成之路》中的“Top N”章节中也提到了。有兴趣的朋友也可以翻回去看看。

具体实操上,和“Top N”的方法一样,我们用尾节点“补漏”被删节点。

2023061321183522425.png

2023061321183602126.png

2023061321183658927.png

2023061321183720228.png

2023061321183788029.png

2023061321183851130.png

上面三张图形象描绘了整个替换、下推调整的过程。

这里啰嗦一句:因为要先得到尾节点的位置,然后再回到待删节点位置——这涉及到遍历和回溯,若采用链表存储整个二叉查找树的话,就不是很方便。所以针对节点删除场景,用数组更简单。

但为了“炫技”,笔者在这里就挑最复杂的单向链表式、非递归版算法来实现一下:)

2023061321183891031.png

2023061321183956532.png

2023061321184040033.png

2023061321184120934.png

2023061321184170735.png

2023061321184248636.png

2023061321184296037.png

2023061321184355638.png

最坏情况无外乎删除根节点——这种情况下下推的距离最长——极限情况下,要下推整个二分查找树的高度。所以这个算法的时间复杂度不超过O(logN)。

至于数组式、递归版算法,读者可以根据《史上最猛之递归屠龙奥义》《二叉堆“功夫熊猫”的速成之路》中讲到的套路,自行推导。

做一棵“稳重的”二分查找树

2023061321184407739.png

2023061321184469340.png

2023061321184525441.png

2023061321184575742.png

上面两棵二分查找树是等价的,但是可以很明显看出:第一棵一些分支会向一边倾斜,而第二棵就显得“稳重”多了。

试想,你要搜索值为17的节点。按照前面二分查找树的搜索算法,对于第一棵树,从根节点开始,一共需要进行4次比较才能找到;而对于第二棵树,只需要进行1次比较就能找到!

为什么会有这么大的差别呢?

答案在于:第二棵树是一棵“平衡二叉树”,它的“稳重”特点实现了一个目标——平均查找长度最短。

下一篇文章我们就来“盘盘”平衡二叉树。

阅读全文
  • 点赞