第十章 搜索 静态搜索结构 动态搜索结构 散列 可扩充散列.

Slides:



Advertisements
Similar presentations
练一练: 在数轴上画出表示下列各数的点, 并指出这些点相互间的关系: -6 , 6 , -3 , 3 , -1.5, 1.5.
Advertisements

二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决了树的
第 9 章 查找.
第九章 查找.
主讲:计算机工程学院 李兰 答疑地点:主教学楼B区213
第一章 行列式 第五节 Cramer定理 设含有n 个未知量的n个方程构成的线性方程组为 (Ⅰ) 由未知数的系数组成的n阶行列式
数据结构课程的内容.
数据结构作业及答案 (C语言版).
第6章 树和二叉树 树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结构。
第九章. 查找 (Chapter 9. Searching)
第9章 查找 9.1 基本概念和术语 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 9.5 小结 顺序查找
数据结构与算法 Data Structure Algorithms
第8章 查找 8.1 静态查找表 8.2 动态查找表 8.3 哈希表.
数据结构 (DATA STRUCTURE).
第九章 查找 £9.1 概述 £9.2 静态查找表 £9.3 动态查找表 £9.4 哈希表 £9.1.1 查找表 £9.2.1 概述
第九章 查找.
树(三) 2012初赛知识点梳理.
树和二叉树(四).
第7章 查找 丽水学院工学院.
第九章查找.
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
Hadoop I/O By ShiChaojie.
树和二叉树(三).
第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找.
第九章 查找 2018/12/9.
第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找.
本章重点难点 重点:顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。
第7章 查找 北京师范大学 教育技术学院 杨开城.
第九章 查找(Search) 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 Hash表.
第七章 集合与搜索 集合及其表示 并查集 静态搜索表 二叉搜索树 AVL树.
何谓查找表 ? 查找表是由同一类型的数据元素(或记录)构成的集合。
第7章 查找 本章中介绍下列主要内容: 静态查找表及查找算法:顺序查找、折半查找 动态查找表及查找算法:二叉排序树 哈希表及查找算法.
第5章 树和二叉树 5.1树 5.2二叉树 5.3二叉树的遍历 5.4线索二叉树 5.5树、森林与二叉树的转换 5.6哈夫曼树.
第11讲 树和二叉树(二).
图内容回顾 图 Dijkstra算法 最短路径 Floyd算法 拓扑排序 邻接矩阵 有向图的应用 DAG图 关键路径 邻 接 表 存储结构
Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算
报告人:陈思同 数据结构与数据库习题课 报告人:陈思同
第五章 树 5.1 树的定义 树是一类重要的非线性数据结构,是以分支关系定义的层次结构 定义
Ch.9 查找 查找和排序是两个重要的运算 §9.1 基本概念
第5到第6章的勘误表 注意:这个 c 应改为 d 1、第 92 页 倒数第 7 行:
数据结构 第八章 查找.
无向树和根树.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
Algorithm Design and Analysis
§ B-树 1.概念 B-树是一种完全平衡的多阶查找树,主要是作为磁盘文件的索引组织,用于外部查找。
顺序表的删除.
顺序查找.
第4章 Excel电子表格制作软件 4.4 函数(一).
3.16 枚举算法及其程序实现 ——数组的作用.
1.2 子集、补集、全集习题课.
树和图 tree and graph 蔡亚星.
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第七、八次实验要求.
分数再认识三 真假带分数的练习课.
#define RBTREE_RED 0 #define RBTREE_BLACK 1 typedef int dataType; typedef struct treeNode{ dataType key; int color; //red:0.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表.
第9章 查找 静态查找表 二叉排序树 平衡二叉树(AVL树) 小结 B树 哈希表.
第六章 Excel的应用 五、EXCEL的数据库功能 1、Excel的数据库及其结构 2、Excel下的数据排序 (1)Excel的字段名行
基于列存储的RDF数据管理 朱敏
1 School of Computing and Information Engineering.
插入排序的正确性证明 以及各种改进方法.
第七章 搜索结构 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
§4.5 最大公因式的矩阵求法( Ⅱ ).
第9章 查找 9.1 查找的基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表查找.
本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
第二次课后作业答案 函数式编程和逻辑式编程
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

