《静态查找表二叉排序树平衡二叉树AVL树小结B树哈希表培训资料》由会员分享，可在线阅读，更多相关《静态查找表二叉排序树平衡二叉树AVL树小结B树哈希表培训资料（104页珍藏版）》请在金锄头文库上搜索。
1、静态查找表 二叉排序树 平衡二叉树（AVL树） 小结 B树 哈希表,第9章 查找,查找(Search)的概念,静态查找表,查找：就是在数据集合中寻找满足某种条 件的数据对象。 查找表：是由同一类型的数据元素(或记录) 组成的数据集合。 查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。 查找不成功，或查找失败。作为结果， 报告一些信息，如失败标志、失败位置等。,关键字：数据元素中某个数据项的值，用以 标识一个数据元素。 主关键字：可唯一地标识一个数据元素的关 键字。 次关键字：用以识别若干记录的关键字。 使用基于主关键字的查找，查找结果应是 唯一的。 静态查找表（p214） 动态
2、查找表,9.1 静态查找表,基本操作： Create( /遍历查找表,9.1.1顺序表的查找 (Sequential Search),所谓顺序查找，又称线性查找，主要用于在线性结构中进 行查找。 存储结构： typedef struct ElemType *elem; int length; SSTable; 查找过程：从表中最后一个元素开始，顺序用各元素的关键字与给定值x进行比较，若找到与其值相等的元素，则查找成功，给出该元素在表中的位置；否则，若直到第一个记录仍未找到关键字与x相等的对象，则查找失败。,算法9.1 （p217） Search_Seq(SSTable ST, KeyType
3、key) /顺序查找的算法，0号元素为监视哨 int i； ST.elem0.key=key; for (i=ST.length; !EQ(ST.elemi.key,key);-i); return i; ,顺序查找的平均查找长度,设查找第 i 个元素的概率为 pi，查找到第 i 个元素所需比较次数为 ci，则查找成功的平均查找长度:,在顺序查找情形，ci = n-i +1, i = 1, , n，因此,在等概率情形，pi = 1/n, i = 0, 1, , n-1。,9.1.2 有序表的查找,折半查找：先求位于查找区间正中的对象的下标mid，用其关键字与给定值x比较: Elementmid
4、.getKey( ) = x，查找成功； Elementmid.getKey( ) x，把查找区间缩小到表的前半部分，再继续进行对分查找； Elementmid.getKey( ) x，把查找区间缩小到表的后半部分，再继续进行对分查找。 每比较一次，查找区间缩小一半。如果查找区间已缩小到一个对象，仍未找到想要查找的对象，则查找失败。,9.1.2 有序表的查找,折半查找： （1）mid= (low+high)/2 （2）比较 ST.elemmid.key = = key? 如果 ST.elemmid.key = = key，则查找成功， 返回mid值 如果 ST.elemmid.key key，
5、则置high=mid-1 如果 ST.elemmid.key high时，表明查找不成功，查找结束。,查找成功的例子 查找失败的例子,算法9.2(p220) int Search_Bin(SSTable ST,KeyType key) /折半查找 int low,high,mid; low = 1; high=ST.length; while (low high) mid = (low+high)/2; if (EQ(key,ST.elemmid.key) return mid; else if (LT(key,ST.elemmid.key) high=mid-1; else low=mid+
6、1; return 0; ,查找成功的情形 查找不成功的情形,从有序表构造出的二叉查找树(判定树),若设 n = 2h-1，则描述对分查找的二叉查找树是高度为 h 的满二叉树。2h = n+1, h = log2(n+1)。 第1层结点有1个，查找第1层结点要比较1次；第2层结点有2个，查找第2层结点要比较2次；，,1）分块有序（升序或降序） 第I块中的最大（小）值小（大）于第i+1块中的最（大）小值 2）查找 （1）先查索引表折半查找 （2）再查顺序表顺序查找 块间有序，块内无序 typedef struct int key; Eletype; typedef struct Elemtype
7、 *elem; int length; SSTable; # define BLOCK_NUM 3,9.1.2 索引顺序表的查找分块查找,Typedef struct int Maxkey; int next; BLKNode,ITBLOCK_Num; int Search_Bin(SSTable ST,int key) /折半查找 int i,p,low,high,mid; printf(“Create index table,Input Maxkey ,i=ITlow.next; ST.ele0.key = key; If(low!=BLOCK_NUM) p=ITlow+1.next; e
8、lse p=ST.length+1; while(ST.elemi%p.key != key ) i+ ; return( i%p ) ; 性能分析： ASL（bls）=Lb+Lw=(b+1/)2 +(s+1)/2 =(b+s+2)/2 =(n/s+s)/2+1 b 分块的个数 b=n/2 s 每块中的记录个数 n 记录的总个数 Lb 确定所在的块 Lw 块内查找,可以用归纳法证明,这样,第 i (1 i h) 层结点有 2i -1个，查找第 i 层结点要比较 i次，。假定每个结点的查找概率相等，即pi = 1/n，则查找成功的平均查找长度为,9.2 动态查找表,表结构本身是在查找过程中动态生
9、成的。 基本操作： InitDSTable( /遍历查找表,定义 二叉排序树（二叉查找树） 或者是一棵空树，或者是具有下列性质的二叉树： 每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同。 左子树(若非空)上所有结点的关键字都小于根结点的关键字。 右子树(若非空)上所有结点的关键字都大于根结点的关键字。 左子树和右子树也是二叉排序树。,9.2.1二叉排序树 ( Binary Sort Tree ),如果对一棵二叉排序树进行中序遍历，可以按从小到大的顺序，将各结点关键字排列起来。,几个二叉排序树的例子,二叉排序树上的构建如何构造二叉排序树,1) 构造过程： 从空树出发，依
10、次插入R1 Rn各数据值： （1）如果二叉排序树是空树，则插入结点就是 二叉排序树的根结点； （2）如果二叉排序树是非空的，则插入值与 跟结点比较，若小于根结点的值，就插 入到左子树中去；否则插入到右子树中。 示例： 45，24，53，12，22，90 ,2) 二叉排序树的数据类型描述,typedef struct int key; ElemType; typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode, * BiTree;,3) 二叉排序树上插入结点的算法,（1）在二叉排序树上插入一个结点
11、的算法； （2）依次输入一组数据元素，并插入到二叉排 序树中的算法,（1）将指针S所指的结点插入到根结点指针为T的 二叉排序树中的算法,void Insert_BST( BiTree ,（2）输入一组数据元素的序列，构造二叉排序树 的算法,void Creat BST( BiTree ,4) 二叉排序树上的查找（动态查找）,int Searh_BST( BiTree T, int key ) BiTree p, q, S, p = T; while ( p ) if ( p-data.key = key ) return(1); else if ( p-data.key key) q=p; p
12、=p-lchild; else q=p; p=p-rchild; S = (BiTNode *) malloc(sizeof(BitNode); S-data.key = key; S-lchild=S-rchild=NULL; if (!T) T=S; else if ( q-data.key key ) q-lchild=S; else q-rchild=S; return(0); 说明：（1）正常情况下，返回0是未找到，但实际上已经插入； （2）也可以用return返回一个自己定义的标志值。,要求：删除一个结点后，仍然保持二叉排序树 的有序性 删除结点的算法： （1）确定被删除结点： A
13、. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 （2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法。,5) 二叉排序树的删除,删除二叉排序树的根结点的算法 （1） 根结点有左右子树的情况下，选择根结点的 左子树中的最大结点为新的根结点；/或者是 右子树中的最小结点为新的根结点； * 最大结点中序遍历 （2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点,删除二叉排序树中一般结点的算法 （1） 若被删除结点P有左、右子树，则
14、按照中序遍历找其 左子树中的最大结点，以此最大结点的值代替P结点 的值，然后删除此最大结点（如同删除根结点） （2）若被删除结点P没有左子树，则把结点P的右子树的 全部挂接在P的双亲上，且位置是P在其双亲中原来 的位置 （3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置 删除二叉排序树中叶子结点的算法 只需将其双亲结点指向它的指针清零，再释放它即可,int Delete_BST( BiTree return(0) ,删除二叉排序树中结点的算法 寻找被删除的结点,void delNode ( BiTree ,删除二叉排序树中结点的算法 删
15、除找到的结点,二叉排序树上的查找,在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。 假设想要在二叉排序树中查找关键字为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键字进行比较： 如果给定值等于根结点的关键字，则查找成功。 如果给定值小于根结点的关键字，则继续递归查找根结点的左子树； 否则。递归查找根结点的右子树。,int SearchBST(BiTree T,KeyType key,BiTree f,BiTree ,二叉排序树的查找 插入新结点88,每次结点的插入，都要从根结点出发查找插入位置，然后把新结点作为叶结点插入。,二叉排序树的插入,为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。 在插入之前，先使用查找算法在树中检查要插入元素有还是没有。 查找成功: 树中已有这个元素，不再插入。 查找不成功: 树中原来没有关键字等于给定值的结点，把新元素加到查找操作停止的地方。,int InsertBST(BiTree ,输入数据，建立二叉排序树的过程,输入数据序列 53, 78, 65, 17, 87, 09, 81, 45, 23 ,同样 3 个数据 1, 2, 3 ，输入顺序不同，建立起来的二叉排序树的形态也不同。这
