2009/12/29 9.1.4索引顺序表的查找(2) 9.1.4索引顺序表的查找(3) ■分块查找（索引顺序查找） ,分块查找过程 ·常引顺序表表示，分块有序，常引表是有序表 ·先确定待查记录所在的块（子表）一一有序表 。索引项是（最大关健字，指针项） 可以用折半查找或顺序查找 。再在块中查找 序表，，。，。。0 只能是顺序查找 170821191431332254052617846. ASL =L +L. 引表2404057810☐ L为查找索引表确定所在块的平均查找长度 L为在块中查找元素的平均查找长度 3103 32/103 圆 9.2动态查找表 9.2动态查找表-ADT(1) ■抽象数据类型定义 。特点：表结构本身是在查找过程中动态生成的 .ADT DynamicSearchTable ■9.2.1二叉排序树和平衡二叉撇 败据对象D:具有相同特性的数据元素的桌合。 败据关系R:数据元素同属一个集合。 ■9.2.2B-搬和B±樾 基本操作P: InitDSTable(&DT) ▣9.2.3键树 操作结果：构造一个空的动态查找表DT DestroyDSTable(&DT) 始条件：动态查找表DT存在 燥作结界：销毁表DT. 33/103 34/103 图 SearchDSTable(DT,key) 潮榨结共；动态者找表D工存在，k为和关牛类相同的给定慎 素的值或在表中的位置，否则为空”· 9.2.1二叉排序树：定义 InsertDSTable(&DT,e) 初始条件，动态查找表DT存在，e为特插入的数据元豪 ·二叉排序树（二叉查找树） 操作结果：着DT中不存在其关字于e.key的据元素，入e到 DT. Binary Sort/Search Tree DeleteDSTable(&DT,key) ,定义（递归）：或者是一棵空树，或者是具有如 初始保件：动老查找表DT存在，key为和关德字类型相同的给定值 下特性的二叉树： 操作结果：若DT中存在其关塘李等于key的兼据元素，则除之 ,若它的左子树不空，则左子树上所直结点的值均小 TraverseDSTable(DT,Visit()) 初始条件：静老查找表DT存在，Vsit是对元素操作的应用西数. 王根结点的值： 操作结果：找某种次序对DT的年个元素调用西业Vs)一次且仅一次。 ,若它的右子树不空，则右子树上所直结点的值均太 一且Vst()失败，则操作失败 王根结点的值： }ADT DynamicSearchTable ,它的左、右子树也分别是二叉样序树。 合 36/103 圄 6
2009/12/29 6 9.1.4 索引顺序表的查找(2) 分块查找(索引顺序查找) 索引顺序表表示，分块有序，索引表是有序表 索引项是(最大关键字, 指针项) 31/103 ( , 0 1 2 3 4 5 6 7 8 9 10 11 12 13 …… 17 08 21 19 14 31 33 22 25 40 52 61 78 46 …… 21 0 40 5 78 10 …… 顺序表 索引表 9.1.4 索引顺序表的查找(3) 分块查找过程 先确定待查记录所在的块(子表)－－有序表 可以用折半查找或顺序查找 32/103 再在块中查找 只能是顺序查找 为在块中查找元素的平 均查找长度 为查找索引表确定所在 块的平均查找长度 w b bs b w L L ASL L L 9.2 动态查找表 抽象数据类型定义 9.2.1 二叉排序树和平衡二叉树 33/103 叉排序树和平衡 叉树 9.2.2 B-树和B+树 9.2.3 键树 9.2 动态查找表-ADT(1) 特点：表结构本身是在查找过程中动态生成的 ADT DynamicSearchTable{ 数据对象D:具有相同特性的数据元素的集合。 34/103 数据关系R:数据元素同属一个集合。 基本操作P: InitDSTable(&DT) 操作结果：构造一个空的动态查找表DT. DestroyDSTable(&DT) 初始条件：动态查找表DT存在. 操作结果：销毁表DT. SearchDSTable(DT, key) 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值. 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元 素的值或在表中的位置，否则为“空”. InsertDSTable(&DT, e) 初始条件：动态查找表DT存在，e为待插入的数据元素. 操作结果：若DT中不存在其关键字等于e.key的数据元素，则插入e到 DT. DeleteDSTable(&DT key) 35/103 DeleteDSTable(&DT, key) 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值. 操作结果：若DT中存在其关键字等于key的数据元素，则删除之. TraverseDSTable(DT,Visit()) 初始条件：静态查找表DT存在,Visit是对元素操作的应用函数. 操作结果：按某种次序对DT的每个元素调用函数Visit()一次且仅一次。 一旦Visit()失败，则操作失败. } ADT DynamicSearchTable 9.2.1 -二叉排序树:定义 二叉排序树(二叉查找树) Binary Sort/Search Tree 定义(递归) 或者是一棵空树 或者是具有如 36/103 定义(递归)：或者是一棵空树，或者是具有如 下特性的二叉树： 若它的左子树不空，则左子树上所有结点的值均小 于根结点的值； 若它的右子树不空，则右子树上所有结点的值均大 于根结点的值； 它的左、右子树也分别是二叉排序树
2009/12/29 9.2.1-二叉排序树：查找举例 9.2.1-二叉排序树：查找算法 ·查找算法（算法9.5(a)) 基于二叉树先序遭历 BiTree SearchBST(BiTree T,KeyType key){ 查找key=70? ∥在根指针T所指二叉排序树中查找某关键字等于 23 66 ∥ky的数据元素，若查找成功，则返回指向该数据 查找key=28? 元素结点的指针，否则返回空指针 097099 f(TEQ(key,T->data.key》return(T:∥查找结束 else if(LT(key,T->data.key)) return(SearchBST(T->lchild,key)); else return(SearchBST(T->rchild,key)); 371103 备 38/103 圄 9.2.1-二叉排序树：插入 9.2.1-二叉排序树：改进的查找算法 二叉排序树的插入 。改写查找算法为算法9.5(b): 。新插入的结点一定是一个新深加的 Status SearchBST(BiTree T.KeyType key,BiTree f.BiTree &p){ 叶子结点并且是查找不成功时查找 33 ∥若查找成功，则指针指南试最调元素结点，并运图 略径上访问的最后一个结点的左孩 ∥T取UE,否则指针推向查找路径上访间的最后一个结点并 子或右盛子结点 运回FALSE,指针指向T的京亲：其初地调用值为NUL山 ,示例：从空树出发，待插的关镀字 if (T)(p-f;return FALSE; ebse if (EQ(key,T->data.key))(p-T;return TRUE:} 序列为33,44,23,46,12,37 else if (LT(key,T->data.key)) 中序遗历二叉排序树可得到一个关键字的有序序列。 return SearehBST(Tlchild,key.T,p): 该例中，中序遗历结果为：12,23,33,37,44,46 else return SearchBST(Trchild,key,T,p): 39/103 40/103 图 9.2.1-二叉排序树：插入算法 9.2.1-二叉排序树：删除1 ·二叉排序树的擂入算法9.6： ■二叉排序树的副除 Status Ins ertBST(BiTree &T,ElemType e) ∥当二又排序刺T中不存在关辅字等于：key的兼烟元素时，插 假设被副结点为°p,其双亲结点为*， 入e并返回IRLE:否则延回FAL.SE 。*p为叶子结点：副去*p,并修政f的孩子域。 if(SearchBST(T,e.key,NLp){H查找不成功 ,p只有左子树P或只有右子树Pk:令P或P.直接成 s-(BiTree)malloc(sizeof(BiTNode)): data-e;slchild -s->rchild-NULL: 为的子树 (p)T∥被结点为新的视结点 33 else if(LT(e.key,p->data.key))p>lchild-s p>rchild一s∥被插结点为右孩子 return TRUE; }else return FALSE:∥树中已有关字湘同的点，不再入 12 41/103 42/103 圄 7
2009/12/29 7 9.2.1 -二叉排序树:查找举例 45 23 66 查找key=70? 37/103 4 34 48 30 44 87 70 99 36 69 查找key=28? 9.2.1 -二叉排序树:查找算法 查找算法( 算法9.5(a) ) ——基于二叉树先序遍历 BiTree SearchBST(BiTree T, KeyType key){ // 在根指针T所指二叉排序树中查找某关键字等于 38/103 // key的数据元素，若查找成功，则返回指向该数据 //元素结点的指针，否则返回空指针 if (!T || EQ(key, T->data.key)) return (T); // 查找结束 else if (LT(key, T->data.key) ) return(SearchBST(T->lchild, key)); else return(SearchBST(T->rchild, key)); } 9.2.1 -二叉排序树: 插入 二叉排序树的插入 新插入的结点一定是一个新添加的 叶子结点,并且是查找不成功时查找 33 39/103 路径上访问的最后一个结点的左孩 子或右孩子结点. 示例：从空树出发，待插的关键字 序列为33,44,23,46,12,37 23 44 12 37 46 中序遍历二叉排序树可得到一个关键字的有序序列。 该例中，中序遍历结果为：12, 23, 33, 37, 44, 46 9.2.1 -二叉排序树:改进的查找算法 改写查找算法为算法9.5(b)： Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){ // 若查找成功，则指针p指向该数据元素结点，并返回 // TRUE 否则指针 指向查找路径上访问的最后 个结点并 40/103 // TRUE；否则指针p指向查找路径上访问的最后一个结点并 //返回FALSE。指针f 指向T的双亲，其初始调用值为NULL if (!T) { p=f; return FALSE;} else if ( EQ(key, T->data.key)) { p=T; return TRUE; } else if ( LT(key, T->data.key) ) return SearchBST(T->lchild, key, T, p); else return SearchBST(T->rchild, key, T, p); } 9.2.1 -二叉排序树:插入算法 二叉排序树的插入算法9.6： Status InsertBST(BiTree &T, ElemType e){ // 当二叉排序树T中不存在关键字等于e.key的数据元素时，插 //入e 并返回TRUE；否则返回FALSE 41/103 if (!SearchBST(T, e.key, NULL, p)) { // 查找不成功 s = (BiTree)malloc(sizeof(BiTNode)); s->data = e; s->lchild = s->rchild = NULL; if ( !p) T=s; // 被插结点*s为新的根结点 else if ( LT(e.key, p->data.key)) p->lchild=s; else p->rchild = s; // 被插结点*s为右孩子 return TRUE; } else return FALSE; // 树中已有关键字相同的结点，不再插入 } 9.2.1 -二叉排序树:删除1 二叉排序树的删除 假设被删结点为*p，其双亲结点为*f， *p为叶子结点：删去*p，并修改*f 的孩子域。 42/103 p p *p只有左子树PL或只有右子树PR：令PL或PR直接成 为*f 的子树 33 23 44 12 37 46 33 23 44 12 46 45 46 45 46