第十章 搜索 静态搜索结构 动态搜索结构 散列 可扩充散列

查找 搜索 搜索结构 同一数据类型(纪录)的元素 构成的数据集合。 搜索 在数据集合中寻找满足条件的对 象(数据元素)。 查找 搜索 搜索结构 同一数据类型(纪录)的元素 构成的数据集合。 搜索 在数据集合中寻找满足条件的对 象(数据元素)。 关键字 数据元素中某个字段(数据项) 的值。 主关键字 唯一地表示一个纪录 。 次关键字 标识若干纪录

搜索成功 找到满足条件的数据对象 报告该对象在结构中的位置 给出整个纪录的信息 搜索失败 搜索不成功 静态搜索 搜索结构在搜索前后不发生变化 动态搜索 搜索的同时执行插入或删除 结构自行调整 提高效率 先排序,分类,编目,索引 优化结构

一、静态搜索结构 基于数组的数据表类 顺序表——线性表、数组、链表。 (1) 顺序搜索 从头至尾逐个比较 最快O(1) 最慢O(n) (1) 顺序搜索 从头至尾逐个比较 最快O(1) 最慢O(n) 搜索成功的等概率平均时间复杂性 O((n+1)/2) (1+2+3+······+n) /n=(n+1)/2 搜索失败O(n+1) 搜索的等概率平均时间复杂性 O(3(n+1)/4) 搜索成功失败各半 ((1+2+······+n)+n(n+1)) /2n =3(n+1)/4

(2)有序表的搜索 折半搜索 对已排序的搜索结构先确定中点,比较待查关键字与中点关键字的大小,反复直到成功。 求n个数据折半查找的等概率成功搜索的平均时间复杂性 1 2 3 4 5 6 7 8 9 10 1 2 2 3 3 3 3 4 4 4 1+2*2+4*3+3*4=29 O(29/10)

S=1+2*2+4*3+8*4+······+2k-1*k = 1+2*2+3*4+4*8+······+k*2k-1 k 满二叉树n个数据的总查找次数: 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 S=1+2*2+4*3+8*4+······+2k-1*k = 1+2*2+3*4+4*8+······+k*2k-1 k s =∑j·2j-1 其中 n=2k-1 j=1

满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1 S=1+2·2+3·4+4*8+5*16+·····+k·2k-1 = 1+2+4+8+16+···+2k-1+ 2+2·4+3·8+4·16+····+(k-1)·2k-1 = 1+2+4+8+16+···+2k-1+ 2·(1+2·2+3·4+4*8+5*16+·····+(k-1)·2k-2) = 1+2+4+···+2k-1+2·(1+2+4+···+2k-2)+ 22·(1+2+4+···+2k-3)+·····+2k-2·(1+2)+2k-1 =2k-1+2·(2k-1-1)+22·(2k-2-1)+·····+2k-2·(22-1)+ 2k-1(2-1) =k·2k-(1+2+4+···+2k-1)=k·2k-(2k-1)=(k-1)·2k+1

满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1 令s=f(k), k=1,2,3,4,······ f(1)=1 f(2)=5 f(3)=17 f(4)=49 f(5)=129 ······· f(k)-1= 0, 22, 24, 3·24,27,······ = 0·21, 1·22, 2·23, 3·24,4·25····· 猜想 f(k)-1=(k-1)·2k

k f(k)= s =∑j·2j-1 其中 n=2k-1 j=1 f(k)-1=(k-1)2k 证明 1) f(1)-1=0 2) f(k+1)-1=f(k)+(k+1)·2k –1 = (k-1)2k+ (k+1)·2k =2·k·2k=k·2k+1 =(k+1-1)·2k+1 S=(k-1)2k+1

满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1 S= (k-1)·2k+1 由 n=2k-1 得 k=log2(n+1) S=(n+1)(log2(n+1)-1)+1 = (n+1)log2(n+1)-n 满二叉树n个数据的搜索成功平均概率时间复杂性 ((n+1)/n) log2(n+1)-1 当n>50时 近似于 log2(n+1)-1

