只进行查找的称为静态查找表;
在查找的过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的元素,称为动态查找表。
静态查找:
1.顺序查找:
算法思想:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查
找成功,找到所查记录;反之,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录,查找不成功
平均查找长度:(n+1)/2
2、二分查找(有序表):
算法思想:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。
平均查找长度:(n+1)/n *log2(n+1) -1
3、分块查找(索引顺序查找):
算法思想:首先将一个线性表(即主表)按照一定的函数关系和条件划分为若干个逻辑字表,为每个字表建立一个索引项,由
所有的字表的索引项构成一个索引表。当进行分块查找时,先根据所给的关键字查找索引表,从中找出给定k值小于或等于索引
值的那个索引块,找到待查块,然后在主表中查找该快,查找待查的记录。
平均查找长度:索引表是有序的,所以在索引表中可以用顺序查找,也可以用折半查找;而块内的记录的随机排序的,所以在
块中用顺序查找。
顺序查找确定块:平均查找长度为1/2 *(n/s +s)+1
二分查找确定块:平均查找长度为log2(n/s +1)+s/2
动态查找:(表结构动态生成)
http://www.doc88.com/p-930477746758.html
1、二叉排序树查找
二叉排序树(二叉搜索树、二叉查找树):二叉排序树中序遍历得到的必定是一个有序序列。
查找过程:
(1)若查找树为空,查找失败;
(2)若查找树非空,将给定值和查找树的根节点比较:
若相等,查找成功,结束查找过程;
若给定值小于根节点,查找将在根节点的左子树上继续进行,转至(1)
若给定值大于根节点,查找将在根节点的右字树上继续进行,转至(1)
时间复杂度:平均O(logn),最坏O(n)
二叉排序树的插入:
新插入的结点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
二叉排序树的结点删除:
假设在二叉排序树上被删结点为p,其双亲结点为f,且p为f的左孩子,下面分三种情况讨论:
(1)若p结点为叶子节点,即pl和pr均为空树,由于删去叶子节点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
(2)若p结点只有左子树pl或者只有右子树pr,此时只要令pl和pr直接成为其双亲结点f的左子树即可。
(3)若p结点的左子树和右子树均不空。
2、二叉平衡树
左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子定义为该节点
的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只能是-1,1,0.平衡树查找的时间复杂度为O()l
ogn
- 浏览: 4933718 次
- 性别:
- 来自: 南京
文章分类
- 全部博客 (2844)
- java (1094)
- hadoop (37)
- jvm (39)
- hbase (11)
- sql (25)
- 异常 (83)
- div css (6)
- 数据库 (95)
- 有趣的code (15)
- struts2 (6)
- spring (124)
- js (44)
- 算法 (65)
- linux (36)
- hibernate (7)
- 中间件 (78)
- 设计模式 (2)
- 架构 (275)
- 操作系统 (91)
- maven (35)
- tapestry (1)
- mybatis (9)
- MQ (101)
- zookeeper (18)
- 搜索引擎,爬虫 (208)
- 分布式计算 (45)
- c# (7)
- 抓包 (28)
- 开源框架 (45)
- 虚拟化 (12)
- mongodb (15)
- 计算机网络 (2)
- 缓存 (97)
- memcached (6)
- 分布式存储 (13)
- scala (5)
- 分词器 (24)
- spark (104)
- 工具 (23)
- netty (5)
- Mahout (6)
- neo4j (6)
- dubbo (36)
- canal (3)
- Hive (10)
- Vert.x (3)
- docker (115)
- 分布式追踪 (2)
- spring boot (5)
- 微服务 (56)
- 淘客 (5)
- mesos (67)
- php (3)
- etcd (2)
- jenkins (4)
- nginx (7)
- 区块链 (1)
- Kubernetes (92)
- 驾照 (1)
- 深度学习 (15)
- JGroups (1)
- 安全 (5)
- 测试 (16)
- 股票 (1)
- Android (2)
- 房产 (1)
- 运维 (6)
- 网关 (3)
最新评论
-
明兜3号:
部署落地+业务迁移 玩转k8s进阶与企业级实践技能(又名:Ku ...
Kubernetes系统常见运维技巧 -
q328965539:
牛掰啊 资料收集的很全面
HDFS小文件处理解决方案总结+facebook(HayStack) + 淘宝(TFS) -
guichou:
fluent挂载了/var/lib/kubelet/pods目 ...
kubernetes上部署Fluentd+Elasticsearch+kibana日志收集系统 -
xu982604405:
System.setProperty("java.r ...
jmx rmi 穿越防火墙问题及jmxmp的替代方案 -
大漠小帆:
麻烦问下,“获取每个Item相似性最高的前N个Item”,这个 ...
协同过滤推荐算法在MapReduce与Spark上实现对比
发表评论
-
Kryo 使用指南
2017-12-05 20:14 18831、Kryo 的简介 Kryo 是一个快速序列化/ ... -
spring session序列化问题排查
2017-12-01 19:07 6153严重: Servlet.service() for ser ... -
利用junit对springMVC的Controller进行测试
2017-11-30 16:26 1399平时对junit测试service/D ... -
Java内存模型之重排序
2017-11-29 09:44 817在执行程序时,为了提供性能,处理器和编译器常常会对指令进行重 ... -
pmd spotbugs 文档
2017-11-28 10:02 0https://pmd.github.io/pmd/pmd ... -
PMD、FindBug、checkstyle、sonar这些代码检查工具的区别?各自的侧重点是什么?
2017-11-28 10:01 2096可以说都是代码静态分析工具,但侧重点不同。pmd:基于源代码 ... -
阿里巴巴Java代码规约插件p3c-pmd使用指南与实现解析
2017-11-23 17:09 1534阿里巴巴Java代码规约插件安装 阿里Java代码规 ... -
静态分析工具PMD使用说明 (文章来源: Java Eye)
2017-11-23 17:07 1105质量是衡量一个软件是否成功的关键要素。而对于商业软件系统,尤 ... -
MyBatis 使用 MyCat 实现多租户的一种简单思路
2017-11-20 18:27 2799本文的多租户是基于多数据库进行实现的,数据是通过不同数据库进 ... -
Spring+MyBatis实现数据库读写分离方案
2017-11-20 17:15 1020百度关键词:spring mybatis 多数据源 读写分离 ... -
数据库连接池druid wallfilter配置
2017-11-20 11:38 1214使用缺省配置的WallFilter <be ... -
java restful 实体封装
2017-11-16 09:47 1538package com.mogoroom.bs.commo ... -
dak
2017-11-15 11:21 0package zzm; import jodd.ht ... -
Java内存模型之从JMM角度分析DCL
2017-11-15 09:35 590DCL,即Double Check Lock,中卫双重检查锁 ... -
Java 打印堆栈的几种方法
2017-11-14 09:36 4655java 中可以通过 eclipse 等工具直接打印堆栈, ... -
Servlet Session学习
2017-11-10 09:25 503HTTP 是一种"无状 ... -
浅析Cookie中的Path与domain
2017-11-10 09:26 1010Path – 路径。指定与co ... -
入分析volatile的实现原理
2017-11-08 09:47 624通过前面一章我们了解了synchronized是一个重量级的 ... -
Spring MVC-ContextLoaderListener和DispatcherServlet
2017-11-15 09:35 635Tomcat或Jetty作为Servlet ... -
搭建spring框架的时候,web.xml中的spring相关配置,可以不用配置ContextLoaderListener(即只配DispatcherServl
2017-11-07 18:27 1382搭建spring框架的时候,web.xml中的sprin ...
相关推荐
排序和查找算法速度排序和查找算法速度排序和查找算法速度排序和查找算法速度
3种查找算法,顺序查找 折半查找 索引查找,c语言编写,可直接运行
各类查找算法的比较(数据结构课程设计) 开始的时候提示输入一组数据。并存入一维数组中,接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序,然后利用三个标志...
写出二分查找算法。给出一组有序的测试数据例如:1,3,4,7,8 查找有无3
几种常用查找算法的比较,内含顺序查找、二分查找、二叉树查找、哈希表查找。
二叉排序树:更新二叉排序树、查找结点、插入结点、删除结点、中序输出排序树 、返回 查找算法:顺序查找、二分查找、二插排序树、返回
查找算法:二分查找、顺序查找的实现 参见博客:http://blog.csdn.net/xiaowei_cqu/article/details/7748260
查找算法授课ppt,包含基础的查找算法的概念介绍和C语言编程时间的简单展示
折半查找算法在顺序表中插入一个元素讲解.pdf
讲述了数据结构中的几种查找算法,比如二分查找算法等,分析了其平均长度,时间以及空间开销
折半查找算法 顺序表 折半查找算法C语言版
二叉查找与递归二叉查找算法
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契...
根据自己搜集的资料很实际实用,总结了几种常用的查找算法
java 几种查找算法
静态查找和动态查找 内查找和外查找 顺序查找又称线性查找(Sequential Search) 二叉查找算法:二分查找又称折半查找(Binary Search)
对C++上的查找算法进行总结,非常的实用,是数据结构入门必学
分别用递归和非递归方法实现二分查找算法 的完整程序,indexof()返回的是循环实现的二分法查找,getindex()实现的是递归算法实现的二分法查找。
电子狗数据导入算法和查找算法
该算法是在折半算法的基础上,推广折段的段数,通过简单的数学模型证明了最优的分段数为3,而不是2(即折半)。在文章的最后给出了算法的C程序代码。如果有应用到实际中,算法还可以进一步精简。