數(shù)據(jù)結(jié)構(gòu)查找全套PPT

數(shù)據(jù)結(jié)構(gòu)查找數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第1頁。優(yōu)選數(shù)據(jù)結(jié)構(gòu)查找Ppt數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第2頁。術(shù)語：查找(檢索)——根據(jù)給定的某個值，在表中確定一個關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素關(guān)鍵字——是記錄某個數(shù)據(jù)項的值，它可以唯一標識一個記錄。次關(guān)鍵字——不能唯一的確定一個記錄，但能確定表的一個子表。子表的元素個數(shù)應(yīng)遠少于表中元素數(shù)。為簡化問題，將表中元素看成簡單的整型數(shù)據(jù)，理解為關(guān)鍵字部分。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第3頁。8.1靜態(tài)查找表

1、順序表的順序查找

應(yīng)用范圍：順序表或線性鏈表表示的表，表內(nèi)元素之間無序。查找過程：從表的一端開始逐個進行記錄的關(guān)鍵字和給定值的比較。

search(st,key，n)//在有n個數(shù)據(jù)的表st中找key{i=n-1;while(i>=0&&st[i]!=key)i--;if(i<0)return-1;//查找不成功返回-1

elsereturni;//查找成功返回下標號}算法主要時間在循環(huán)，為減少判定，n個數(shù)據(jù)用容量為n+1的一維數(shù)組表示。st[1]到st[n]存儲數(shù)據(jù)，st[0]作為監(jiān)視哨

search1(st,key，n){st[0]=key;i=n;while(st[i]!=key)i--;returni;//查找返回序號，0為不成功}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第4頁。順序查找的平均時間為表長的一半。2、順序有序表的查找———二分（折半）查找查找過程：每次將待查記錄所在區(qū)間縮小一半適用條件：采用順序存儲結(jié)構(gòu)的有序表算法實現(xiàn)設(shè)表長為n，low、high和mid分別指向待查元素所在區(qū)間的上界、下界和中點,k為給定的待查值初始時，令low=1,high=n,mid=(low+high)/2讓k與mid指向的記錄比較：若k=r[mid]，查找成功，結(jié)束若k<r[mid]，則high=mid-1若k>r[mid]，則low=mid+1重復(fù)上述操作，直至low>high時，查找失敗highmidlow數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第5頁。bin_search(st[],key,n){low=0;high=n-1;while(low<=high){mid=(low+high)/2;

if(st[mid]==key)returnmid;elseif(st[mid]>key)high=mid-1;elselow=mid+1;}return-1;}mid=(low+high)>>1;遞歸：bin_search(st[],key,l,h){if(l<=h){mid=(l+h)>>1;if(st[mid]==key)returnmid;elseif(st[mid]>key)returnbin_search(st,key,l,mid-1);elsereturnbin_search(st,key,mid+1,h)}elsereturn-1;}平均查找時間數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第6頁。3、分塊查找數(shù)據(jù)組織：將表分成幾塊，塊內(nèi)無序，塊間有序；先確定待查記錄所在塊，再在塊內(nèi)查找（1）用數(shù)組存放待查記錄,（2）建立索引表，由每塊中最大（?。┑年P(guān)鍵字及所屬塊位置的信息組成。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第7頁。12345678910111213141516171822121389203342443824486058745786532248861713索引表查38當(dāng)索引表較大時，可以采用二分查找在數(shù)據(jù)量極大時，索引可能很多，可考慮建立索引表的索引，即二級索引，原則上索引不超過三級數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第8頁。分塊查找方法評價由上面的公式，在n一定時，可以通過選擇s使ASL盡可能小可以證明，當(dāng)時，對于（1）ASL最小。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第9頁。小結(jié)：時間：順序查找最差，二分最好，分塊介于兩者之間空間：分塊最大，需要增加索引數(shù)據(jù)的空間特點：1）順序查找對表沒有特殊要求2）分塊時數(shù)據(jù)塊之間在物理上可不連續(xù)。所以可以達到插入、刪除數(shù)據(jù)只涉及對應(yīng)的塊；另外，增加了索引的維護。3）二分查找要求表有序，所以若表的元素的插入與刪除很頻繁，維持表有序的工作量極大。4）在表不大時，一般直接使用順序查找。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第10頁。二分查找的C/C++接口stdlib.hvoid*bsearch(void*key,void*base,intnelement,intsize,int(*fcmp)(constvoid*,constvoid*))其中：fcmp規(guī)定：第一個數(shù)據(jù)小于第二個，返回小于0的數(shù)第一個數(shù)據(jù)等于第二個，返回0第一個數(shù)據(jù)大于第二個，返回大于0的數(shù)數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第11頁。#include<iostream.h>#include<stdlib.h>cmp(constvoid*a,constvoid*b){ if(*(int*)a<*(int*)b)return-1; elseif(*(int*)a==*(int*)b)return0; elsereturn1;}voidmain(){ intar[]={-2,3,6,9,10,21,22,34,56}; int*p; intt; t=9; p=(int*)bsearch(&t,ar,sizeof(ar)/sizeof(int),sizeof(int),cmp); if(p!=NULL)cout<<*p<<endl;}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第12頁。8.2動態(tài)查找8.2.1二叉排序樹和二叉平衡樹一、二叉排序樹1

