树结构

简介: 树结构通过二叉搜索树(BST)实现二分查找:每个节点左子树值小于根,右子树值大于等于根。查找时从根节点出发,比较目标值与当前节点值,决定向左或右子树递归,每次排除一半数据,时间复杂度为O(log n),实现高效检索。

树结构是如何进行二分查找的?

上一讲我们讲了,因为链表并不具备 随机访问 的特点,所以二分查找无法生效。当链表想要访问中间的元素时,我们必须从链表头开始,沿着指针一步一步遍历,需要遍历一半的节点才能到达中间节点,时间代价是 O(n/2)。而有序数组由于可以 「随机访问」,因此只需要 O(1) 的时间代价就可以访问到中间节点了。

那如果我们能在链表中以 O(1) 的时间代价快速访问到中间节点,是不是就可以和有序数组一样使用二分查找了?你先想想看该怎么做,然后我们一起来试着改造一下。

直接记录和访问中间节点

既然我们希望能以 O(1) 的时间代价访问中间节点,那将这个节点直接记录下来是不是就可以了?因此,如果我们把中间节点 M 拎出来单独记录,那我们的第一步操作就是直接访问这个中间节点,然后判断这个节点和要查找的元素是否相等。如果相等,则返回查询结果。如果节点元素大于要查找的元素,那我们就到左边的部分继续查找;反之,则在右边部分继续查找。

对于左边或者右边的部分,我们可以将它们视为两个独立的子链表,依然沿用这个逻辑。如果想用 O(1) 的时间代价就能访问这两个子链表的中间节点,我们就应该把左边的中间节点 L 和右边的中间节点 R,单独拎出来记录。

并且,由于我们是在访问完了 M 节点以后,才决定接下来该去访问左边的 L 还是右边的 R。因此,我们需要将 L 和 M,R 和 M 连接起来。我们可以让 M 带有两个指针,一个左指针指向 L,一个右指针指向 R。这样,在访问 M 以后,一旦发现 M 不是我们要查找的节点,那么,我们接下来就可以通过指针快速访问到 L 或者 R 了。

将 M 节点改为带两个指针,指向 L 节点和 R 节点

对于其余的节点,我们也可以进行同样的处理。下面这个结构,你是不是很熟悉?没错,这就是我们常见的二叉树。你可以再观察一下,这个二叉树和普通的二叉树有什么不一样?

没错,这个二叉树是 有序 的。它的左子树的所有节点的值都小于根节点,同时右子树所有节点的值都大于等于根节点。这样的有序结构,使得它能使用二分查找算法,快速地过滤掉一半的数据。具备了这样特点的二叉树,就是 二叉检索树(Binary Search Tree),或者叫 二叉排序树(Binary Sorted Tree)。

讲到这里,不知道你有没有发现,尽管有序数组和二叉检索树,在数据结构形态上看起来差异很大,但是在提高检索效率上,它们的核心原理都是一致的。那么,它们是如何提高检索效率的呢?核心原理又一致在哪里呢?接下来,我们就从两个主要方面来看。

● 将数据有序化,并且根据数据存储的特点进行不同的组织。对于连续存储空间的数组而言,由于它具有「随机访问」的特性,因此直接存储即可;对于非连续存储空间的有序链表而言,由于它不具备「随机访问」的特性,因此,需要将它改造为可以快速访问到中间节点的树状结构。
● 在进行检索的时候,它们都是通过二分查找的思想从中间节点开始查起。如果不命中,会快速缩小一半的查询空间。这样不停迭代的查询方式,让检索的时间代价能达到 O(log n) 这个级别。

相关文章
|
11月前
|
存储 API 索引
数据结构的存储方式
数据结构底层存储只有数组和链表两种,其他如栈、队列、树、图等均为其衍生。数组支持随机访问但扩容困难,链表灵活增删但无法随机访问。所有数据结构的操作本质为“增删查改”,遍历方式分为线性迭代与非线性递归。理解二者差异,是掌握各类高级数据结构的基础。(238字)
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
11月前
|
算法 数据可视化
二叉树的递归/层序遍历 递归遍历(DFS)
本文详解二叉树的遍历框架,涵盖递归遍历的固定访问顺序及前、中、后序的本质区别——即代码在递归函数中的位置不同所致。同时深入讲解层序遍历(BFS)的三种实现方式,适用于不同场景,尤其适合求最短路径问题;而DFS则因结构天然适合搜索所有路径。通过实例对比,阐明BFS与DFS的应用偏好及原理依据。
二叉树的递归/层序遍历 递归遍历(DFS)
|
11月前
|
SQL 自然语言处理 数据可视化
大火的 ChatBI,是如何实现灵活的自然语言数据分析?
这对业务人员而言,不仅简化了数据分析流程,更无需依赖 IT 代码开发,实现了自主灵活的智能问数,高效敏捷展开分析。
|
11月前
|
存储 NoSQL 关系型数据库
Geohash 编码
Geohash编码将经纬度转换为字符串,通过不断二分地球经纬度区间,交叉组合生成区域编码,再转为Base32简化表示。它用于高效存储和查询地理位置,广泛应用于Redis、MySQL等系统,具有相同前缀的编码代表相近区域,便于空间索引与检索。
|
11月前
|
存储 算法 安全
加密算法
加密算法主要分为对称加密(如AES、SM4)、非对称加密(如RSA、SM2)、哈希摘要(如SHA-2、SM3)、电子签名及密码存储技术。对称加密加解密快但需保密密钥;非对称加密使用公私钥,安全性高但速度慢;哈希摘要用于验证数据完整性,不可逆。各类算法在信息安全中各有应用场景。
excel 百分位函数 学习
excel 百分位函数 学习
1356 1
|
调度 项目管理 计算机视觉
『软件工程8』软件项目进度安排与跟踪,一招学会计算关键路径
该文章详细解释了如何在软件项目管理中安排进度与跟踪,特别是如何计算和利用关键路径方法(CPM)来优化项目时间管理。
|
开发框架 安全 .NET
程序技术好文:进程和线程的区别
程序技术好文:进程和线程的区别
481 0
|
SQL 安全 网络协议