第八章查找第八章查找第八章查找“学生”表格8.1查找的基本概念关键字类型说明typedeffloatKeyType；//实型typedefintKeyType；//整型typedefchar*KeyType；//字符串型数据元素类型定义typedefstruct｛KeyTypekey；//关键字域……；//其它域｝ElemType；8.2静态查找表顺序查找算法（P217算法9.1）8.2.1无序表的查找8.2.2有序表的查找8.2.2有序表的查找8.2.2有序表的查找折半查找算法（P220算法9.2）8.2.2有序表的查找8.2.2有序表的查找8.2.2有序表的查找8.2.3索引顺序表的查找8.2.3索引顺序表的查找8.2.3索引顺序表的查找8.3动态查找表8.3.1二叉排序树二叉排序的查找（P228算法9.5（a））8.3.1二叉排序树8.3.1二叉排序树8.3.1二叉排序树二叉排序的查找（P228算法9.5（b））二叉排序的插入（P228算法9.6）输入数据，建立二叉排序树的过程8.3.1二叉排序树8.3.1二叉排序树8.3.1二叉排序树8.3.1二叉排序树删除结点80，令*p的中序直接后继H（或直接前驱）的值替代*p的值，然后再从二叉排序树中删除*p的中序直接后继H。删除结点80，令*p的右子树为*f的右子树，*p的左子树为H的左子树。二叉排序树删除算法（P230算法9.7）二叉排序树删除算法（P230算法9.8）8.3.1二叉排序树8.3.1二叉排序树8.3.2平衡二叉树8.3.2平衡二叉树8.3.2平衡二叉树平衡树的生成过程8.3.2平衡二叉树8.3.2平衡二叉树8.3.2平衡二叉树－1B8.3.2平衡二叉树B顺时针向右8.3.2平衡二叉树8.3.2平衡二叉树8.3.2平衡二叉树8.3.3B-树和B+树8.3.3B-树和B+树8.3.3B-树和B+树3.B-树的查找算法ResultSearchBTree(BtreeT,KeyTypeK){p=T;q=NULL;found=FALSE;i=0;while(p&&!found){n=p->keynum;i=Search(p,k);//在p->key[1..n]中查找//使得p->key[i]≤K≤p->key[i+1]if(i>0&&p->key[i]==k)found=TRUE;else{q=p;p=p->ptr[i];}}if(found)return(p,i,l);elsereturn(q,i,0);}4.B-树查找分析B-树上进行查找包含两种基本操作:（1）在B-树中找结点；（2）在指定结点中找关键字。由于B-树通常存储在磁盘上，则前一查找操作是在磁盘上进行的，而在指定结点中找关键字是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中的信息读入内存，然后再利用顺序查找或折半查找查询等于k的关键字。显然，在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数、即待查关键字所在结点在B-树上的层次数，是决定B-树查找效率的首要因素。8.3.3B-树和B+树45在图（b）上插入关键字26（2）删除操作首先在B-中找到要删除的关键字，然后进行删除操作。在最下层的非终端结点中删除一个关键字有以下三种情况：若关键字所在的结点为最下层的非终端结点，且其中的关键字个数不少于「m/2ר，则删除完成，否则需要进行结点的合并。若被删除关键字结点中关键字个数等于「m/2ך-1，而其相邻的右兄弟（或左兄弟）结点中的关键字个数大于「m/2ך-1，则应将其兄弟结点中的最小（或最大）关键字上移至其双亲结点中，而将双亲结点中小于（或大于）且紧靠该该上移关键字的关键字下移至被删除关键字中。若被删除关键字结点和其相邻的兄弟结点中的关键字个数都等于「m/2ך-1。假设该结点有右兄弟，且其指针由其双亲结点中的Ai指针指示，则删除该关键字后，它所在结点中剩余的关键字和指针与其双亲结点中的关键字Ki一起合并到其兄弟结点中（若没有右兄弟，则合并到左兄弟结点中）。若导致其双亲结点的关键字个数小于「m/2ך-1，则需要继续合并。45删除50第三种情况：8.3.3.2B+树1.B+树的定义B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树是一棵的m路平衡索引树。m阶的B+树和m阶的B-树的差异在于：（1）有n棵子树的结点中含有n个关键字；（2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接；（3）所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。8.3.3B-树和B+树2.B+树的查找