数据结构-查找

一、基本术语

二、线性结构

ASL:平均查找长度  \sum_{i=1}^{n}PiCi

1、顺序查找

1.1、代码实现

typedef struct {int* elem;int TableLen;
}SSTable;int Search_Seq(SSTable ST, int key) {ST.elem[0] = key;   //哨兵,使得循环不用判断数组是否会越界int i;for (i = ST.TableLen; ST.elem[i] != key; i--);return i;
}

ALS_{yes}=(n+1)/2           ALS_{no}=n+1

1.2、优缺点

                缺:当n较大时,平均查找长度较大,效率低

                优:对数据元素的存储没有要求,顺序存储或链式存储都可以,对链表只能顺序查找

                对有序线性表的顺序查找,查找失败时不需要完整遍历整个线性表,从而降低查找失败的平均查找长度。

1.3、应用-有序顺序表上的顺序查找判定树

ALS_{no}=n/2+n/(n+1)

到达失败节点时所查找的长度等于它上面的一个圆形节点的所在层数

2、折半查找

2.1、代码实现

int Binary_Search(SSTable L, int key) {int low = 0, high = L.TableLen - 1, mid;while (low <= high) {mid = (low + high) / 2;if (L.elem[mid] == key)return mid;else if (L.elem[mid] > key)high = mid - 1;else low = mid + 1;}return -1;
}

ALS_{yes} = log_{2}(n+1) -1

2.2、折半查找判定树

①结点的值为该记录的关键字值,树的叶节点为方形,表示查找失败的区间。

②查找成功时的查找长度为从根结点到目的结点的路径上的结点数

③查找失败时的查找长度为从根节点到对应失败节点的父节点的路径上的结点数

④若有序序列有n个元素,则对应判定树有n个圆形叶节点和n+1个方型的叶节点

⑤若mid=\left \lfloor (low+high)/2 \right \rfloor,则对于任何一个结点,右子树结点数-左子树结点数=0或1,即右子树结点个数多于或等于左子树结点个数。下取反之

⑥折半查找的判定树是一棵平衡二叉树

⑦元素个数为n时,树高为\left \lceil log_2{(n+1)} \right \rceil,比较次数最多不会超过树高

3、分块查找

又称索引顺序查找,块内无序,块间有序(第一个块中的最大关键字小于第二个块中的所有记录)

typedef struct {int MaxValue;int low, high;//区间范围
};

顺序查找:ALS_{} = L1+L2=(s^{2}+2s+n)/2s   长度为n,分为b块,每块s个记录

s=\sqrt{n},平均查找长度取到最小值

三、树形查找

1、二叉排序树

1.1、目的及定义

        ①目的:提高查找,插入和删除关键字的速度

        ②定义:左(右)子树上的所有节点均小于(大于)根节点的值  (对二叉排序树进行中序遍历,可以得到一个递增的有序序列)

1.2、二叉排序树的查找

//非递归
BiTNode* BTS_Search(BiTree T, int key) {while (T && T->data != key) {if (key < T->data)T = T->lchild;else T = T->rchild;}return T;
}
//递归
BiTNode* BTS_Search(BiTree T, int key) {if (T == NULL)return;if (T->data == key)return T;else if (T->data > key)return BTS_Search(T->lchild, key);else return BTS_Search(T->rchild, key);
}

1.3、二叉排序树的插入

二叉排序树是一种动态树表,其特点是树的构造通常不是一次生成的,而是在查找过程中,当树不存在关键字值等于给定值的结点时再进行插入

int BTS_Insert(BiTree& T, int key) {if (T == NULL) {T = (BiTNode*)malloc(sizeof(BiTNode));T->data = key;T->lchild = NULL;T->rchild = NULL;return 1;}else if (T->data == key)return 0;//插入失败else if (T->data > key)return BTS_Insert(T->lchild, key);elsereturn BTS_Insert(T->rchild, key);
}

1.4、二叉排序树的构造

void Creat_BST(BiTree& T, int str[], int n) {T = NULL;int i = 0;while (i < n) BTS_Insert(T, str[i++]);
}

1.5、二叉排序树的删除

删除某结点后,该树必须还是一棵二叉排序树