n个元素的折半搜索 2k-1≤n<2k+1-1 搜索成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间 即 k-1 和 k 之间 k=[log2(n+1)] n个元素的折半搜索成功平均概率时间复杂性 log2(n+1)-1/2

根据斐波那契序列的特点对有序表分割 斐波那契搜索 0.618法 斐波那契序列 1 2 3 5 8 13 21 34 55······f(n)······ f(n+2)=f(n)+f(n+1) 从20个数的数表中查找一个纪录 先找比较第13个,如果小,再比较第8个,···· 如果大 比较后几个数的第5个······ 每次都比较位于这个数列的黄金分割点0.618处

平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差 以下序列中查找元素10的过程 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 平均查找性能优于折半查找 O(log2n) 最坏情况比折半查找差

(3)静态树表的搜索 不等概率查找时折半查找不一定好, 以每点查找次数(概率)为这点的权wi 带权二叉树总路径长度 PH=∑wihi i 不同于霍夫曼树:每个结点都有权值,都 要查找。

PH=3·1+2·2+2·4+1·3 +5·3+4·3+3·3+1·4+5·4 A B C D E F G H I =78 A B C D E F G H I 1 1 2 5 3 4 4 3 5 3 E 查找次数 不是静态最优二叉树 C 2 G 4 B D H F 3 1 5 4 A I 1 5 权值

次优查找树 Nearly Optimal Search 数据 al,al+1,······,ai-1,ai, ai+1,······,ah 权值 wl,wl+1,·····wi-1,wi,wi+1,·····,wh 令 h i-1 Δpi= ∑wj-∑wj j=i+1 j=l 取最小值: Δpi=min{Δpj: l≤j≤h} 以ai为根, al+1,······,ai-1为左子树 ai+1,······,ah 为右子树 构造次优查找树

i 令swi= ∑wj , Δpi = swh-swi-swi-1 j=l A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 s wi 1 2 4 9 12 16 20 23 28 Δpi 27 25 22 15 7 0 8 15 23 Δpi 11 9 3 1 9 8 1 7 Δpi 3 1 2

A B C D E F G H I wi 1 1 2 5 3 4 4 3 5 平均查找次数 O(HP/swh) 4 F 1*3+3*3+4*3+5*3+ 1*4+2*4=71<78 D 5 H 3 B E I G 1 5 次最优树 3 4 A C 1 2 平均查找次数 O(HP/swh)

索引顺序表 分块有序 后一子表中的关键字都大于前一子表中的关键字 索引表 最大关键字 起始地址 22 48 86 1 7 13 22 12 9 20 33 42 44 38 24 48 60 58 74 49 86 53 分块有序 后一子表中的关键字都大于前一子表中的关键字

索引顺序表的查找 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索 索引表 22 48 86 1 7 13 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中搜索

索引顺序表的查找成功的平均概率时间复杂性 索引表查找时间+子表查找时间 设索引表长为s,搜索表长为n,被平均分成s块, 每块长n/s, 索引表平均查找时间 (s+1)/2 子表平均查找时间 (n/s+1)/2 ½(s+1)+ ½(n/s+1)= ½(s+n/s)+1 当 s=√n 时 有最小值 √n +1

有序索引顺序表 当索引顺序表已经排序时,子块搜索可以用折半搜索。 平均查找时间: (s+1)/2 +log2(1+n/s)-1/2 = log2(1+n/s)+s/2 索引也用折半查找,平均查找时间 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1 当s= √n 时 2 log2(√n +1)-1

二、动态搜索表 特点 查找过程中生成搜索表 查找失败时插入纪录 二叉搜索树 平衡二叉搜索AVL树

二叉搜索树 (二叉排序树) 49 38 65 97 76 13 27 49 其左非空子树上所有结点的值都小于根结点的值 其右非空子树上所有结点的值都大于根结点的值 左右子树也是二叉搜索树 二叉搜索树的作用:排序,检索 49 38 65 97 76 13 27 49 49 65 38 97 13 49 27 76

二叉搜索树的插入过程 57 20 60 45 12 8 57 60 20 11 59 50 3 57 20 8 45 60 59 3 12 50 11 8 45 59 3 45 12 50 12 57 11 8 20 60 50 3 11 59