二叉排序樹定義

二叉排序樹（BinarySortTree）或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹中所有結(jié)點的值均小于它的根結(jié)點的值；（2）若右子樹不空，則右子樹中所有結(jié)點的值均大于它的根結(jié)點的值；（3）左、右子樹也分別為二叉排序樹；數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第13頁。45372453100619078312根據(jù)二叉排序樹的定義，對二叉樹進行LDR遍歷得到是遞增序列。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第14頁。2、查找：步驟：若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點的關(guān)鍵字值，遞歸查左子樹。若大于根結(jié)點的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功。12225030011020099105230216

TreeNode*SearchBST(t,key)/*在二叉分類樹查找關(guān)鍵字之值為key的結(jié)點，找到返回該結(jié)點的地址，否則返回空。t為二叉分類樹的根結(jié)點的指針。*/{if(t==NULL||key==t->data)returnt;elseif（key<t->data)returnSearchBST(t->lchild,key);elsereturnSearchBST(t->rchild,key);}//SearchBST數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第15頁。3、插入算法：首先執(zhí)行查找算法，找出被插結(jié)點的父親結(jié)點。判斷被插結(jié)點是其父親結(jié)點的左、右兒子。將被插結(jié)點作為葉子結(jié)點插入。若二叉樹為空。則首先單獨生成根結(jié)點。注意：新插入的結(jié)點總是葉子結(jié)點。例：將序列：122、99、250、110、300、280作為二叉排序樹的結(jié)點的關(guān)鍵字值，生成二叉排序樹。12299250300280110數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第16頁。voidInsertBST(*&t，key)//在二叉排序樹中插入查找關(guān)鍵字key{if(t==NULL){t=newBiTree;t->lchild=t->rchild=NULL;t->data=key;return;}if(key<t->data)InsertBST(t->lchild,key);elseInsertBST(t->rchild,key);}voidCreateBiTree(tree,d[],n）//n個數(shù)據(jù)在數(shù)組d中，tree為二叉排序樹根{tree=NULL;for(i=0;i<n;i++)InsertBST(tree,d[i]);}類C程序?qū)崿F(xiàn)：數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第17頁。4.二叉排序樹中一個結(jié)點的刪除在二叉排序樹中刪除結(jié)點的原則是：刪除結(jié)點后仍是二叉排序樹。設(shè)在二叉排序樹被刪除結(jié)點是x，其雙親結(jié)點為f。情況討論：（1）x為葉子結(jié)點，則直接刪除（2）x只有左子樹xL或只有右子樹xR,則令xL或xR直接成為雙親結(jié)點f的子樹；ffxxLfxxRf數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第18頁。（3）x即有左子樹xL也有右子樹xRfxxRxL在xL中選值最大的代替x，該數(shù)據(jù)按二叉排序樹的性質(zhì)應(yīng)在最右邊。qfxxRcscLqLsLfsxRcqcLqLsL數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第19頁。二叉排序樹的刪除操作例子

