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

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

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

相关文章
|
3月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
102 1
|
12天前
|
算法
树的遍历算法有哪些?
不同的遍历算法适用于不同的应用场景。深度优先搜索常用于搜索、路径查找等问题;广度优先搜索则在图的最短路径、层次相关的问题中较为常用;而二叉搜索树的遍历在数据排序、查找等方面有重要应用。
21 2
|
15天前
|
算法 搜索推荐 数据库
二分搜索:高效的查找算法
【10月更文挑战第29天】通过对二分搜索的深入研究和应用,我们可以不断挖掘其潜力,为各种复杂问题提供高效的解决方案。相信在未来的科技发展中,二分搜索将继续发挥着重要的作用,为我们的生活和工作带来更多的便利和创新。
23 1
|
1月前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
32 4
|
1月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
20 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
1月前
|
算法 决策智能
基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
该程序基于禁忌搜索算法求解车辆路径问题(VRP),使用MATLAB2022a版本实现,并带有GUI界面。用户可通过界面设置参数并查看结果。禁忌搜索算法通过迭代改进当前解,并利用记忆机制避免陷入局部最优。程序包含初始化、定义邻域结构、设置禁忌列表等步骤,最终输出最优路径和相关数据图表。
|
2月前
|
大数据 UED 开发者
实战演练:利用Python的Trie树优化搜索算法,性能飙升不是梦!
在数据密集型应用中,高效搜索算法至关重要。Trie树(前缀树/字典树)通过优化字符串处理和搜索效率成为理想选择。本文通过Python实战演示Trie树构建与应用,显著提升搜索性能。Trie树利用公共前缀减少查询时间,支持快速插入、删除和搜索。以下为简单示例代码,展示如何构建及使用Trie树进行搜索与前缀匹配,适用于自动补全、拼写检查等场景,助力提升应用性能与用户体验。
56 2
|
1月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
25 0
|
1月前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
16 0