平衡二叉树AVL树 ——加快查找排序的速度 定义: 左右两子树深度之差不超过1, 左子树和右子树都是平衡二叉树。 45 45 平衡 不平衡 57 12 12 60 8 20 8 20 50 3 11 3 11 59

同一个数组的二叉排序树和二叉平衡树 20 30 80 40 10 60 50 70 49 20 49 30 65 13 49 30 10 49 60 65 13 20 80 27 40 13 40 80 27 10 97 13 60 50 49 70 50 97 70 49

AVL树的结点 增加一个平衡因子 balance=height(right subtree)-height(left subtree) data balanceFactor right balance=height(right subtree)-height(left subtree) balance=1或-1

平衡因子 1 49 1 65 38 13

左重加左——右转 结点p左重,还要加一个左结点 不平衡 右转: 将p作lc的右子结点 p lc lc p 49 65 38 49 13 65 10 p 10 38

左重加左——右转 结点p左重,还要加一个左结点 不平衡 右转:将p作lc的右子结点, 将lc的右子树接成p的左子树 p lc lc p 38 13 lc 13 40 p 38 10 20 10 40 4 20 4

右重加右——左转 结点p右重,还要加一个右结点 不平衡 左转:将p作rc的左子结点, 将rc的左子树接成p的右子树 p rc rc p 38 40 rc 13 40 p 45 38 45 39 4 13 39 4

左重加左的右——双旋 左转再右转 结点p左重 lc的右子树加一个结点 不平衡 先以lc np为轴左转 再以p, np为轴右转 p np p 左重加左的右——双旋 左转再右转 结点p左重 lc的右子树加一个结点 不平衡 先以lc np为轴左转 再以p, np为轴右转 p np p 38 38 20 p lc np lc 40 20 13 40 38 13 lc np 20 13 26 10 40 26 10 26 10

右重加右的左——双旋 右转再左转 结点p右重 rc的左子树加一个结点 不平衡 先以rc np为轴右转 再以p, np为轴左转 p np p 右重加右的左——双旋 右转再左转 结点p右重 rc的左子树加一个结点 不平衡 先以rc np为轴右转 再以p, np为轴左转 p np p 38 38 46 rc np np p 46 13 13 55 55 38 rc np 41 46 55 67 67 13 41 41 67

AVL树的生成 20 30 80 40 10 60 50 70 左转 左重加左的右 左转再右转 49 30 49 65 13 20 49 20 30 80 40 10 60 50 70 49 30 49 65 13 20 49 30 13 65 49 27 80 20 27 80 10 40 左转 13 60 13 65 49 30 49 27 80 左重加左的右 左转再右转 20

20 30 80 40 10 60 50 70 13 30 49 65 左转 49 27 80 20 60 13 49 30 65 10 49 27 80 20 40 13 右转 10 40 13 49 13 30 65 60 49 20 60 左重加左的右 左转再右转 10 80 27 40 13

20 30 80 40 10 60 50 70 13 65 49 30 49 20 60 10 80 27 40 13 65 30 13 49 50 70 13 13 49 20 60 10 27 80 40 13

AVL树的高度 设AVL树高度为h, 这棵树至少多少结点? 设至少有nh个结点 n0=0, n1=1 , n2=2, nh+1=nh+nh-1+1, nh+1+1=nh+1+nh-1+1, 令 fh= nh+1, 则 f0=1, f1=2 , fh+1=fh+fh-1 nh = fh-1 nh=(51/2)*((1+ 51/2)/2)h+3 -1

n个结点的AVL树的高度h至多是多少? n=(51/2)*((1+ 51/2)/2)h+3 -1 log2 (n+1)-log251/2= (h+3 )(log2 ((1+ 51/2)/2)) log2 ((1+ 51/2)/2)≈0.694 h+3= (log2 (n+1)-log251/2)/0.694 h<(3/2) log2 (n+1)-1

练习 一. 画出以下输入所对应AVL树: 1)R,O,T,A,R,Y,C,L,U,B 2)60,25,7,99,15,3,10 38,59,62,34 二. 分别给出这两棵树的前序,中序, 后序遍历输出 三、高度为5的AVL树至少几个节点。 15个节点的AVL树至多多高?