葉子結(jié)點：直接刪除。如：刪除數(shù)據(jù)為15、70的結(jié)點。15607030205060302050數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第20頁。12225030011020099105230216400450500若被刪結(jié)點的左兒子為空或者右兒子為空。如下圖所示，刪除結(jié)點的數(shù)據(jù)場為200的結(jié)點。刪除20012225030023021640045050011099105數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第21頁。被刪結(jié)點的左、右子樹皆不空1222503001102009910523021640045050011025030010520099230216400450500數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第22頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第23頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第24頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第25頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第26頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第27頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}pqs數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第28頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第29頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}psdq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第30頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第31頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}dpsdq數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第32頁。voiddelete(*&p){if(p->rchild==NULL){q=p;p=p->lchild;deleteq;}elseif(p->lchild==NULL){q=p;p=p->rchild;deleteq;}else{q=p;s=p->lchild;while(s->rchild!=NULL){q=s;s=s->rchild;}p->data=s->data;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;}deletes;}p等于q的情況spxqsxqp數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第33頁。刪除一個結(jié)點：DeleteBST(*&t,key)//在根為t的排序二叉樹中刪去值為key的結(jié)點{

if(!t)returnelseif(t->data==key){delete(t);elseif(t->data>key)DeleteBST(t->lchild,key);elseDeleteBST(t->rchild,key);}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第34頁。DABCFEG二、平衡二叉樹

起因：提高查找速度，避免最壞情況出現(xiàn)。如下圖單枝情況的出現(xiàn)。

平衡因子（平衡度）：結(jié)點的平衡因子是結(jié)點的左子樹的高度減去右子樹的高度。（或反之定義）平衡二叉樹：每個結(jié)點的平衡因子都為1、－1、0的二叉排序樹?；蛘哒f每個結(jié)點的左右子樹的高度最多差1的二叉排序樹。1、概念與定義數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第35頁。例：014125392863536050171873011-1-1-100000000平衡二叉樹028181453963536050173012-1-100001-1非平衡二叉樹0數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第36頁。

2、平衡樹的平衡方法：在左圖所示的平衡樹中插入數(shù)據(jù)為2的結(jié)點。插入之后仍應(yīng)保持平衡分類二叉樹的性質(zhì)不變。14125392863536050171873011-1-1-100000000平衡樹1412539286353605017187301-1-1-1000000002112原平衡度為0不平衡點解決：如何用最簡單、最有效的辦法保持平衡分類二叉樹的性質(zhì)2數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第37頁。141253928635360501718730+1+1-1-1-1000000002112原平衡度為0不平衡點Adelson解決思路：不涉及到不平衡點的雙親，即以不平衡點為根的子樹的高度應(yīng)保持不變。新結(jié)點插入后，向根回溯找到第一個原平衡因子不為0的結(jié)點（如圖中9）。新插入的結(jié)點和第一個平衡因子不為0的結(jié)點之間的結(jié)點，其平衡因子原皆為0在調(diào)整中，僅涉及前面所提到的最小子樹（如：以9為根的子樹）仍應(yīng)保持排序二叉樹的性質(zhì)不變。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第38頁。3、平衡種類分析

左調(diào)整（新結(jié)點插入在左子樹上的調(diào)整）：1、LL情況：（插入在結(jié)點左子樹的左子樹上）LL旋轉(zhuǎn)旋轉(zhuǎn)前后：高度都為h+11h-10AB1h-12hh-1BRARBLBA0h0h-1h-1BRARBL數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第39頁。旋轉(zhuǎn)算法voidLL_rotate(BBSTNode*a){BBSTNode*b;b=a->Lchild;a->Lchild=b->Rchild;b->Rchild=a;a->Bfactor=b->Bfactor=0;a=b;}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第40頁。2、LR情況：（新插入結(jié)點在左子樹的右子樹上）h-1旋轉(zhuǎn)前后高度仍然是h+1h-1CB0h-1BLARACRh-2CLh-1-10BLAB1h-102-1ARARCCRCLh-2h-101LR旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第41頁。旋轉(zhuǎn)算法voidLR_rotate(BBSTNode*a){BBSTNode*b,*c;b=a->Lchild;c=b->Rchild;/*初始化*/a->Lchild=c->Rchild;b->Rchild=c->Lchild;c->Lchild=b;c->Rchild=a;if(c->Bfactor==1){a->Bfactor=-1;b->Bfactor=0;}elseif(c->Bfactor==0)a->Bfactor=b->Bfactor=0;else{a->Bfactor=0;b->Bfactor=1;}}數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第42頁。