步骤:①若被删的结点z是叶节点,直接删除

           ②若结点z只有一棵左子树或者右子树,让z的子树成为z父节点的子树,代替z的位置

           ③若结点z有两棵子树,让z的直接后继(右子树的min,右子树左走到头)(或直接前驱(左子树max,左子树右走到头))代替z,然后从二叉排序树中删除这个直接后继(或直接前驱),从而转化为①②

1.6、查找效率分析

取决于树的高度。若二叉排序树的左右子树的高度只差的绝对值不超过1,则ALS_{yes} = O(log_{2}n )。若该树为单支树,则ALS=O(n)

1.7、二分查找判定树和二叉排序树的区别

①查找过程:差不多

②平均时间性能:差不多

③唯一性:二分判定树唯一,但二叉排序树不唯一

④维护表的有序性:二叉排序树无需移动结点,只需修改指针即可完成插入和删除,平均执行时间为O(log_{2}n ),二分查找的对象是有序顺序表,插入删除平均执行时间为O(n)

⑤若有序表是静态查找表:宜用顺序表作为存储结构,而采用二分查找实现查找

⑥若有序表是动态查找便:采用二叉排序树作为逻辑结构

2、平衡二叉树AVL

2.1、目的及定义

        ①目的:避免树的高度增长过快,降低二叉排序树的性能,适用于以查为主,很少删/插的场景

        ②定义:左子树和右子树的高度之差的绝对值不超过1

2.2、平衡二叉树的插入

若插入导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A,再对以A为根的子树,调整。

调整方法:

①LL(A的L的L插入新结点导致不平衡):右旋一次,将A的左孩子B作为根,而A成为B的右孩子,B原来的右子树作为A的左子树

②RR(A的R的R插入新结点导致不平衡):左旋一次,将A的右孩子B作为根,而A成为B的左孩子,B原来的左子树作为A的右子树

③LR(A的L的R插入新结点导致不平衡):先左旋再右旋。左旋:以A的左子树B为根,进行一次左旋操作,使B的右孩子C提升到B的位置。再进行右旋,使C提升到A的位置

④RL(A的R的L插入新结点导致不平衡):先右旋再左旋。右旋:以A的右子树B为根,进行一次右旋操作,使B的左孩子C提升到B的位置。再进行左旋,使C提升到A的位置

2.3、平衡二叉树的构造

在构造过程中不断调整使树平衡

2.4、平衡二叉树的删除

先以二叉排序树的方法对结点z删除

步骤:①若被删的结点z是叶节点,直接删除

           ②若结点z只有一棵左子树或者右子树,让z的子树成为z父节点的子树,代替z的位置

           ③若结点z有两棵子树,让z的直接后继(右子树的min,右子树左走到头)(或直接前驱(左子树max,左子树右走到头))代替z,然后从二叉排序树中删除这个直接后继(或直接前驱),从而转化为①②

            ④若导致了不平衡,对结点z向上回溯,找到第一个不平衡的结点w,再进行调整

2.5、平衡二叉树的查找

①与二叉排序树相同,进行关键字的比较次数不超过树的高度

②深度为h的平衡二叉树中含有最少结点数n_{h}=n_{h-2} + n_{h-1} +1,其中n0=0,n1=1,n2=2,n3=4,n4=7......

③含有n个结点的平衡二叉树的最大高度为O(log_{2}n ),因此平均查找效率为O(log_{2}n )

3、红黑树

3.1、目的及定义

①目的:为了保持AVL树的平衡性,在插入和删除操作后,会非常频繁地调整全树整体拓扑结构,代价较大,为放款条件,而引入。适用于频繁删/插操作

②定义:一棵红黑树是满足红黑性质的二叉排序树

        根节点是黑色的

        虚构的外部节点是黑色的(null结点)

        不存在两个相邻的红结点

        对每个结点,从该结点到任意一个外部节点的简单路径上,所含黑节点的数量相同

        引入n+1个外部节点,保证每个内部节点子树非空

        黑高(bh):从某结点出发(不包含该结点)到达一个外部节点的任意一个简单路上上的黑节点的总数

3.2、结论

①从根到外部节点的最长路径不大于最短路径的2倍

②有n个内部节点的红黑树的高度h<=2log_2{(n+1)}

③根节点黑高为h的红黑树中,内部结点至少有多少个?

        最少:总共h层黑节点的满树:2^{h}-1

3.3、红黑树的插入

