首页 > 其他分享 >二叉查找树知识简记

二叉查找树知识简记

时间:2024-10-31 22:20:39浏览次数:6  
标签:结点 右子 二叉 简记 查找 树中 链接

二叉查找树( BST)

一、概念

1、简述

一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。

具体来说,就是使用每个结点含有两个链接(链表中每个结点只含有一个链接)的二叉查找树来高效地实现符号表

2、特点

(1)在二叉查找树中,每个结点还包含了一个键和一个值,键之间也有顺序之分以支持高效的查找。

(2)一棵二叉查找树本质是一棵二叉树,其中每个结点都含有一个 可比较的键(以及相关联的值)且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的键。

(3)使用二叉查找树的算法的运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。在最好的情况下,一棵含有 N 个结点的树是完全平衡的,每条空链接和根结点的距离都为~ lgN。在最坏的情况下,搜索路径上可能有 N个结点。

(4)一棵二叉查找树代表了一组键(及其相应的值)的集合,而同一个集合可以用多棵不同的二叉查找树表示

(5)在一棵二叉查找树中,所有操作在最坏情况下所需的时间都和树的高度成正比。

二、查找

1、算法

在二叉查找树中查找一个键的递归算法:

如果树是空的,则查找未命中;

如果被查找的键和根结点的键相等,查找命中,
否则我们就(递归地)在适当的子树中继续查找。

如果被查找的键较小就选择左子树,较大则选择右子树

2、特点

(1)只有该结点所表示的子树才会含有和被查找的键相等的结点。

(2)和二分查找中每次迭代之后查找的区间就会减半一样,在二叉查找树中,随着我们不断向下查找,当前结点所表示的子树的大小也在减小(理想情况下是减半,但至少会有一个结点)。

(3)当找到一个含有被查找的键的结点(命中)或者当前子树变为空(未命中)时这个过程才会结束。

(4)从根结点开始,在每个结点中查找的进程都会递归地在它的一个子结点上展开,因此一次查找也就定义了树的一条路径。

(5)对于命中的查找,路径在含有被查找的键的结点处结束。

(6)对于未命中的查找,路径的终点是一个空链接,

三、插入

二叉查找树的另一个更重要的特性就是插入的实现难度和查找差不多。

1、算法

插入之前先查找要插入的键,当查找一个不存在于树中的结点并结束于一条空链接时,将链接指向一个含有要插入的键的新结点

如果树是空的,就返回一个含有该键值对的新结点;

如果被查找的键小于根结点的键,我们会继续在左子树中插入该键,否则在右子树中插入该键。

2、特点

(1)使用二叉查找树的算法的运行时间取决于树的形状,而树的形状又取决于键被插入的先后顺序。

(2)在最好的情况下,一棵含有 N 个结点的树是完全平衡的,每条空链接和根结点的距离都为~ lgN。

(3)在最坏的情况下,搜索路径上可能有 N个结点。

(4)在由 N 个随机键构造的二叉查找树中,查找命中平均所需的比较次数为∼ 2lnN(约1.39lgN)

(5)在由 N 个随机键构造的二叉查找树中插入操作和查找未命中平均所需的比较次数为∼ 2lnN(约 1.39lgN)

(6)二叉查找树得以广泛应用的一个重要原因就是它能够保持键的有序性

四、最大键和最小键

1、最小键

如果根结点的左链接为空,那么一棵二叉查找树中最小的键就是根结点;

如果左链接非空,那么树中的最小键就是左子树中的最小键。

2、最大键

找出最大键的方 法也是类似的,只是变为查找右子树。

五、向上取整和向下取整

1、向下取整 floor

如果给定的键 key 小于二叉查找树的根结点的键,那么小于等于 key 的最大键 floor(key) 一定在根结点的左子树中;

如果给定的键 key 大于二叉查找树的根结点,那么只有当根结点右子树中存在小于等于 key 的结点时,小于等于 key 的最大键才会出现在右子树中,否则根结点就是小于等于 key的最大键。

2、向上取整 ceiling


将“左”变为“右”(同时将小于变为大于)就能够得到向上取整 ceiling() 的算法。

六、选择操作 select

假设我们想找到排名为k的键(即树中正好有k个小于它的键)。

如果左子树中的结点数t大于k,那么我们就继续(递归地)在左子树中查找排名为 k 的键;

如果 t 等于 k,我们就返回根结点中的键;
如果 t 小于 k,我们就(递归地)在右子树中查找排名为( k-t-1) 的键。

七、排名 rank

rank() 是 select() 的逆方法,它会返回给定键的排名。

它的实现和 select() 类似:

如果给定的键和根结点的键相等,我们返回左子树中的结点总数 t;

如果给定的键小于根结点,我们会返回该键在左子树中的排名(递归计算);

如果给定的键大于根结点,我们会返回 t+1(根结点)加上它在右子树中的排名(递归计算)

八、删除最大键和删除最小键

1、删除最小键deleteMin()

递归方法接受一个指向结点的链接,并返回一个指向结点的链接。这样我们就能够方便地改变树的结构,将返回的链接赋给作为参数的链接。
对于 deleteMin(),要不断深入根结点的左子树中直至遇见一个空链接,然后将指向该结点的链接指向该结点的右子树

