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

阅读本文需要5分钟

引言

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

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

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

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

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

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

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

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

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

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

二分查找树的数学思想

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

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

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

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

牛顿

《自然哲学的数学原理》

二分查找法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

结束

本文分享自微信公众号 - Java研发军团(ityuancheng)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-05-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏窗户

一个图像项目的可能性处理方式

  随着深度学习的发展,图像、声音的识别几乎都是它的天下。但深度学习需要很大的空间来存储参数,而且推理的时间与所使用的硬件关系很大,于是对于成本是有很大的要求的...

7620
来自专栏窗户

不要为了虚荣心而让孩子过早的学习人工智能

  这个题目有点攻击性的意思,看的人不大舒服。最开始的时候,我题目在《反对孩子学人工智能》、《坚决反对孩子学人工智能》之间犹豫。后来一想,是否攻击性过强,于是妥...

13730
来自专栏科技分享

Libevent源码分析系列【转】

转自:https://www.cnblogs.com/zxiner/p/6919021.html

8410
来自专栏科技分享

Libevent源码分析系列

源码那么多,该怎么分析从哪分析呢?一个好的方法就是先用起来,会用了,然后去看底层相应的源码,这样比较有条理,自上向下掌握。下面用libevent库写个程...

37040
来自专栏GreenLeaves

.Net 并发写入文件的多种方式

本文主要演示日常开发中利用多线程写入文件存在的问题,以及解决方案,本文使用最常用的日志案例!

13360
来自专栏软件开发 -- 分享 互助 成长

目录1.智能指针的作用2.智能指针的使用3.智能指针的设计和实现

C++程序设计中使用堆内存是非常频繁的操作,堆内存的申请和释放都由程序员自己管理。程序员自己管理堆内存可以提高了程序的效率,但是整体来说堆内存的管理是麻烦的,...

13830
来自专栏linux驱动个人学习

ioremap_nocache() 函数的使用

调用ioremap_nocache()函数之后,返回一个线性地址,此时CPU 可以访问设备的内存(已经将其映射到了线性地址空间中了),此时CPU可以使用访问内存...

18120
来自专栏GreenLeaves

C# 算法之选择排序

选择排序是排序中比较简单的一种,实现的大致思路如下:首先我们拿到一个需要排序的数组,假设该数组的第一个元素是最小的,然后将数组中剩下的元素,于最小的元素进行比较...

10830
来自专栏窗户

相互递归(1)

  相互递归就是多个函数互相定义,最常见的就是两个函数,比如f和g,f的定义中用到g,而g的定义中用到f。

11320
来自专栏GreenLeaves

.Net 环境下比较各种数据库插入操作的性能

再说Windows的异步I/O操作前,先聊聊一些题外话,能帮助我们更好的理解异步I/O操作,常规的Web程序,当用户发起一次请求,当请求通过管道到达客户端的这个...

11710

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励