二叉搜索树的查找分析 平均等概率查找时间 (1+2+2+3+3+3)/6=14/6 (1+2+3+4+5+6)/6=7/2 8 8 3 45 57 12 60 8 20 45 20 (1+2+3+4+5+6)/6=7/2 12 11 8 3

随机二叉搜索树等概率平均查找时间 P(n)≤2(1+1/n)lnn O(log2n) 最坏 O(n/2)

平衡二叉搜索AVL树的查找分析 求含有n个关键字的AVL树的最大深度? 设深度h的AVL树的最小结点数为Nh N0=0, N1=1, N2=2 Nh= Nh-1+ Nh-2+1 Nh+1= Nh-1+1+ Nh-2+1 令 F(h)= Nh+1, 则 F(h)=F(h-1)+F(h-2) Nh Nh-1 Nh-2

深度h的AVL树的最小结点数Nh F(h)= Nh+1, F(h)=F(h-1)+F(h-2) F(h)是斐波那契数列 F(1)=1 F(2)=2 F(3)=3 F(4)=5 F(5)=8 ······· N1=0, N2=1, N3=2, N4=4, N5=7, N6=12,····

平衡二叉搜索AVL树的查找分析 设 n个结点的AVL树的最大深度为h, 则 Nh=n F(h)=n+1 可以得到h. h就是最大查找次数 等概率平均查找成功时间复杂性O(log2n)

B-树 平衡的多路搜索树 B-树的定义 空树 或 m叉树 每个结点至多有m棵子树, 如根结点不是叶,至少有两棵子树, 除根之外,所有非终端结点至少有┌m/2 ┐棵子树 ,本节中记为[m/2], m=3时 称为2-3树 所有的非终端结点含有信息 (n,A0,K1,A1,K2,······,Kn,An) [m/2]-1个关键字 5) 所有叶结点都在同一层次 ,叫做失败结点。

所有的非终端结点含有信息 n A0 K1 A1 K2 ······ Kn An n : 有n+1棵子树, K1≤K2≤······≤Kn 关键字有序序列, 指针Ai-1指向子树中结点的关键字小于Ki,

1 · 35 1 · 18 2 · 43 78 1 · 11 1 · 27 1 · 39 3 · 47 53 1 · 99 F F F F F F F F F F F

B-树的搜索过程 检索结点53 每增加一个关键字增加一个结点 最底层空结点有n+1个 1 · 35 1 · 18 2 · 43 78 F F 11 1 · 27 1 · 39 3 · 47 53 1 · 99 F F F F F F F F F F F 每增加一个关键字增加一个结点 最底层空结点有n+1个

B-树的查找分析 n个关键字,m阶B-树的最大深度h, 深度h的m阶B-树的最少结点数=n, 设第i层最少结点数Ni N1=1, N2=2, N3=2 [m/2] N4= 2 [m/2]2, N5= 2[m/2]3 ······ Nh= 2[m/2]h-2 Nh+1= 2[m/2]h-1 底层叶结点都是空结点 n+1≥Nh+1

h·[m/2] ≤ (log[m/2]((n+1)/2)+1)·[m/2] O(log2n) Nh+1= 2[m/2]h-1≤ n+1 h-1 ≤ log[m/2]((n+1)/2) h ≤ log[m/2]((n+1)/2)+1 n个结点的B-树的最大查找次数 为 h·[m/2] ≤ (log[m/2]((n+1)/2)+1)·[m/2] O(log2n)

B-树的插入 先从底层以大小增加一个关键字 1. 结点中的关键字不超过m时完成。 2.结点中的关键字等于m时: 将该结点分成左右两个结点 中间一个关键字上升至双亲结点 重复2.直至根

增加一个关键字60 插入底层 1 · 35 1 · 18 2 · 43 78 F F F F F F F F F F F 1 · 11 1 27 1 · 39 3 · 47 53 1 · 99 F F F F F F F F F F F 插入底层

增加一个关键字60 将53上移结点分裂 1 · 35 1 · 18 2 · 43 78 F F F F F F F 1 · 39 3 · 47 53 60 1 · 99 F F F F F F F 将53上移结点分裂

