查找类算法之二分搜索树 | 算法必看系列十-阿里云开发者社区

开发者社区> 被纵养的懒猫> 正文

查找类算法之二分搜索树 | 算法必看系列十

简介: 二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
+关注继续查看

动画 | 什么是二分搜索树(二叉查找树)?

二分搜索树属性
640 (1).png
二分搜索树的又名比较多,有的叫二叉排序树,也有的叫二叉查找树,或者有序二叉查找树。是指一棵空树或者具有下列性质的二叉树:

1.若任意节点的左子树不空,则左子树所有节点的值均小于它根节点的值;

2.若任意节点的右子树不空,则右子树所有节点的值均大于它根节点的值;

3.任意节点的左、右子树也分别为二叉查找树;

4.没有键值相等的节点。

它的查找、插入和删除的时间复杂度都等于树高,期望值是O(logn),最坏时间复杂度是O(n),比如树退化成线性表。
640.gif
查找元素
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
递归查找
递归查找的方式有很多,有层序遍历、前序遍历、中序遍历和后序遍历。我这里就举后面三个遍历方式。
Code
如果代码是下面这样写的,那它遍历过程是怎么样的?看下面动画。
640.png
动画:前序遍历
(响应读者的建议,动画不放BGM了二分搜索树(二叉查找树)?
二分搜索树属性
640 (1).png
二分搜索树的又名比较多,有的叫二叉排序树,也有的叫二叉查找树,或者有序二叉查找树。是指一棵空树或者具有下列性质的二叉树:

1.若任意节点的左子树不空,则左子树所有节点的值均小于它根节点的值;

2.若任意节点的右子树不空,则右子树所有节点的值均大于它根节点的值;

3.任意节点的左、右子树也分别为二叉查找树;

4.没有键值相等的节点。

它的查找、插入和删除的时间复杂度都等于树高,期望值是O(logn),最坏时间复杂度是O(n),比如树退化成线性表。
640.gif
查找元素
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
递归查找
递归查找的方式有很多,有层序遍历、前序遍历、中序遍历和后序遍历。我这里就举后面三个遍历方式。
Code
如果代码是下面这样写的,那它遍历过程是怎么样的?看下面动画。
640.png
动画:前序遍历
(响应读者的建议,动画不放BGM了)

动画:前中后遍历

从上面动画就发现,通过中序遍历得到的正好是一个升序序列。如果不考虑升序,后序遍历也能够为二分搜索树早点释放内存,早点减少栈的使用空间。
Code
image.png
添加元素
对于二叉树的添加和删除元素,使用链表存储形式比较好操作的,如果使用数组形式存储,删除某一个有子树的元素会引发一系列的位置改变,涉及到交换元素的位置,性能也比链表的小。所以待会后面出现的伪代码都以链表存储形式去操作。
Code
image.png
删除元素:删除最小和最大的元素
删除最小和最大的元素很简单,如果是删除最小的元素,从二叉树的顶点出发,一直递归它的左孩子,直到某节点的左孩子为空,这时候这个节点就是最小的元素。删除最大的元素也是一样的,一直递归它的右孩子,直到某节点的右孩子为空。
删除任意元素
如果删除任意元素,而这元素正好有左右子树的,那该是怎么办呢?

1962年,Hibbard提出了HibbardDeletion的解决方法。

看到Hibbard名字就想起来,我在希尔排序介绍过Hibbard增量序列,也把它相应的公式通过代码体现出来,代替希尔增量序列去进行希尔排序,最坏时间复杂度也比希尔增量序列的要小。

回到删除有左右子树的元素,想想它的左右子树也属于二叉排序树(也是二分搜索树),它左子树的最大值比它小,它右子树的最小值比它大。所以不管选择左子树的最大值还是选择右子树的最小值,替换掉要删除的元素,整个二叉树都是符合二分搜索树的规则。
动画:删除元素

Code:删除任意元素
image.png
支持重复元素的二分搜索树
二分搜索树有一个规则是:没有键值相等的节点。那么就不建议把待添加的元素跳过值相等的节点,到下一步继续比较直到插入新的节点。比如我想插入23,插完之后上有23,下有23,那查找就没有意义了,也破坏了时间复杂度上的O(logn)。

建议就是在节点上加一个属性:count。当插入23的时候,count就可以自算++。这不仅满足了没有键值相等的规则,也满足时间复杂度的期望值。
image.png
Code
image.png

--END--

来源 | 算法无遗测
作者 | 我脱下短袖

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【双11背后的技术】基于深度强化学习与自适应在线学习的搜索和推荐算法研究
作者:灵培、霹雳、哲予 1. 搜索算法研究与实践 1.1 背景 淘宝的搜索引擎涉及对上亿商品的毫秒级处理响应,而淘宝的用户不仅数量巨大,其行为特点以及对商品的偏好也具有丰富性和多样性。因此,要让搜索引擎对不同特点的用户作出针对性的排序,并以此带动搜索引导的成交提升,是一个极具挑战性的问题。传统
10205 0
神经架构优化(NAO):新的神经架构搜索(NAS)算法
如果你是一名深度学习实践者,你可能发现自己经常会遇到同一个关键问题:我应该为现在的任务选择哪种神经网络架构?
521 0
怎么设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程
6907 0
谷歌百度以图搜图 "感知哈希算法" C#简单实现
/// /// 感知哈希算法 /// public class ImageComparer { /// /// 获取图片的Hashcode /// /// /// public static string GetImageHashCode(string imageName) { int width = 8; int height = 8; // 第一步 // 将图片缩小到8x8的尺寸,总共64个像素。
1535 0
人工智能: 自动寻路算法实现(一、广度优先搜索)
前言 随着人工智能技术的日益发达,我们的生活中也出现了越来越多的智能产品。我们今天要关注的是智能家居中的一员:扫地机器人。
1672 0
字符串查找KMP算法(转)
如果你用过ctrl+F这个快捷键,那么你有很大的概率使用过这个算法,这就是在待查找字符串(可能有成千上万个字符)中找出模式串(比较小,可能有几个字符),可能找到大于或者等于1次的位置。例如,在ababcd中找出abc。
789 0
查找类算法之二分搜索树 | 算法必看系列十
二分搜索树是为了实现快速查找而生的,也支持快速添加和删除一个数据。如何查找某个元素首先跟根节点去做比较,如果相等的话就返回;如果待查元素要比根节点小,就进行左子树递归查找;如果待查元素要比根节点大,就进行右子树的递归查找;如果查找到最后还没有一个符合的元素,就返回null。
493 0
560
文章
1795
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载