右調(diào)整（新結(jié)點插入在右子樹上進行的調(diào)整）1、RR情況：（插入在的右子樹的右子樹上）處理方法和LL對稱2、RL情況：（插入在右子樹的左子樹上）處理方法與LR對稱平衡樹建立方法：（1）按二叉排序樹插入結(jié)點（2）如引起結(jié)點平衡因子變?yōu)閨2|，則確定旋轉(zhuǎn)點，該點是離根最遠（或最接近于葉子的點）（3）確定平衡類型后進行平衡處理，平衡后以平衡點為根的子樹高不變數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第43頁。589162127431011二叉排序樹數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第44頁。結(jié)點的關(guān)鍵字個數(shù)至少為1。{q=p;cmp(constvoid*a,constvoid*b)線性探測再散列：di=1,2,3,……m-1elselow=mid+1;}例：將序列：122、99、250、110、300、280作為二叉排序樹的結(jié)點的關(guān)鍵字值，生成二叉排序樹。p->data=s->data;※在B+樹上，既可以進行縮小范圍的查找，也可以進行順序查找；※若在結(jié)點內(nèi)查找時，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進行查找次關(guān)鍵字——不能唯一的確定一個記錄，但能確定表的一個子表。{q=p;p=p->rchild;p選的不好，容易產(chǎn)生同義詞二叉排序樹的刪除操作例子elseif(p->lchild==NULL)類似于B_樹進行，即必要時，也需要進行結(jié)點的“分裂”或“合并”。用線性探測再散列處理沖突，即Hi=(H(key)+di)%m二叉平衡樹811122371095614數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第45頁。采用B_樹和B+

樹目的應(yīng)文件系統(tǒng)的要求而發(fā)展起來的，大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次訪問外存。但硬盤的驅(qū)動受機械運動的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外存次數(shù)。在1972年由R.Bayer和E.Macreight提出用B_樹作為索引組織文件。提高訪問速度、減少時間。 B_樹和B+樹一、B_樹及其操作數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第46頁。1、m階B_樹定義：m階B_樹滿足或空，或為滿足下列性質(zhì)的m叉樹：(1)樹中每個結(jié)點最多有m棵子樹(2)根結(jié)點在不是葉子時，至少有兩棵子樹(3)除根外，所有非終端結(jié)點至少有m/2棵子樹(4)有s個子樹的非葉結(jié)點具有n=s-1個關(guān)鍵字，結(jié)點的信息組織為:(n,A0,K1,A1,K2,A2

…Kn，An）

這里：n:關(guān)鍵字的個數(shù)，ki（i=1,2,…,n)為關(guān)鍵字，且滿足Ki<Ki+1,，Ai(i=0,1,..n)為指向子樹的指針。(5)所有的葉子結(jié)點都出現(xiàn)在同一層上，不帶信息（可認為外部結(jié)點或失敗結(jié)點）。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第47頁。例：4階B_樹。除根結(jié)點和葉子結(jié)點之外，每個結(jié)點的子樹個數(shù)至少為m/2=2個；結(jié)點的關(guān)鍵字個數(shù)至少為1。該B_樹的深度為4。葉子結(jié)點都在第4層上。藍色代表結(jié)點中關(guān)鍵字個數(shù)黑色代表結(jié)點中關(guān)鍵字第1層第2層第3層第4層133118243781111271391993475864FFFFFFFFFFFF數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第48頁。3、B_樹的查找：查找過程，類似于二叉樹的查找，關(guān)鍵字為key的記錄。從根開始在結(jié)點中順序或二分（當(dāng)m較大時）查找，如果Ki=key則查找成功,

若Ki<key<Ki+1：順Ai指向的子樹重復(fù)查找若key<K1：順A0指向的子樹重復(fù)查找若key>Kn;：找順An指向的子樹重復(fù)查找若找到葉子，則查找失敗。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第49頁。4、B_樹中結(jié)點的插入

m代表B_樹的階，插入總發(fā)生在最低層1）插入后關(guān)鍵字個數(shù)小于等于m-1,完成。2）插入后關(guān)鍵字個數(shù)等于m,結(jié)點分裂，以中點數(shù)據(jù)為界一分為二，中點數(shù)據(jù)放到雙親結(jié)點中。這樣就有可能使得雙親結(jié)點的數(shù)據(jù)個數(shù)為m,引起雙親結(jié)點的分裂，最壞情況下一直波及到根，引起根的分裂——B_樹長高。

122430457053902610039506185例：3階B_樹的插入操作。最多3棵子樹，2個數(shù)據(jù)；最少2棵子樹，1個數(shù)據(jù)。所以3階B_樹也稱為2-3樹。插入位置插入數(shù)據(jù)：33數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第50頁。31224304570539026100395061857243034570539026100395061851230324457053902610039506185127100303245390263950618512745707插入7數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第51頁。5、B_樹中結(jié)點的刪除*刪除發(fā)生在最底層（1）被刪關(guān)鍵字所在結(jié)點中的關(guān)鍵字數(shù)目大于等于m/2，直接刪除。（2）刪除后結(jié)點中數(shù)據(jù)為m/2-2，而相鄰的左（右）兄弟中數(shù)據(jù)大于m/2-1，此時左（右兄弟）中最大（小）的數(shù)據(jù)上移到雙親中，雙親中接（靠）在它后（前）面的數(shù)據(jù)移到被刪數(shù)據(jù)的結(jié)點中。32445539037100506170被刪關(guān)鍵字324456190371005370數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第52頁。(3)其左右兄弟結(jié)點中數(shù)據(jù)都是m/2-1，此時和左（右）兄弟合并，合并時連同雙親中相關(guān)的關(guān)鍵字。此時，雙親中少了一項，因此又可能引起雙親的合并，最壞一直到根，使B-樹降低一層。324459010061703244590371006170刪除3732445901006170數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第53頁。*刪除不在最底層在大于被刪數(shù)據(jù)中選最小的代替被刪數(shù)據(jù)，按B_樹性質(zhì)，其位置如下圖所示（x是要刪除的數(shù)據(jù)）xy用于代替x的數(shù)據(jù)問題轉(zhuǎn)換成在最底層的刪除數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第54頁。作業(yè)：試從空樹開始，畫出按以下次序向2-3樹中插入數(shù)據(jù)的建樹過程：20，30，50，52，60，68，70。如果以后刪除50和68，畫出每一步執(zhí)行后2-3樹的狀態(tài)。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第55頁。二、B+樹在實際的文件系統(tǒng)中，用的是B+樹或其變形。有關(guān)性質(zhì)與操作類似與B_樹。1、差異：（1）有n棵子樹的結(jié)點中有n個關(guān)鍵字（2）所有葉子結(jié)點中包含全部關(guān)鍵字信息及對應(yīng)記錄位置信息（3）所有非葉子為索引，只含關(guān)鍵字而且僅有子樹中最大或最小的信息。（4）非葉最底層順序聯(lián)結(jié)，這樣可以進行順序查找數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第56頁。59971544591015010203060910對應(yīng)01的記錄數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第57頁。2．查找過程※在B+樹上，既可以進行縮小范圍的查找，也可以進行順序查找；※在進行縮小范圍的查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束；※若在結(jié)點內(nèi)查找時，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進行查找3．插入和刪除的操作類似于B_樹進行，即必要時，也需要進行結(jié)點的“分裂”或“合并”。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第58頁。8.3哈希表前面查找方法共同特點：通過將關(guān)鍵字值與給定值比較，來確定位置。效率取決比較次數(shù)。理想的方法是：不需要比較，根據(jù)給定值能直接定位記錄的存儲位置。這樣，需要在記錄的存儲位置與該記錄的關(guān)鍵字之間建立一種確定的對應(yīng)關(guān)系，使每個記錄的關(guān)鍵字與一個存儲位置相對應(yīng)。例1949-2000年某地區(qū)人口統(tǒng)計表可以按公式確定其人數(shù)：y年人數(shù)=表[y-1948]年份人數(shù)123…..5152194919501951……...19992000200021002200……...44004420數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第59頁。1.哈希（也稱為Hash、雜湊、散列）基本思想在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到元素。哈希函數(shù)——在記錄的關(guān)鍵字與記錄的存儲位置之間建立的一種對應(yīng)關(guān)系。哈希函數(shù)是一種映象，是從關(guān)鍵字空間到存儲位置空間的一種映象。哈希函數(shù)可寫成：

addr(ai)=h(ki)ai是表中的一個元素addr(ai)是ai的存儲位置信息ki是ai的關(guān)鍵字數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第60頁。哈希表——應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的位置信息，并將記錄根據(jù)此信息放入表中，這樣構(gòu)成的表叫哈希表。哈希查找——利用哈希函數(shù)進行查找的過程。除了特別簡單的應(yīng)用，在大多數(shù)情況下，所構(gòu)造出的哈希函數(shù)是多對一的（非單射函數(shù)）。即可能有多個不同的關(guān)鍵字，它們對應(yīng)的哈希函數(shù)值是相同的，這意味著不同記錄由哈希函數(shù)確定的存儲位置是相同的。這種情況被稱為沖突。即：若key1不等于key2,而h(key1)=h(key2)

Hash查找適合于關(guān)鍵字可能出現(xiàn)的值的集合遠遠大于實際關(guān)鍵字集合的情形。根據(jù)抽屜原理，沖突是不可能完全避免的，所以，要解決：（1）構(gòu)造一個性能好，沖突少的Hash函數(shù)（2）如何解決沖突數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第61頁。2、常用的哈希函數(shù)（1）直接定址法構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址，即H(key)=key或H(key)=a·key+b特點：

直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突實際中能用這種哈希函數(shù)的情況很少。此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第62頁。(2)數(shù)字分析法構(gòu)造：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址。

例有80個記錄，關(guān)鍵字為8位十進制數(shù)，哈希地址為2位十進制數(shù)8134653281372242813874228130136781322817813389678136853781419355…..…..分析：只取8只取1只取3、4只取2、7、5數(shù)字分布近乎隨機所以：取任意兩位或兩位與另兩位的疊加作哈希地址數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第63頁。此方法僅適合于：能預(yù)先估計出全體關(guān)鍵字的每一位上各種數(shù)字出現(xiàn)的頻度。(2)數(shù)字分析法構(gòu)造：對關(guān)鍵字進行分析，取關(guān)鍵字的若干位或其組合作哈希地址。

數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第64頁。以關(guān)鍵字的平方值的中間幾位作為存儲地址。求“關(guān)鍵字的平方值”的目的是“擴大差別”，同時平方值的中間各位又能受到整個關(guān)鍵字中各位的影響。（3）平方取中法數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第65頁。（4）折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址。種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加。例關(guān)鍵字為：0442205864，哈希地址位數(shù)為4586442200410088H(key)=0088移位疊加58640224046092H(key)=6092間界疊加數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第66頁。

此方法適合于:關(guān)鍵字的數(shù)字位數(shù)特別多，且每一位上數(shù)字分布大致均勻情況。（4）折疊法構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進位）做哈希地址。種類移位疊加：將分割后的幾部分低位對齊相加間界疊加：從一端沿分割界來回折送，然后對齊相加。數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第67頁。（5）除留余數(shù)法構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key%p，pm特點：簡單、常用，可與上述幾種方法結(jié)合使用p的選取很重要；p選的不好，容易產(chǎn)生同義詞（6）隨機數(shù)法構(gòu)造：取關(guān)鍵字的偽隨機函數(shù)值作哈希地址，即H(key)=random(key)適于關(guān)鍵字長度不等的情況說明：哈希函數(shù)構(gòu)造不應(yīng)太復(fù)雜不存在絕對好和壞的函數(shù)數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第68頁。3、沖突解決A)開放定址法方法：當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)%m，i=1,2,……k(km-1)其中：H(key)——哈希函數(shù)

m——哈希表表長

di——增量序列分類線性探測再散列：di=1,2,3,……m-1二次探測再散列：di=12,-12,22,-22,32,……±k2(km/2)偽隨機探測再散列：di=偽隨機數(shù)序列數(shù)據(jù)結(jié)構(gòu)查找全套PPT全文共79頁，當(dāng)前為第69頁。例已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=key%13,哈希表長為m=16，

設(shè)每個記錄的查找概率相等用線性探測再散列處理沖突，即Hi=(H(key)+di)%mH(55)=3沖突->H1=(3+1)%16=4

沖突->H2=(3+2)%16=5H(79)=1沖突->H1=(1+1)%16=2

沖突->H2=(1+2)%16=3

沖突->H3=(1+3)%16=4

沖突->H4=(1+4)%16=5

沖突->H5=(1+5)%16=6

沖突->H6=(1+6)%16=7

沖突->H7=(1+7)%16=8

沖突->H8=(1+8)%16=9012345678910111213141514168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1沖突->H1=(1+1)%16=2H(68)=3H(20)=7H(84)=6沖突->H1=(6+1)%16=7

沖突->H2=(6+2)%16=8H(27)=1沖突->H1

=(1+1)%16=2

沖突->H2=(1+2)%16=3

沖突->