【精品数据结构】检索结构.PPT

1、1 第第 8 章章 检索结构检索结构 2 8.1 概述概述 检索也称查找 检索是指在数据元素（记录）集合中求出满足某给定条件的 记录 数据元素（记录）中确定某特定数据字段的值与给定值相匹 配的记录 关键字字段（简称关键字） 检索成功与不成功 在某此问题中，当检索不成功时要插入不存在的数据 记录，或在某种情况下删除所找到的记录 8.1 .1 检索的概念检索的概念 3 检索算法（方法） : 按检索操作是否全部在内存进行： 内检索 外检索 按是否增删元素 静态检索 动态检索 8.1 .1 检索的概念检索的概念 4 检索算法（方法） : 按是否进行比较操作 比较式检索 非比较式检索 按关键字是否变化

2、原词检索 变词检索 8.1 .1 检索的概念检索的概念 5 为了提高检索效率，要专门为检索操作设置数 据结构 若按数据元素集合中元素间结构关系分类 线性结构（含线性链结构） 线性索引结构 树形结构 散列（杂凑）结构 8.1 .2 检索结构检索结构 6 按检索结构中数据元素是否会增加或减少分类 静态检索结构：操作中不增加或减少元素 动态检索结构：操作中可能增加元素或减少元素 8.1 .2 检索结构检索结构 7 检索算法的空间复杂度分析 在现有结构上进行检索的算法 实现检索算法而构造专门的数据结构的算法 检索算法的时间复杂度分析 以关键字的比较次数为主度量算法的时间复杂度 8.1 .3 检索算法的

3、时间与空间复杂检索算法的时间与空间复杂 度分析度分析 8 待查关键字的位置对算法本身而言是个随机量， 所以要综合测定算法的检索次数，需使用检索 次数的数学期望 将检索算法的检索次数的数学期望称为平均检 索长度ASL（Average Search Length） 对检索成功（关键字在表中）情况其计算式为： ASL= 8.1 .3 检索算法的时间与空间复杂检索算法的时间与空间复杂 度分析度分析 n i iic p 1 9 检索不成功的情况（关键字不在数据元素集 中），平均检索长度即为检索失败对应的比较 次数。 检索算法的总的平均检索长度应为检索成功与 失败两种情况的平均检索长度的数学期望。 8.1

4、 .3 检索算法的时间与空间复杂检索算法的时间与空间复杂 度分析度分析 10 判定树中每个结点表示被查数据元素集中的一个元素 （常用元素编号表示） 从树根到某一结点的路径，就表示检索该结点所经历 的过程，路径上各结点为检索中测试（比较）过的结 点 树结点的各个儿子，表示从该结点起下步检索的各选 择分枝 对无儿子结点，表示检索过程进行到它（即与它比较） 后，不能继续进行，应终止 8.1.4 检索算法的判定树检索算法的判定树 11 判定树的构造方法 若某检索算法A在数据元素集D上进行检索，则A对D的（检索） 判定树定义为： 若D=空，则A对D的判定树为空 若第1次是与元素i1比较（测试），则令i1

5、为判定树的根 若与i1比较后，下一步的检索操作是在数据集D1,.,Dm 之一中 进行（即可能在D1,.,Dm中任意一个上进行），则令算法A的 其余部分对D1,.,Dm的判定树（子树）为根结点i1的各子树， 这里，D1,.,Dm应为(D-i1)的一个划分。 （即D1.Dm=D- i1，且DjDk=空，jk，j, k1,.,m） 8.1.4 检索算法的判定树检索算法的判定树 12 123456789 （a）顺序查找判定树 5 27 1368 49 （b）折半查找判定树 5 27 1 3 68 4 9 （c）折半查找判定树(带外结点 ) 图 判定树 13 判定树的深度就表示检索算法的最大比较次数 树