先以二叉排序树的方法对结点z插入,然后调整:新插入的结点初始为红色

①如果z的父节点是黑色,无需调整

②如果z是根节点,z为黑色,树的黑高增1

③如果z不是根节点,且父节点z.p为红色

        Ⅰ、z的叔结点y是黑色,且z是一个右孩子:LR,左旋再右旋 或 RL,右旋再左旋;

        Ⅱ、z的叔结点y是黑色,且z是一个左孩子:LL,右旋一次 或 RR,左旋一次。以上两者旋转后,将z的爷父结点交换颜色

        Ⅲ、z的叔结点u是红色:父叔都是红色的,爷是黑色的。先将父叔染为黑色,爷染为红色。然后把爷结点作为z重复循环,指针z在树上上移两层。知道满足z为根节点或ⅠⅡ的情况

3.4、红黑树的删除

4、B树和B+树

四、散列表

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/401984.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LoadRunner性能指标分析常用监控参数

性能分析&#xff0c;Windows自带一种 &#xff0c;LoadRunner自带一种&#xff0c;2种参数类似 Windows自带入口 运行中搜索&#xff1a;性能监视器 进到&#xff1a;性能-数据收集器-用户定义-右键-新建-数据收集器集 名称自己任意输入&#xff0c;选择手动创建 数据类型根…

Haproxy的配置详解与使用

一、haproxy简介 HAProxy是一个使用C语言编写的自由及开放源代码软件&#xff0c;其提供高可用性、负载均衡&#xff0c;以及基于TCP和HTTP的应用程序代理。 HAProxy特别适用于那些负载特大的web站点&#xff0c;这些站点通常又需要会话保持或七层处理。HAProxy运行在当前的硬…

JavaScript基础——函数

函数简介 定义函数 调用函数 函数的参数和返回值 函数参数 1.有形参情况下不传递实参 2.传递数量少于形参个数的实参 3.传递数量等于形参个数的实参 函数返回值 报错Uncaught SyntaxError: Illegal return statement 返回数字和字符串 返回数组、对象和函数 没有返回…

nginx服务部署及其平滑升级

概述 1. 7层负载均衡&#xff08;nginx&#xff09; 1. 停掉4层的环境 systemctl disable --now keepalived.service # 停用之前的4层协议方式2. 源码安装nginx tar zxf nginx-1.22.1.tar.gz 具体方式是源码编译“三部曲” ./configure # 负责检查环境&#xff0c;生成指导…

JAVA实现GB/T 32960.3—2016电动汽车远程服务与管理系统技术规范 第3部分:通信协议及数据格式

完整的TCP服务端解析代码 1.maven依赖 不要的依赖自行删除&#xff0c;懒的删了 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-in…

Jenkins持续集成工具学习

一、从装修厨房看项目开发效率优化 二、持续集成工具 三、JavaEE项目部署方式对比 四、JenkinsSVN持续集成环境搭建 五、JenkinsGitHub持续集成环境搭建

8 个最佳 Java IDE 和文本编辑器

从 2024 年使用的最佳 Java IDE 和代码编辑器中进行选择&#xff0c;并提高您的 Java 生产力。 Java 是世界上最流行的编程语言之一&#xff0c;于 1995 年首次推出&#xff0c;它确实践行了“编写一个&#xff0c;随处运行”的座右铭。该语言用途广泛&#xff0c;可用于构建从…

排序算法之希尔排序

title: 希尔排序 date: 2024-7-25 10:48:15 0800 categories: 排序算法 tags:排序算法希尔排序 description: 1959年Shell发明&#xff0c;是简单插入排序的改进版。是一种高效的排序算法&#xff0c;通过分组和逐步缩减增量&#xff0c;使得数组在接近有序的情况下进行最终排…

【docker】dockerfile部署lnmp、docker compose初步

1、dockerfile部署lnmp mkdir /opt/lnmp cd /opt/lnmp mkdir nginx mysql php docker network create --subnet20.0.0.0/24 lnmp-net将wordpress文件夹拷贝到nginx、php文件夹 /opt/nginx/Dockerfile: # 使用官方的nginx镜像作为基础镜像 FROM nginx:latest# 复制默认配置文件…

分销商城小程序系统渠道拓展