增加一个关键字60 再将53上移结点分裂 1 · 35 1 · 18 2 · 43 53 78 F F F F F F F F 1 · 39 47 1 · 60 1 · 99 F F F F F F F F 再将53上移结点分裂

增加一个关键字60 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F 1 · 39 1 · 47 1 99 F F F F F F F F

B-树的删除 找到要删除的关键字所在结点,删除。 若这个结点是最下层结点,并且其中关键字数不少于[m/2]-1删除完成。 若删除的是非终端结点中的关键字Ki,以指针Ai 所指子树的最小关键字Y代替Ki,删除Y. 重复直至叶结点 若这个结点是最下层结点,但是其中关键字数不少于[m/2]-1,删除完成。

若该结点的左右兄弟结点的关键字数都等于[m/2]-1,则将其与一个兄弟结点合并,从双亲结点下移一个关键字被删除关键字的位置。 重复2。

删除一个关键字53 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F F 1 · 39 1 · 47 60 65 1 · 99 F F F F F F F F F

删除一个关键字53 关键字78上移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F F F 1 · 39 1 47 1 · 60 65 1 · 99 F F F F F F F F F 关键字78上移

删除一个关键字53 关键字99上移 1 · 35 78 1 · 18 2 · 43 1 99 F F F F F F F F F 1 · 39 1 · 47 1 · 60 65 1 · F F F F F F F F F 关键字99上移

删除一个关键字53 关键字65上移,99下移, 1 · 35 78 1 · 18 2 · 43 1 65 F F F F F F F F 1 39 1 · 47 1 · 60 1 · 99 F F F F F F F F 关键字65上移,99下移,

删除一个关键字53 关键字65继续上移,与78交换,删除完成 1 · 35 65 1 · 18 2 · 43 1 78 F F F F F 39 1 · 47 1 · 60 1 · 99 F F F F F F F F 关键字65继续上移,与78交换,删除完成

删除一个关键字53 关键字78上移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F F 1 · 39 1 · 47 1 · 60 1 · 99 F F F F F F F F 关键字78上移

删除一个关键字53 1 · 35 53 1 · 18 2 · 43 1 78 F F F F F F F F 1 · 39 1 · 47 1 60 1 · 99 F F F F F F F F

删除一个关键字53 关键字99上移 1 · 35 78 1 · 18 2 · 43 1 99 F F F F F F F F 1 · 39 47 1 · 60 1 · F F F F F F F F 关键字99上移

删除一个关键字53 两个结点合并,关键字99下移 1 · 35 78 1 · 18 2 · 43 1 F F F F F F F 1 · 39 1 · 47 1 · 60 99 F F F F F F F 两个结点合并,关键字99下移

删除一个关键字53 两个结点合并,关键字78下移 1 · 35 1 · 18 2 · 43 78 F F F F F F F 1 · 39 47 1 · 60 99 F F F F F F F 两个结点合并,关键字78下移

删除一个关键字53 关键字78继续下移,与60交换 1 · 35 1 · 18 2 · 43 60 F F F F F F F 1 · 39 47 1 · 78 99 F F F F F F F 关键字78继续下移,与60交换

B+树 B-树的变形 根结点(非叶时)至少有两个结点 除根外,非叶结点至少有[m/2]棵子树 最多有m棵子树,非叶结点都是索引, 含有子树中的最大或最少关键字 含有n个关键字的非叶结点有n棵子树 所有的叶子结点都在同一个层次上,叶子结点中包含全部关键字,以及指向这些关键字的指针

B+树 根 59 97 15 44 59 72 97 叶 10 15 21 37 44 51 59 63 72 85 91 97 两种查找:从根开始,从叶起始

B+树查找成功的时间复杂性 设第i层最少结点数Ni N1=[m/2], N2=2[m/2], N3=2 [m/2]2 ······ Nh= 2[m/2]h-1 n≥Nh n ≥ 2[m/2]h-1 h-1=log[m/2](n/2) h=log[m/2](n/2)+1 h·[m/2]=(log[m/2](n/2)+1)·[m/2] O(log2n)

B+树的插入和删除 与B-树类似