6、的分枝数越大（即数据集分块越多），树深 度就越小 检索某结的比较次数，就是从树根到该结点的 路径上的结点个数 外结点外结点 增设了外结点的判定树为完全二叉树 8.1.4 检索算法的判定树检索算法的判定树 14 增设了外结点的判定树为完全二叉树 判定树的内路径内路径长定义为该树中各内结点的路径长 （从根到某结点的路径长定义为该结点的内径长）之和 外路径外路径长定义为树中各外结点的路径长之和 设I与E分别代表判定树的内与外路径长，则有 E=I+2n 这里n为内结点数目 8.1.4 检索算法的判定树检索算法的判定树 15 8.1.4 检索算法的判定树检索算法的判定树 实际中，各关键被查概率可能不同，

7、为此，引入加权 内外路径长 设wi与li分别为结点i的权值与在树中的层次数（即结点 i的路径长），则定义wi与li的积为i的加权路径长 加权内路径长I= 加权外路径长E= i n i il w 1 i n i il w 12 1 16 8.2 线性结构的检索线性结构的检索 属于静态检索 算法简单，但速度不高 主要用在对小型数据集的检索 一般的线性表有两种存贮结构：连续式与链式 对它们的检索，一般采用顺序搜索的方式称为顺 序查找 若元素已按关键字排序，则可采用更高效的检索法 折半查找 17 8.2.1 1 无序表的检索无序表的检索 (一)算法 long SeqSearch(int a, long

8、 n, int key) /*连续存储结构的线性表的顺序查找 a 输入量.一维数组，充当线性表，n为元素个数。 序号为0的位置不使用 key待查关键字 返回成功时返回key在表中的序号，否则返回0*/ long i; a0=key; /设置监视哨 i=n; while(ai!=key) i-; return i; 18 8.2.1 1 无序表的检索无序表的检索 (二)平均检索长度 检索成功时的平均检索长度 ASL=1/n(n-i+1)=1/n (n-i+1)=(n+1)/2=O(n) ASL总=q0(n+1)+q1(n+1)/2 若它们是等概率的 ASL总=1/2(n+1)+1/2(n+1)/