线上卖货渠道很多&#xff0c;想要不断提高营收和新客获取&#xff0c;除了自己和工具本身努力外&#xff0c;还需要其他人的帮助来提高商城店铺的整体销量。 搭建saas商城系统网站/小程序&#xff0c;后台上货&#xff0c;设置支付、配送、营销、精美模板商城装修等内容&…

快速解析数据挖掘,最短时间明白什么是数据挖掘------下

信息损失函数 &#xff08;Information Loss Function&#xff09;是衡量在数据转换或处理过程中信息丢失的程度的函数。在数据科学、机器学习和统计学中&#xff0c;信息损失是一个重要的概念&#xff0c;尤其是在数据降维、特征选择、数据压缩和隐私保护等领域。 信息损失函…

数字化营销在公域场景中的无限可能

在如今的商业领域&#xff0c;公域场景为企业提供了广阔的发展空间&#xff0c;而数字化营销则成为了企业在这些场景中脱颖而出的关键利器。 ​ 一、电商平台营销 当企业在淘宝、京东等大型电商平台开设店铺&#xff0c;数字化营销便开始大显身手。 企业不仅能踊跃参与像双十…

【MySQL】explain 执行计划各字段解析

MySQL 如何读写数据&#xff1f;https://blog.csdn.net/weixin_43551213/article/details/140862538 MySQL 索引https://blog.csdn.net/weixin_43551213/article/details/140847916 在上一篇文章中提到了索引&#xff0c;而添加索引是优化 SQL 语句的一个方式&#xff0c;但是…

计算机网络——运输层(进程之间的通信、运输层端口,UDP与TCP、TCP详解)

运输层协议概述 进程之间的通信 运输层向它上面的应用层提供通信服务。 当网络边缘部分的两台主机使用网络核心部分的功能进行端到端的通信时&#xff0c;都要使用协议栈中的运输层&#xff1b;而网络核心部分中的路由器在转发分组时只用到下三层的功能。 Q1&#xff1a;我们…

mysql windows安装与远程连接配置

安装包在主页资源中 一、安装(此安装教程为“mysql-installer-community-5.7.41.0.msi”安装教程&#xff0c;安装到win10环境) 保持默认选项&#xff0c;点击”Next“。 点开第一行加号展开一路展开找到“MySQL Server 5,7,41 - X64”点击选中点击一下中间只想右侧的箭头看到…

Attention注意力机制

神经网络注意力机制代码实现 import torch import torch.nn as nn import torch.nn.functional as F# MyAtt类实现思路分析 # 1 init函数 (self, query_size, key_size, value_size1, value_size2, output_size) # 准备2个线性层 注意力权重分布self.attn 注意力结果表示按照指…

简单测试AOP五种增强执行时机

1. 目标方法类&#xff0c;spring代理bean Component public class Test {public void test(){System.out.println("test 目标方法");}public void testException(){throw new RuntimeException();} } 2. 配置类 Configuration ComponentScan EnableAspectJAutoPr…

unity项目打包为webgl后应用于vue项目中(iframe模式)的数据交互

参考文章&#xff1a; 1.Unity打包WebGL: 导入Vue 2.unity文档-WebGL&#xff1a;与浏览器脚本交互 3.unity与vue交互(无第三方插件&#xff09; 目录 一、前期工作1.新建.jslib文件2.新建.cs脚本3. 新建一个Text对象和button按钮对象4.添加脚本空对象UIEvent5.导出unity为w…

Windows配置开机直达桌面并跳过锁屏登录界面在 Windows 10 中添加在启动时自动运行的应用

目录 Win10开机直达桌面并跳过锁屏登录界面修改组策略修改注册表跳过登录界面 在 Windows 10 中添加在启动时自动运行的应用设置系统级别服务一、Windows下使用sc将应用程序设置为系统服务1. 什么是sc命令&#xff1f;2. sc命令的基本语法3. 创建Windows服务的步骤与示例创建服…

CANoe软件中Trace窗口的筛选栏标题不显示(空白)的解决方法

文章目录 问题描述原因分析解决方案扩展知识总结问题描述 不知道什么情况,CANoe软件中Trace窗口的筛选栏标题突然不显示了,一片空白。现象如下: 虽然不影响CANoe软件的使用,但是观感上非常难受,对于强迫症患者非常不友好。 原因分析 按照常规思路,尝试了: 1、重启CAN…