1. 首页
  2. java数据结构

11-数据结构+算法(第11篇) 无死角“盘”它!二分查找树

引言

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

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

1-数据结构+算法(第11篇)

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

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

  1. 非叶子节点的分岔数:分岔数越多,表示大类包含的小类数目也就越多,那么为了定位到底属于哪个小类,比较次数也就越多,从而时间开销也就越大。

  2. 树的高度(或称为深度):树越深(高),从根节点(最大类)到叶子节点(目标物)的路径也就越长,也就意味着时间开销越大。

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

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

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

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

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

二分查找树的数学思想

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

1-数据结构+算法(第11篇)

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

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

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

1-数据结构+算法(第11篇)

牛顿

1-数据结构+算法(第11篇)

《自然哲学的数学原理》

二分查找法

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

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

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

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

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

1-数据结构+算法(第11篇)

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

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

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

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

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

1-数据结构+算法(第11篇)

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

1-数据结构+算法(第11篇)
可以看出,整个算法结构与二分查找树的搜索算法类似,时间复杂度也是O(logN)。

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

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

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

  1. 直接计算出到底哪个节点最终应该到这个位置

  2. 先用一个节点顶上,然后再进行下推调整

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

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

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

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

1-数据结构+算法(第11篇)
1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

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

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

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

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

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

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

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

1-数据结构+算法(第11篇)

1-数据结构+算法(第11篇)

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

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

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

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

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

希望读者能够给小编留言,也可以点击[此处扫下面二维码关注微信公众号](https://www.ycbbs.vip/?p=28 "此处扫下面二维码关注微信公众号")

JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:11-数据结构+算法(第11篇) 无死角“盘”它!二分查找树

链接:https://www.javajike.com/article/2435.html

« 12-数据结构+算法(第12篇)玩平衡二叉树就像跷跷板一样简单!
10-数据结构+算法(第10篇)叉堆“功夫熊猫”的速成之路»

相关推荐

QR code