二叉排序树

news/2024/10/30 9:27:29/

二叉排序树

一、二叉排序树的定义(二叉排序树可用于元素的有序组织、搜索)

二叉排序树,又称二叉查找树BST,Binary Search Tree)
性质:左子树结点值 < 根结点值 < 右子树结点值左子树和右子树又各是一颗二叉排序树
进行中序遍历(左根右),可以得到一个递增的有序序列

二、查找操作

1.定义

//二叉排序树结点
typedef struct BSTNode{int key;struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

2.算法思想
若树非空,目标值与根结点的值比较:
若相等,则查找成功;
若小于根结点,则在左子树查找,否则在右子树查找。
查找成功,返回结点指针;查找失败返回NULL

3.代码实现(非递归实现)
最坏空间复杂度O(1)

//在二叉排序树种查找值为key的结点
BSTSearch1

4.代码实现(递归实现)
最坏时间复杂度O(h)

//在二叉排序树种查找值为key的结点
BSTSearch2

三、插入操作

1.算法思想
若原二叉排序树为空,则直接插入结点;否则,若关键字k小于根结点值,则插入到左子树,若关键字k大于根结点值,则插入到右子树

2.代码实现(递归实现)
最坏空间复杂度O(h)
//树中存在相同关键字的结点,插入失败
//新插入的结点一定是叶子

//在二叉排序树插入关键字为k的新结点(递归实现)
BSTInsert

3.代码实现(非递归实现)

//在二叉排序树插入关键字为k的新结点(递归实现)
BSTInsert

四、二叉排序树的构造

例1:按照序列str={50,66,60,26,21,30,70,68}建立BST
例2:按照序列str={50,26,21,30,66,60,70,68}建立BST(不同的关键字序列可能得到同款二叉排序树)
例3:按照序列str={26,21,30,50,60,66,68,70}建立BST(也可能得到不同款二叉排序树)

//按照str[]中的关键字序列建立二叉排序树
CreatBST

五、删除操作(重点)

1.算法思想
先搜索找到目标结点:

  • 若被删除结点z是叶结点,则直接删除,不会破坏二叉排序树的性质。
  • 若结点z只有一棵左子树或右子树,则让z的子树成为z父节点的子树,代替z的位置。
  • 若结点z有左、右两棵子树,则令z的直接后继(或直接前驱)代替z,然后从二叉排序树种删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况。

左子树结点值 < 根结点值 < 右子树结点值
进行中序遍历,可以得到一个递增的有序序列
中序遍历


( 根 右)
(( 根 右) 左 根 右)
z的后继:z的右子树中最左下结点(该结点一定没有左子树)


(左 根 )
(左 根 (左 根 ))
z的前驱:z的左子树中最右下结点(该结点一定没有右子树)

六、查找效率分析(重点)

查找长度 – 在查找运算中,需要对比关键字的次数称为查找长度,反映了查找操作时间复杂度
若树高h,找到最下层的一个结点需要对比h次
最好情况:n个结点的二叉树最小高度为[log2n]向下取整+1。平均查找长度=O(log2n)
最坏情况:每个结点只有一个分支,树高h=结点数n,平均查找长度=O(n)
查找成功平均查找长度ASL(Average Search Length)
在这里插入图片描述
ASL 成功= (1 * 1 +2 * 2 +3 * 4 + 4 * 1) / 8 = 2.625

查找失败平均查找长度ASL(Average Search Length)
在这里插入图片描述
ASL失败=(3 * 7 + 4 * 2) / 9 = 3.22

在这里插入图片描述
ASL成功 = (1 *1 + 2 * 2 + 3 * 1 +4 * 1 + 5 * 1 + 6 * 1 + 7 * 1) / 8 = 3.75
在这里插入图片描述
ASL失败 = (2 * 3 + 3+ 4 + 5+ 6 +7 * 2) / 9 = 4.22


http://www.ppmy.cn/news/460734.html

相关文章

推荐一款适合苹果电脑小白使用的BT下载器

BT是一种互联网的P2P传输协议&#xff0c;全名"BitTorrent"&#xff0c;目前是基于广大开发者群体的开放式传输协议&#xff0c;可用于文件的远程传输。BT下载是通过一个P2P下载软件来实现的&#xff0c;具有下载的人越多下载速度越快的特点。 下面我推荐一款适合苹…

BT.601与BT.656

ITU-R Recommendation BT.601&#xff0c;简称Rec.601或者BT.601&#xff08;或者它的前身&#xff0c;CCIR601&#xff09;&#xff0c;是1982年由ITU-R发布的一个标准&#xff0c;用于将各行数位视讯讯号进行数位化。旧名称为CCIR 601&#xff0c;国际电信联盟&#xff08;IT…

BT.601和BT.656

BT601和BT656 在日常的工作中我们常听到BT601&#xff08;CCIR601&#xff09;和BT656的说法&#xff0c;另外老一点的文档可能还会提到CCIR601&#xff0c;CCIR656的说法&#xff0c;今天就对这两个概念做简单说明。 首先说明一下ITU-R BT601/656和CCIR601/656的前世今生&…

BT.709 vs BT.2020

BT.709和BT.2020都是ITU-R发布的电视参数标准。 BT.709是《节目制作和国际节目交换中使用高清晰度电视标准的参数值》&#xff0c;指定了高清电视也就是常说的1080p电视的参数标准。 BT.2020是《超高清电视系统节目制作和国际交换的参数数值》&#xff0c;指定了超高清电视&a…

BT没死!305个国外BT资源聚合站点大全

最近各个BT站的日子很不好过&#xff0c;很多都关门停业&#xff0c;不仅仅是国外的海盗湾&#xff0c;连国内比较知名的BTChina也没了。但是作为一种资源共享的方式&#xff0c;BT下载并没有死&#xff0c;还有很多类似海盗湾和BTChina这样的聚合型站点&#xff0c;为大家提供…

最全BT介绍

BitTorrent 简介 riba2534 2021年04月11日 19:26 阅读 851 关注 BitTorrent 简介 从 P2P 说起 经常在网上飙车的老司机应该都知道 BT 下载&#xff0c;但是有时候拿到了种子却下载不动&#xff0c;会不会很抓狂&#xff0c;是不是还觉得是自己网不行&#xff0c;那作为一…

国内国外最好的BT站点

2008年十个国内国外最好的BT站点 互联网的BT站点。 国外的十个站点 1.Mininova 网址 http://www.mininova.org/ 特点&#xff1a;东西比较多资格比较老&#xff0c;地球人都知道资格老的总能排第一位。 2.The Pirate Bay 网址 http://thepiratebay.org/ 特点&#xff1a…

国外最好的BT站点

1.http://www.mininova.org Mininova 特点:东西比较多资格比较老,地球人都知道资格老的总能排第一位。 2.http://thepiratebay.org The Pirate Bay : 特点:东西比较多而且有中文,找东西方便,可惜速度有点慢。 3.http://isohunt.com IsoHunt: 特点:更新比较快,速度也不错…