键树__ 数字查找树 Trie树 (Digital Search Tree) 度≥2的树, 每个结点只包含组成关键字的部分符号。 为查找方便,约定简述为有序树,同层兄弟有序排列。

键树的例 16个关键字 CAI,CAO,LI,LAN,CHA,CHANG,WEN, CHAO,YUN,YANG,LONG,WANG,ZHAO, LIU,WU,CHEN

以首字符分组: {CAI,CAO, CHA,CHANG, CHAO,CHEN} {LI,LAN, LONG, LIU} {WEN,WANG,WU} {YANG,YUN} {ZHAO}

继续以第二,第三····字符分组 直到每组一个关键字 {{{CAI},{CAO}}, {{CHA},{CHANG}, {CHAO}}, {CHEN}} {{LAN} , {LIU}, {LONG}} {{WANG}, {WEN},{WU}} {{YANG},{YUN}}

以集合,子集,元素的层次组成树 C L W Y Z A H A U H A I O A E U I O A E N $ U N N N $ G G $ N $ O $ $ $ A O N $ $ $ $ $ G $ $ $ $

键树的孩子兄弟表示———双链树 C L W Y Z A H A U H A I O A E U I O A E N $ U N N N $ G G $ N $ O $ $ $ A O N $ $ $ $ $ G $ $ $ $

键树的查找成功时间复杂性 键树的结点的最大度d由基决定: 关键字是英文单词: d=27 数字: d=11 设键树的深度为h 假设关键字的位数都相等 则查找一个字的平均长度 h(1+d)/2

三、哈希表 Hashing table___散列 一种搜索结构 不经过任何比较,一次存取就能得到所查的纪录: 每个记录和存储位置之间建立一个一一对应关系 f , 对每个关键字K, f(K)就是K的存储位置 称f为哈希函数。

哈希函数的例 int HF(int key)//直接定址法 a,b是选定的常数 { return a*key+b;} 1993 1994 1996 1999 2001 1993 1994 1996 1999 2001

留余数法 int HF(int key)//模一个素数得到的余数 { return key%11; } 35 18 48 107 9 43 60 23 35 48 60 107 18 9 43

数字分析法 1939 1949 1969 1999 2001 以第三位定位 2001 1939 1949 1969 1999

int HF(char *key)//首末字母法,首末字母之和模101 { int len=strlen(key), hashf=0; if(len<=1)hashf=key[0]; else hashf=key[0]+key[len-1]; return hashf%101; } Beijing Shanghai Tianjin Chongqing Beijing ChongQing Shanghai Tianjin

int HF(char *key)//全字母法,所有字母的和模101 { int hashf=0; while(*key)hashf+=*key++; return hashf%101; } int HF(int key)//平方取中法 { key*=key; //key平方 key>>=11; //右移11位,去掉末尾11位 return key%1024;//去掉前面11位

处理冲突的方法 冲突collision: 不同的关键字得到同一个地址 1.开放定址法——线性探查法 23 35 48 17 60 29 38 40 23 35 48 60 17 29 38 40

开放定址法 23 35 48 60 17 29 38 40 查找成功平均查找次数 (1+1+1+1+1+4+3)/8=12/8=3/2

哈希表的装填因子α α=———————— 表中填入的纪录数 哈希表的长度 开放定址法的查找成功的平均查找次数 (1+1/(1-α))/2 查找不成功的平均查找次数 (1+1/(1-α)2)/2

开放定址法的缺点 容易引起“二次聚集” 发生冲突的点引起再一次冲突的可能性增加 使冲突点聚集 可以用再哈希法改进 即定义一个哈希函数序列 发生冲突的关键字用下一个哈希函数确定位置 避免聚集

链地址法 19 14 23 01 68 20 27 55 11 10 79 1 2 3 4 5 6 7 8 9 10 11 12 ∧ 01 14 27 79 ∧ 55 68 ∧ 19 84 ∧ 20 ∧ 10 23 ∧ 11 ∧

查找成功的平均查找次数 (1+2+3+4+1+2+1+2+1+1+2+1)/12 =21/12 α=12/12=1 1+1/2=1.5

链地址法 查找成功的平均查找次数 1+α/2 查找不成功的平均查找次数 α+e-α