此时已经没有任何链接指向要被删除的结点,因此它会被清理掉。

可以用类似的方式删除任意只有一个子结点(或者没有子结点)的结点

2、删除最大键deleteMax()

deleteMax()方法的实现和 deleteMin() 完全类似。

九、删除

若从二叉搜素树中删除节点x, 在删除结点 x 后需要用它的后继结点填补它的位置。

因为 x 有一个右子结点,因此它的后继结点就是其右子树中的最小结点。

因为 x.key 和它的后继结点的键之间不存在其他的键,所以替换后仍然能够保证树的有序性,

将 x 替换为它的后继结点的步骤:
(1) 将指向即将被删除的结点的链接保存为 t;
(2) 将 x 指向它的后继结点 min(t.right);
(3) 将 x 的右链接(原本指向一棵所有结点都大于 x.key 的二叉查找树)指向 deleteMin(t.right),也就是在删除后所有结点仍然都大于 x.key 的子二叉查找树;
(4) 将 x 的左链接(本为空)设为 t.left(其下所有的键都小于被删除的结点和它的后继结点)。


十、范围查找

1、中序遍历

遍历二叉查找树的基本方法,叫做中序遍历

首先要遍历的是根结点的左子树中的所有键(根据二叉查找树的定义它们应该都小于根结点的键),

然后是根结点的键,

最后遍历根结点的右子树中的所有键(根据二叉查找树的定义它们应该都大于根结点的键)

2、范围查找

给定两个参数,并将两参数确定范围内的键返回给用例的keys()方法

修改一下中序遍历逻辑,将所有落在给定范围以内的键加入一个队列 Queue 并跳过那些不可能含有所查找键的子树

标签:结点,右子,二叉,简记,查找,树中,链接
From: https://blog.csdn.net/well_fly/article/details/143418493

相关文章

  • 二叉树专题学习
    前言:由于二叉树这一章的题型比较多,涉及到的递归程序也较多,所以单开一个随笔来记录这个学习过程,希望对读者有帮助。理论知识基础在二叉树的选择题中,常常会涉及到对于最多或最少结点、最大或最小高度、求叶子结点个数这几类经典的问题。上机题1.二叉树的建立和遍历P1305新二......
  • 108-二叉树-将有序数组转换为二叉搜索树
    树|二叉搜索树|数组|分治|二叉树二叉搜索树(BinarySearchTree,简称BST)和平衡二叉搜索树(BalancedBinarySearchTree)是计算机科学中非常重要的数据结构,广泛应用于各种算法和系统中。理解它们的定义、特点和性质对于掌握数据结构和算法至关重要。下面,我们将详细......
  • 【优选算法】——二分查找!
    目录1、二分查找2、在排序数组中查找元素的第一个和最后一个位置3、搜索插入位置4、x的平方根5、山脉数组的封顶索引6、寻找峰值 7、寻找旋转排序数组中的最小值8、点名9、完结散花1、二分查找给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 targ......
  • 有序二叉树简介
    有序二叉树有序二叉树:左边的结点值小于当前结点,右边结点值大于当前结点。有序二叉树结点模型root表示指向根结点的指针。构建有序二叉树判断root是否为nullroot为空,root=node如果root不为空,定义index游标,初始值==root。判断index和node结点值的大小二叉树的......
  • C++:二叉搜索树进阶
    文章目录前言一、二叉搜索树的查找(递归版本)二、二叉树搜索树的插入(递归版本)三、二叉搜索树的删除(递归版本)四、析构函数五、拷贝构造六、赋值重载七、代码总结八、二叉搜索树性能对比九、key_value模型总结前言前面我们学习的二叉搜索树迭代的版本,今天我们来学习递归......
  • 【数据结构多彩画卷】不要只会普通的二叉树了 , 你听说过用二叉树来排序吗? 【二叉搜索
    本篇会加入个人的所谓鱼式疯言❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • C++:二叉搜索树(迭代)
    文章目录前言一、二叉搜索树1.二叉搜索树的概念2.二叉搜索树的操作1)遍历2)查找3)插入4)删除二、二叉搜索树的实现(迭代版本)1.二叉搜索树的结构定义2.二叉搜索树的插入3.二叉搜索树遍历4.二叉搜索树删除5.二叉搜索树查找6.二叉搜索树代码总结总结前言今天来学......
  • 代码随想录算法训练营第十二天| 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大
    226.翻转二叉树题目链接:.-力扣(LeetCode)文章讲解:代码随想录视频讲解:听说一位巨佬面Google被拒了,因为没写出翻转二叉树|LeetCode:226.翻转二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com......
  • 代码随想录算法训练营第十三天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    110.平衡二叉树题目链接:.-力扣(LeetCode)文章链接:代码随想录视频链接:后序遍历求高度,高度判断是否平衡|LeetCode:110.平衡二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦!快来打卡!本期视频的文字讲解版在「代码随想录」刷题网站:programmercarl.com,这里刷题顺序,详......
  • 给定一个二叉树,找出其最大深度
      文心快码(BaiduComate)是基于百度文心大模型,在研发全流程全场景下为开发者提供辅助建议的智能代码助手。结合百度积累多年的编程现场大数据、外部优秀开源数据,可为开发者生成更符合实际研发场景的优秀代码,提升编码效率,释放“十倍”软件生产力。......