9、2=3/4(n+1) 19 8.2.1 1 无序表的检索无序表的检索 (三)线性链表的顺序检索 在链表中检索关键字值为key的结点的过程为： p=pHead; while (p!=NULL return p; /p为NULL时失败，否则p指向所查到的结点 20 8.2.2 2 有序表的折半检索有序表的折半检索 (一)折半检索算法 基本思想 先找出有序表中点位置上的元素（表空时无中点，表示检索 不成功），用待查关键字与它比较 若相等，则已查到，结束 否则，若它小于待查关键字，则下步在有序表的前半部（值 小于中点元素的部分）中按类似方法检索，若它的值大于待 查关键字，则在表的后半部按类似方法检索

10、21 8.2.2 2 有序表的折半检索有序表的折半检索 (一)折半检索算法 long BinSearch(int a, long n, int key) /*有序表（升序）的折半查找的非递归算发 a输入量，一维数组，充当有序线形表（连续结构），表中 元素按关键字key的升序排列，0号位置空置 key输入量，待查关键字 返回返回所找到的关键字的位置号，找不到时返回0 */ long low, high, mid; low=1;high=pL-last; 22 8.2.2 2 有序表的折半检索有序表的折半检索 (一)折半检索算法 while(low=high) mid=(low+high)/2;

11、/求中点 if (key=amid ) return mid; else if ( key high) return 0; /查不到 mid=(low+high)/2; if(key=amid) return mid; if(keylast+1); /*为索引表申请存储区*/ if(pII=null) return NULL; /*不能分配空间，失败返回*/ for(i=0;ilast;i+) pIIi.ip=1; /*索引表中记录指示器初始化，在下面的步骤中，pII充当计数器， pIIi 的值为关键字key大于或等于pL-roomi.key的记录数目加1*/ 8.3.2 2 稠密索引稠密索引

12、 32 for(i= pL-last;i0;i-) for(j=i-1;j0;j-) if(pL-roomj.keypL-roomi.key pIIj.ip+; else pIIi.ip+; return pII; /*CreateIndex*/ 33 8.3.3 3 分块索引（索引顺序检索）分块索引（索引顺序检索） (1)分块索引结构 分块有序是指：对任意两块B1和B2，若B1在逻辑上位 于B2之前，则B1中任一元素的关键字也在逻辑上位于 B2中任一元素之前 分块有序并不要求块内一定有序 每块对应一个索引项，每个索引项的结构为： 最大或最小关键字值块首地址或尾地址 34 8.3.3 3 分块

13、索引（索引顺序检索）分块索引（索引顺序检索） 8101210 049 1083570101180120140130280290210220 0 1 2 3 4 5 6 7 8 9 10 11 12 35 8.3.3 3 分块索引（索引顺序检索）分块索引（索引顺序检索） (1)分块索引结构 若数据集为一维数组data，则为它生成一个名为index 的索引表 的过程为（假定块长为BlockSize， 索引中存块内最小关键字与 块首元素下标,数据集长为N）： numBlock=N/BlockSize+N%BlockSize; /*求出块数目numBlock*/ posBlock=0; for(i=1

14、;i=numBlock;i+) indexi.ip=posBlock; indexi.key=dataposBlock; posBlock=posBlock+BlockSize; 36 8.3.3 3 分块索引（索引顺序检索）分块索引（索引顺序检索） (1)索引顺序检索 分两个步骤： 在索引表中确定关键字所在块； 在块中检索关键字。 分块检索的平均检索长度ASL应为 ASL=ASLi+ASLb = 1/bj+ 1/sj =(b+1)/2+(s+1)/2 =1/2(n/s+s)+1 37 8.4 树形检索结构（树目录）树形检索结构（树目录） 树中的每一结点是一个索引项 树结构的检索一般也快于线性

15、结构 树目录也常常用于驻留在外存上的数据集 树目录多用作动态结构 8.4.1 1 概述概述 38 二叉排序树是一种基本的树目录，由它可导出最优 （次优）二叉排序树与平衡二叉树。然后导出各种B树。 B树可用来实现高效的外部文件索引，广泛地应用于数 据库实现中 对树目录，由于检索就在树目录上进行，所以树目录 的检索判定树就是树目录本身 8.4.1 1 概述概述 39 (一)基本概念 二叉排序树（也称二叉检索树）是这样一种结点含关键 字的二叉树，它或为空二叉树，或满足下列性质： (i)若它的左子树不空， 则其左子树上所有结点的关键字 均分别小于它的根结点关键字； (ii)若它的右子树不空，则右子树上

16、所有结点的关键字均 分别大于它的根结点的关键字。 (iii)它的左右子树亦分别为二叉排序树。 8.4.2 2 二叉排序树二叉排序树 40 8.4.2 2 二叉排序树二叉排序树 50 30 80 1070 90 2055 ifelse for charr while case 图 二叉排序树 (a) (b) 41 (一)基本概念 前面讨论的折半检索与Fibonacii检索判定树均为二叉排序树 对二叉排序树进行中序遍历就会得到一个结点（关键字）的升序序 列 若给二叉排序树添加外结点，则外结点就可有具体的含意：某外结 点代表这么一个值的集合，该集合中的值的大小由开区间(a,b)确定， 这里a与b 分

17、别为该外结点在该二叉排序树（带外结点）的中序遍历 序列中的前趋结点与后继结点的关键字值 8.4.2 2 二叉排序树二叉排序树 42 (一)基本概念 C+ 描述 template struct TBinTreeNode TElem info; TElem *lc,*rc; 8.4.2 2 二叉排序树二叉排序树 43 (二)二叉排序树的检索 二叉树检索的递归程序为： TBinTreeNode *SearchBinSortTree(TBinTree *root, TElem key) /root为被检索的树的根指针 if (root=NULL) return NULL; if (root-info

18、= key) return root; if (key info) return SearchBinSortTree(roo-lc, key); return SearchBinSortTree(roo-rc, key); 8.4.2 2 二叉排序树二叉排序树 44 (二)二叉排序树的检索 二叉树检索的非递归程序为： TBinTreeNode *SearchBinSortTree2(TBinTree *root, TElem key) /root为被检索的树的根指针 TBinTreeNode *p; p = root; while (p!=NULL) if (key =p-info) retu

19、rn p; if (key info) p = p-lc; else p = p-rc; return p; 8.4.2 2 二叉排序树二叉排序树 45 (二)二叉排序树的检索 有时候，需要找到某关键字对应的结点的父亲，实现程序如下： TBinTreeNode *SearchFatheBinSortTree(TBinTree *root, TElem key, char isLeft=0; p0=NULL; p = root; 8.4.2 2 二叉排序树二叉排序树 46 (二)二叉排序树的检索 while (p!=NULL) if (key =p-info) return p0; p0 = p

20、; if (key info) p = p-lc; isLeft=1; else p = p-rc; isLeft=0; return p0; 8.4.2 2 二叉排序树二叉排序树 47 (三)二叉排序树的插入 TBinTreeNode *InsertBinTree(TBinTreeNode * 8.4.2 2 二叉排序树二叉排序树 48 (三)二叉排序树的插入 if (root=NULL) root=pNode; return NULL; p = SearchFatherBinSortTree(root, pNode-info, isLeft); if （isLeft）p-lc=pNode;

21、 else p-rc=pNode; return p; 8.4.2 2 二叉排序树二叉排序树 49 70 10 70 30 2080 10 70 30 2080 50 90 10 70 30 2080 50 90 10 70 30 2080 50 55 70 20 70 30 20 10 70 30 20 (a)初态 (b)插入70 (c)插入20 (d)插入30 (e)插入10 （空） (f)插入80 (g)插入50 (h)插入90 (i)插入55 图图 建立二叉排序过程示例 50 (三)二叉排序树的插入 利用该程序，也可根据原始数据生成二叉排序树： TBinTreeNode *Create

22、BinTree(int a, long n) /根据一维数组a中的原始数据，创建二叉排序树，返回其树根。 long k; TBinTreeNode *root, *p; char isLeft; root=NULL: for (k=0; kinfo=ak; InsertBinSortTree(root, p, isLeft) 8.4.2 2 二叉排序树二叉排序树 51 (三)二叉排序树的插入 显然，读入关键字的次序不同，所建二叉树的形式也不 同 8.4.2 2 二叉排序树二叉排序树 5 4 3 2 1 5 4 3 2 1 图图 插入次序不同，树结构也不同 52 (四)二叉排序树的删除 (1)

23、若p无左子树，则用p的右子树（若有的话）的根代替p if (p=flc) flc=prc; /p是f的左儿子 else frc=prc; return p; 8.4.2 2 二叉排序树二叉排序树 53 (四)二叉排序树的删除 (2) 若p有左子树，但p无右子树，则用p的左子树代替p （见图 8 0b）。 实现方法为： if (flc=p) flc=plc; else frc=plc; return p; 8.4.2 2 二叉排序树二叉排序树 54 p PR f p PR f (a)p无左子树 p PL f p PL f (b)p有左子树，但无右 子树 55 (四)二叉排序树的删除 (3) 若p

24、有左子树，也有右子树，则用p的中序前驱（中序 序列中p的直接前趋）q代替p，并将q的左子树转让给q的父 亲（注：q必无右子树） q=plc; r=p; /使r一直为q的父亲 while (q-rc!=NULL) r = q ; q=qrc; 8.4.2 2 二叉排序树二叉排序树 56 (四)二叉排序树的删除 /用q的左子树置换q / r等于p时，q就是p的左儿子，也是将q 的左子树挂接在p的左链 rrc=qlc; /下面用q置换p qlc=plc; qrc=prc; if (flc=p) flc=q; else frc=q; retrun p; 8.4.2 2 二叉排序树二叉排序树 57 f

25、Q PR S SL R RL QL 左图 (d)删除p的另一方法(用p左儿 置换p，p 的右子树挂接到p 的 直接前趋的右链) P PR f p S SL R RL r Q QL q Q PR f q S SL R RL r QL (c)p有左、右子树 图图 二叉排序树中删除p 58 typedef int tKey; /*关键字类型*/ typedef struct tSBTreeNode tKey key; /*关键字字段*/ /*这里可定义其他字段*/ struct TSBTreeNode *lclc, ,* *rc; /*左右儿子域*/ tSBTreeNode; tSBTreeNode

26、 *SBtreeSearch(tSBTreeNode *root,tKey key,tSBTreeNode *f) /*二叉排序树查找子程序（递归） root输入量，为待查二叉排序树的根指针 key输入量，待查关键字 *f指向被查接点的父亲，用树根调用此函数时，变量f为空 指针的地址 返回值树中第一个关键字等于key的结点的指针，若树中五 此结点，则返回nuul */ 59 if(root=NULL|root-key=key) return root; *f=root; if(keylc,key,f); else return SBTReeSearch(root-rc,key,f); /*SB

27、TreeSearch*/ 60 tSBTreeNode *SBTreeSearchPos(tSBTreeNode *root,tKey key,char *isl) /*在二叉排序树中查找插入位置（递归） root待查二叉排序树的根指针 key 输入量，待查关键字 *isl输入量，说明见下 返回值返回以*root为根的二叉排序树中的key应 出现的位置的父指针。若位置为他父亲懂得左儿子， 则置*isl为1，否则置为0 注：若树中已有与key相同的关键字结点，则认为key 小 于它们 */ 61 if(root=NULL) return NULL; /*为提高速度，此行可取消，但调用该 函数时不

28、能用空树调用（*root不为NULL）*/ if(roor-rc=NULL) *isl=1; return root; else return SBTreeSearchPos(root-lc,key,isl); else if(roo-rc=NULL) *isl=0; return root; else return SBTreeSearchPos(root-rc,key,isl); /*SBTreeSearchPos*/ 62 tSBTreeNode * SBTreeIns(tSBTreeNode *root,tKey,key) /* 在二叉排序树中插入一个关键字结点 *root输入量，指向

29、二叉排序树的根 key输入量，为待插入的关键字值 返回返回插入的结点的指针 */ tSBTreeNode *p,*q; char isl; q=(tSBTreeNode )malloc (sizeof(tSBTreeNode); /*申请一 个结点*/ q-key=key;q-lc=NULL,q-rc=NULL; 63 if(*root=NULL) *root=NULL; /*对空树，将新结点作为树根*/ else p=SBTreeSearchPos(*root,key, /* 找插入位置*/ if(isl) p-lc=q; else p-lc=NULL) *f=p-rc; else if(p

30、-rc=NULL) *f=p-lc; else /*p 的左右子树均不为空*/ q=p-lc; r=p; /*使r一直为q之父结点指针*/ while(q-rc!=NULL) /*找p的直接前驱q*/ r=q;q=q-rc; if(r!=p) r-rc=q-lc; /*用q的左子树代替q的位置*/ else /* r等于q时，q就是p 的左儿子，故应将q 的左子树挂接到p 的左链*/ r-lc=q-lc; 66 /*下面用q置换p*/ q-lc=p-lc; q-rc=p-rc; *f=q; /*if(p-rc=NULL)else*/ return p0; /*SBTreeDelNode*/ 6

31、7 tSBTreNode * SBTreeDelKey(tSBTreeNode *root,tKey,key) /*从二叉排序树中摘除指定关键字所在的第一个结点 *root指向二叉排序树的根 key待删除关键字值 返回被删除结点的指针 */ tSBTreeNode *p,*f; 68 if(key=*root-key) return SBTreeDelNode(*root,root);/*删根*/ else p=SBTreeSearch(*root,key, /*找key所在结点p及其父亲f*/ if(p=NULL) return NULL ; /*找不到key*/ if(p=f-lc) re

32、turn SBTreeDelNode(p, /*删p，用f的左链代管p子树的剩 余部分*/ else return SBTreeDelNode(p, /*SBTreeDelKey*/ 69 (五)二叉排序树的分析与最优二叉排序树 只需分析二叉排序树的检索算法 检索算法的效率与树的结构相关，而树结构又与关键字进 入树中的次序有关 8.4.2 2 二叉排序树二叉排序树 80 6085 2090 (b) 关键字输入次序为(80,60,20,85,90) 所对应的二叉排序树 20 60 80 85 90 (关键字输入次序为(20,60,80,85,90) 所对应的二叉排序树 70 (五)二叉排序树的分

33、析与最优二叉排序树 给定n个关键字与它们的n个检索概率值，能否存在一棵平 均检索长度（即加权内外路径长度，见8.1.4）最小的二 叉排序树呢？回答是肯定的。 这种树称为最优二叉排序树。 对于经常进行插入与删除的二叉排序，较好的选择是平衡 二叉排序树，它是二叉排序树与最优二叉排序树之间的一 种折衷。 8.4.2 2 二叉排序树二叉排序树 71 (一)概念 高度平衡二叉树（height Balanced binary tree）：或是一棵空树， 或是 具有下列性质的二叉树：它的左右子树均为平衡二叉树，且它们二者 的深度之差不超过1。在不至于产生混淆的情况下， 我们常称其高度平 衡二叉树为平衡二叉树

34、或平衡树。 平衡因子：二叉树中的结点的平衡因子定义为该结点的左子树的深度 与右子树深度之差。 平衡二叉排序树：若二叉排序树为平衡二叉树，则称为平衡二叉排序 树。在本节中，常以平衡二叉树称平衡二叉排序树。 8.4.3 3 平衡二叉排序树的性质平衡二叉排序树的性质 72 (二)若干性质 平衡树中任一结点的平衡因子均为-1,0,1三者之一，这是 显然的。因为任一结点的左右子树深度之差不超过1。 任一棵二叉排序树，都可以转化为一棵平衡二叉排序树。 （A e c oHBe ck , H c 1962）一棵具有n 个（内部）结 点的平衡二叉树，其高度h满足 log2(n+1)h1.4404log2(n+2

35、)-0.328 8.4.3 3 平衡二叉排序树的性质平衡二叉排序树的性质 73 (一)插入平衡调整 设p 是一棵平衡二叉树（p为根），则将某一结点插入它中后，有下列 情况 ( i)p的平衡因子为-1（p左重），结点插入到p的左子树，并使p左子树 升高，则p变为左超重（p平衡因子变为-2），此时需进行平衡调整。 (ii)p的平衡因子为1（p右重），结点插入到p的右子树，并使p 右子树 升高，则p变为右超重，需进行平衡调整。 (iii)其它情况均不需进行平衡调整。即p平衡因子0，或p左重，但结点 插入到p的右子树，或p右重，但结点插入到p左子树。 8.4.4 4 平衡二叉树局部平衡调整算法平衡二叉

36、树局部平衡调整算法 74 (一)插入平衡调整 8.4.4 4 平衡二叉树局部平衡调整算法平衡二叉树局部平衡调整算法 A BA B 图图 二叉排序树变换 左右：以B为轴顺时针旋转（父变左子之右子） 右左：以A为轴递时针旋转（父变右子之左子） 75 (a) -1/-2 P 0/-1 P1 h h-1 P1l P1r h-1 插入结点 P1r h-1或h-2 0 P 0/1 P h P1l Pr h-1 P1r h-1或h-2 LL 76 插入结点 P2r h-2或h-3 -1/-2 P 0/1或1/2 P1 h-1h-2 P2l Pr h-1 0/-1或-1/-2 P2 P1l h-1或h-2 P

37、2r P P1 P2l Pr P2 P1l P2r 1或2 P P2l PrP1l 0或1 P1 0 P2 LR (b) 77 1/2 P 0/1或1/2 P1 h h-1 P1r h-1 Pl P1l h-1或h-2 RR 0 P1 0/-1 P P1r P1lPl (c) 78 RL 插入结点 1/2 P Pl h-1 0/1或-1/-2 P1 0/-1或-1/-2 P1 P1r h-1或h-2 P2r h-2或h-3 h-1 h-2 P2l P1r P P1 P1l PlP2 P2r P2r 1或0或2 P1 P2l P1rPl 0 P P2 (d) 图图 在平衡二叉排序树中，插入接点后

38、的平衡调整（结点内标住的x/y表 示插 入前与插入后的平衡因子分别为x/y。图中，圆圈表示结点，方框表示 子树 79 （空树） 插入结点10 10 插入6 10 6 插入3 对子树10LL 10 6 3 插入结点2、5 10 6 3 52 插入4 10 63 5 24 对子树6LR 10 6 3 52 4 插入16 16 10 63 5 24 对6RR 16 10 6 3 5 24 插入结点18、20 80 16 10 6 3 5 24 18 20 对16RR插入17 18 16 10 6 3 5 24 20 18 16 10 6 3 5 24 20 17 对10RL 18 16 10 6 3

39、 5 24 2017 图图 平衡二叉树的插入与平衡（箭头所指结点为最小不平 衡子树的根） 81 (二)删除平衡调整 设p是一棵平衡二叉排序树（子树），则当p的某子树高度 被降低1后， 仅在下列情况下，p才需进行平衡调整： (i)p右轻（即左重），且p右子树高度被降低 (ii)p左轻（即右重），且p左子树高度被降低 8.4.4 4 平衡二叉树局部平衡调整算法平衡二叉树局部平衡调整算法 82 (a)LL型 LL -1/-2 P 0/-1 P1 h-1 h-2 Pr P1l h-1 P1r h-1或h-2 1或0 P1 -1或0 P P1l P1rPr 83 删除28 30 20 10 616264

40、0 48182228 217 45 30 20 10 6162640 481822 217 45 8 26 30 18 10 2240 2145 对26进行LL 删除4、6、16、20 26 30 20 10 6162240 481821 7 45 84 删除45 8 26 30 18 10 2240 21 删除8 26 30 18 10 2240 21 21 10 30 22 18 2640 对18进行RL 图图 平衡二叉排序树的删除平衡调整 85 1970年R.Bayer和E.Mccrerght提出了一种适合用于外查找的树，它是 一种平衡的多叉树，其特点是插入、删除时易于平衡，外查找效 率

41、高，适合于组织磁盘文件的动态索引结构，这就是我们将要讨 论的B-树。 1)B-树的定义 一棵m阶的B-树满，或为空树，或为满足下列条件的m叉树： (1)每个结点至多有m棵子树； (2)若根结点不是叶结点，则至少有2棵子树； (3)除根之外的所有非终端结点至少有m/2棵子树； 8.5 B-树 86 (4)所有的非终端结点所包含的信息： （n, A0, K1, A1, K2, A2, , KN, AN) 其中Ki(i=1,.,n)为关键字，且Ki=Ki+1; Ai(i=0, .,n)为指向子树根结点的指针，且指针Ai-1的指子树中所有结点的 关键字昀小于Ki(I=1,.,n)，An的指子树中所有结

42、点的关键字均大于Kn， n(m/2-1=nkeynum; i = Search ( p, K); /在p-key1.keynum中查找，i使得：p-keyi=Kkeyi+1 if ( i0 /找到待查关键字 else ( q = p; p = p-ptri; if ( found ) return ( p, i, 1);/查找成功 else return ( q, i, 0);/查找不成功，返回K的插入位置信息 / SearchBTree 90 B-树的树的插入和删除插入和删除 B- 树的插入 首先在最低层的某个非终端结点中添加一个关键字，若该结点的 关键字个数不超过m-1，则插入完成，否则要

43、产生结点的“分 裂”。 B- 树的删除 首先应找到该关键字所在结点，并从中删除之，若该结点为最下 层的非终端结点，且其中的关键字数目不少于m/2，则删除完成， 否则要进行“合并” 结点的操作。 91 45 53 9024 3 12375061 70100 bt b cdfg h a e (a) 一棵 2-3树 45 53 9024 3 1230 375061 70100 bt b cdfg h a e (b) 插入30之后 92 45 53 9024 3 1226 30 375061 70100 bt b cdfg h a e (c) 45 53 9024 30 3 12375061 7010

44、0 bt b cdfgh a e (d) 插入26之后 26 d 93 (e) 45 70 53 24 30 3 12375061100 bt b cdfgh a e 插入85之后 26 45 53 9024 30 3 12375061 70 85100 bt b cdfg h a e 26 45 53 70 9024 30 3 12375061100 bt b cdfg h a e 26 (g) 85 gg 90 85 g d d d (f) 94 (h) 45 70 7 24 30 337 bt b cd a 26 24 45 70 7 37 bt b d a 26 d d (i) 12

45、c 53 5061100 fgh 90 85 g 30 b 53 5061100 fgh 90 85 g e e ee 3 c 12 c 95 70 7 37 bt b d a 26 d 30 b 53 5061100 fgh 90 85 g e e c 12 c 插入7之后 24 a 45 m 3 96 Status InsertBTree ( Btree *T, KeyType K, Btree q, int i) /在m阶B树T上结点*q的keyi与keyi+1之间插入关键字K。 /若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。 x = K; ap = NULL;

46、finished = FALSE; while ( q /将x和ap分别插入到q-keyi+1和q-ptri+1 if ( q-keynum keys; /将q-keys+1.m, q-ptrs.m和q-recptrs+1.m移入新结点 *ap q = q-parent; if ( q) i = Search (q, x); /在双亲结点*q中查找x的插入位置 /else /while if ( !finished ) /T是空树(参数q的初值为NULL)或者根结点已分裂为结点*q和*ap NewRoot (T, q, x, ap); /生成含信息（T,x,ap)的新根结点*T，原T和ap为子

47、树指针 97 B树的删除过程树的删除过程 45 53 9024 3375061 70100 bt b cdfg h a e 45 61 9024 3375370100 bt b cdfg h a e 98 B树的删除树的删除 45 9024 33761 70100 bt b cdg h a e 45 90 1003 24 bt c a h 61 70 g 99 B+树是应文件系统所需的一种B- 树的变型树。m阶的B+树和m阶的B-树的 差别在于： （1）有n棵子树的结点中含有n个关键字； （2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录 的指针，且叶子结点本身依关键字的大小

48、自小而大顺序链接。 （3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点） 中的最大（或最小）关键字。 B+ + 树树 100 B+ + 树树 59 97 15 44 59 21 37 44 72 97 63 72 85 91 9751 5910 15 root sqt 101 通常在B+树上有两个头指针，一个指向根结点，另一个指向关键字最小的 叶子结点。 B+树的查找运算有两种： 从最小关键字起顺序查找 从根结点开始，进行随机查找。 在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。 在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向 下直到叶子结点。

49、 B+ + 树树 102 8.6 哈希表 9.4.1 哈希表（Hash Table,散列表) 散列(Hashing)基本思想：以结点的关键字K为自变量，通过 一个确定的函数关系f ，计算出对应的函数值f(K)，把这个值解 释为结点的存储地址，将结点存入f(K)所指的存储位置上。查找 时再根据要查找的关键字用同样的函数计算地址，然后到相应的 单元里去取要找的结点。因此散列法又称关键字-地址转换法。用 散列法存储的线性表叫散列表(Hash Table)，上述的函数f称为散 列函数，f(K)称为散列地址。 103 编号 地区名 总人口 汉族 回族 . C 1.30 散列函数： （1）f(key) =

50、 key , key 是编号 （2）f(key)=关键字中第一个字母在字母表中的编号。 Key 为地区名的拼音。 （3）f(key)=关键字中第一个和最后一个字母在字母表中 的序号之和，此和若比30大，则减去30。Key的含义同 上。 104 (1)若散列函数是一对一的函数，则在查找时，只需根据散列函数对给定 值进行某种运算，即可得到待查结点的存储位置； (2)设散列表的空间大小为m，填入表中的结点数是n，则称n/m为散列表的 装填因子。实用中常取=0.65为宜。 (3)散列函数的选取原则是：运算尽量简单；函数的值域必须在表长的范 围内；尽可能使关键字不同时，其散列函数值亦不相同。 (4)若某

51、个散列函数H对于不相等的关键字Key1和Key2得到相同的散列地址 (即H(Key1)=H(Key2)，则该现象称为冲突(Collision)，而发生冲突的这 两个关键字则称为H的同义词(Synonym)。 散列法查找必须研究下面的两个主要问题： （1）选择一个计算简单且冲突尽量少的“均匀”的散列函数 （2）一个解决冲突的方法，即寻找一种方法存储产生冲突的同义词。 哈希表的讨论哈希表的讨论 105 9.4.1 散列函数的构造方法散列函数的构造方法 1）数字选择法数字选择法:若事先知道关键字集合，且关键字的位数比散列表的地址位 数多，则可选取数字分布比较均匀的若干位作为散列地址。 2）平方取中法：平方取中法：即先通过求关键字的平方值扩大差别，然后再取中间的几 位或其组合作为散列地址。因为一个乘积的中