數(shù)據(jù)結(jié)構(gòu)課程講義.ppt

第九章 查找,這也是線性表的基本運(yùn)算之一。通常稱為檢索、查詢等。 1 線性查找 11 順序檢索 基本思想： 從線性表的一端開始，逐個地將待查找元素的關(guān)鍵字與每個元素的關(guān)鍵字進(jìn)行比較，若找到，則返回1，否則返回0。 該算法的時間復(fù)雜度為O(n).,1 線性查找,順序查找采用從頭至尾逐個比較 最快O(1) 最慢O(n) 查找成功的等概率平均時間復(fù)雜性 O(n+1)/2) 1/n(1+2+3+n)=(n+1)/2 查找失敗O(n+1) 查找的等概率平均時間復(fù)雜性 O(3(n+1)/4) 查找成功失敗各半 1/2n(1+2+n)+n(n+1)=3(n+1)/4,1 線性查找,1 線性查找,12 二分查找 亦稱折半查找，是基于提高查找速度的一種方法。檢索時要求元素是排序的。 基本思想： 每次將待查找元素的關(guān)鍵字與已排序元素序列的中間點(diǎn)元素進(jìn)行比較，如相等，則返回1，否則修改高點(diǎn)或低點(diǎn)，重新進(jìn)行查找比較。 該算法的時間復(fù)雜度為O(n).,這是有序表的查找查找,對已排序的查找結(jié)構(gòu)先確定中點(diǎn)，比較待查關(guān) 鍵字與中點(diǎn)關(guān)鍵字的大小，反復(fù)直到成功。 求n個數(shù)據(jù)折半查找的等概率成功查找的平均時 間復(fù)雜性 1 2 3 4 5 6 7 8 9 10,1,2,2,3,3,3,3,4,4,4,1+2*2+4*3+3*4=29 O(29/10),n個元素的折半查找,2k-1n2k+1-1 查找成功平均概率時間復(fù)雜性 介于 log2(2k)-1 和 log2(2k+1)-1 之間 即 k-1 和 k 之間 k=log2(n+1) n個元素的折半查找成功平均概率時間復(fù)雜性 log2(n+1)-1/2,1 線性查找,13 分塊查找 亦稱索引順序查找。也是基于提高查找速度的一種方法。檢索時要求元素構(gòu)成的塊間是排序的，而塊內(nèi)是未排好序的。 基本思想： 將所有元素按關(guān)鍵字值劃分成若干塊，塊之間是排序的，而塊內(nèi)暫時是無序的。查找時候，首先折半查找確定元素所在的塊，然后再在塊內(nèi)進(jìn)行順序查找即可比較。,3、索引順序查找,分塊有序 后一子表中的關(guān)鍵字都大于前一子表中的關(guān)鍵字,最大關(guān)鍵字 起始地址,索引表,索引順序表的查找,查找 關(guān)鍵字key=38 1. 先檢索索引表 確定子表位置 2. 再在子表中查找,索引表,分塊查找成功的平均概率時間復(fù)雜性,索引表查找時間+子表查找時間 設(shè)索引表長為s，查找表長為n,被平均分成s塊， 每塊長n/s, 索引表平均查找時間 (s+1)/2 子表平均查找時間 (n/s+1)/2 (s+1)+ (n/s+1)= (s+n/s)+1 當(dāng) s=n 時 有最小值 n +1,當(dāng)索引順序表已經(jīng)排序時，子塊查找可以用折半查找。 平均查找時間： (s+1)/2 +log2(1+n/s)-1/2 = log2(1+n/s)+s/2 索引也用折半查找，平均查找時間 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1 當(dāng)s= n 時 2 log2(n +1)-1,2 樹形結(jié)構(gòu)的查找,21 二叉排序樹及其查找過程 二叉樹BT是二叉排序樹，只要BT是滿足如下的條件： （1）若BT的左子樹非空，則其左子樹上所有結(jié)點(diǎn)的值均小于其根結(jié)點(diǎn)的值；（2）若其右子樹上所有結(jié)點(diǎn)的值均大于其根結(jié)點(diǎn)的值；（3）其左右子樹均為二叉排序樹。 對二叉排序樹的中序遍歷的結(jié)果就是一個升序序列。 二叉排序樹又稱為二叉查找樹。 于是，只要將元素序列組織成二叉排序樹，在進(jìn)行查找時，讓待查找元素與根結(jié)點(diǎn)值進(jìn)行比較，若相等，則查找成功，否則，如果比根結(jié)點(diǎn)小，則只需要在左子樹中查找即可；如果比根結(jié)點(diǎn)大，則只需要在右子樹中查找即可。,2 樹形結(jié)構(gòu)的查找,其所涉及到的數(shù)據(jù)結(jié)構(gòu)如下： typedef struct btnode keytype key; datatype other; struct btnode *lchild,*rchild; BSTNODE; BSTNODE *ptr; 則*ptr就表示一棵二叉排序樹。,2 樹形結(jié)構(gòu)的查找,22 二叉排序樹實(shí)現(xiàn)查找運(yùn)算 根據(jù)二叉排序樹的定義和性質(zhì)，不難得到其查找算法： int bstsearch(*Pt,x) pkey=x) return(1); if(p-keyx) prchild; else plchild; ,二叉查找樹的查找分析,平均等概率查找時間 (1+2+2+3+3+3)/6=14/6,45,12,57,8,20,60,45,12,8,20,3,11,(1+2+3+4+5+6)/6=7/2,隨機(jī)二叉查找樹等概率平均查找時間,P(n)2(1+1/n)lnn O(log2n) 最壞 O(n/2),特點(diǎn)：用于頻繁進(jìn)行插入、刪除、查找的所謂動態(tài)查找表。,122,250,300,110,200,99,二叉排序樹,L,N,P,E,M,C,Y,105,230,216,查找步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。 否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹。 若大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。 在左右子樹上的操作類似。,122,250,300,110,200,99,105,230,216,2 樹形結(jié)構(gòu)的查找,2.2 二叉排序樹的插入運(yùn)算 由于插入運(yùn)算是二叉樹的基本運(yùn)算之一，所以利用二叉樹的插入運(yùn)算就可以實(shí)現(xiàn)在線性升序序列中插入結(jié)點(diǎn)，使之仍然是升序的功能。 其實(shí)現(xiàn)過程為：若二叉排序樹為空，則待插入結(jié)點(diǎn)*s就作為根結(jié)點(diǎn)插入到空二叉樹中；若二叉樹非空，則比較s-key:p-key,若，就插入到右子樹中，若=則不必插入。 該過程是遞歸的，很容易得到遞歸算法，也可以得到非遞歸算法。,2 樹形結(jié)構(gòu)的查找,void insertbst(*pt,*s) pkeykey) plchild; else prchild; if(pt=NULL) ptkeykey) f-lchildrchild=s; 顯然，插入運(yùn)算是將待插入結(jié)點(diǎn)作為葉子插入的。所以算法的目的就是首先找到插入的位置。,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,122,250,99,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,122,250,99,122,250,110,99,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法： 首先執(zhí)行查找算法，找出被插結(jié)點(diǎn)的父親結(jié)點(diǎn)。 判斷被插結(jié)點(diǎn)是其父親結(jié)點(diǎn)的左、右兒子。將被 插結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。 若二叉樹為空。則首先單獨(dú)生成根結(jié)點(diǎn)。 注意：新插入的結(jié)點(diǎn)總是葉子結(jié)點(diǎn)。,122,250,300,110,280,99,e、g：將數(shù)的序列：122、99、250、110、300、280 作為二叉排序樹的結(jié) 點(diǎn)的關(guān)鍵字值，生成二叉排序樹。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法：,執(zhí)行實(shí)例：插入值為 280 的結(jié)點(diǎn),15,60,70,30,20,50,3、二叉排序樹的查找分析,平均情況分析（在成功查找兩種的情況下）,e.g: 下述兩種情況下的成功的平均查找長度 ASL,15,60,70,30,20,50,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,2 樹形結(jié)構(gòu)的查找,2.3 二叉排序樹的刪除運(yùn)算 由于刪除結(jié)點(diǎn)運(yùn)算也是二叉樹的基本運(yùn)算之一，所以利用二叉樹的刪除運(yùn)算就可以實(shí)現(xiàn)在線性升序序列中刪除結(jié)點(diǎn)，使之仍然是升序的序列。 其實(shí)現(xiàn)過程為： 若待刪除結(jié)點(diǎn)不在二叉排序樹，則不進(jìn)行任何操作；否則，假設(shè)找到的待刪除結(jié)點(diǎn)為*p，fath指向*p的雙親，那么，刪除*p的過程可以采用如下的方法：*p是否有左（右）子樹來分別進(jìn)行處理。,2 樹形結(jié)構(gòu)的查找,（1）若*p沒有左子樹，則只需要將*p的右子樹按照二叉排序樹的特性，連接到合適的位置即可。若*p沒有根結(jié)點(diǎn)，則只需要將*p的右子樹的根作為新的根結(jié)點(diǎn)；若*p不是根，則必須將它與其雙親*fath之間的連接斷開，可以采用將將連接到*p的右子樹連接到*fath的左（右）鏈域上。當(dāng)然，若*p的右子樹也為空，則*p就是葉子結(jié)點(diǎn)，即p-rchild=NULL,則就相當(dāng)于將空樹連接到*fath的左（右）鏈域中。,2 樹形結(jié)構(gòu)的查找,（2）若*p有左子樹，則*p也可能有右子樹，需要將*p的左、右子樹按照二叉排序樹的特性，連接到合適的位置。此時可以采用兩種處理方法：一種是令p的左子樹直接連接到*p的雙親*fath的左（右）鏈域上，而*p的右子樹下接到*p的中序前趨結(jié)點(diǎn)*s的右鏈域上。（這里*s是*p的左子樹中最右下的結(jié)點(diǎn)，其右鏈域肯定為空）。 另外一種處理方法是：采用以*p的中序前趨*s頂替*p(相當(dāng)于將*s的內(nèi)容復(fù)制到*p中)，將*s的左子樹直接上接到*s的雙親*q左（右）鏈域上，再刪去*s。,葉子結(jié)點(diǎn)：直接刪除，更改它的父親結(jié)點(diǎn)的相應(yīng)指針域?yàn)榭?。如：刪除關(guān)鍵字為 15、70 的結(jié)點(diǎn)。,15,60,70,30,20,50,60,30,20,50,子樹的根結(jié)點(diǎn)：通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？左子樹中最大的結(jié)點(diǎn) 或 右子樹中最小的結(jié)點(diǎn)，參看圖。 要點(diǎn)：維持二叉排序樹的特性不變。在中序周游中緊靠著被刪結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。,122,250,300,110,200,99,105,230,216,400,450,500,子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。 如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為 99 、200 的結(jié)點(diǎn)。,被刪結(jié)點(diǎn),122,250,300,200,230,216,400,450,500,110,105,刪除,99,122,250,300,110,200,99,105,230,216,400,450,500,被刪結(jié)點(diǎn),子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。 如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為 99 、200 的結(jié)點(diǎn)。,122,250,300,230,216,400,450,500,刪除,200,110,99,105,122,250,300,110,200,99,105,230,216,400,450,500,被刪結(jié)點(diǎn),子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左兒子為空或者右兒子為空。 如下圖所示，刪除結(jié)點(diǎn)的關(guān)鍵字為 99 、200 的結(jié)點(diǎn)。,結(jié)論：將被刪結(jié)點(diǎn)的另一兒子作為它的父 親結(jié)點(diǎn)的兒子，究竟是作為左兒子 還是右兒子依原替身結(jié)點(diǎn)和其父親 結(jié)點(diǎn)的關(guān)系而定。 釋放被刪結(jié)點(diǎn)的空間。,被刪結(jié)點(diǎn),子樹的根結(jié)點(diǎn)：若被刪結(jié)點(diǎn)的左、右子樹皆不空，通常的做法：選取“替身”取代被刪結(jié)點(diǎn)。有資格充當(dāng)該替身的是誰哪？ 左子樹中最大的結(jié)點(diǎn)(被刪結(jié)點(diǎn)的左子樹中的最右的結(jié)點(diǎn)，其右兒子指針域?yàn)榭? 或 右子樹中最小的 結(jié)點(diǎn)(被刪結(jié)點(diǎn)的右子樹中的最左的結(jié)點(diǎn)，其左兒子指針域?yàn)榭? ，參看下圖。 要點(diǎn)：維持二叉排序樹的特性不變。在中序周游中緊靠著被刪 結(jié)點(diǎn)的結(jié)點(diǎn)才有資格作為“替身”。,做法：將替身的關(guān)鍵字復(fù)制到被刪結(jié) 點(diǎn)的關(guān)鍵字。 將結(jié)點(diǎn) 的左兒子作為 的父結(jié)點(diǎn) 的右兒子。,110,110,99,注意：結(jié)點(diǎn) 右兒子必為空 結(jié)點(diǎn) 的父結(jié)點(diǎn)為,110,110,99,200,250,300,110,99,105,230,216,400,450,500,做法：將替身的關(guān)鍵字復(fù)制到被刪結(jié) 點(diǎn)的關(guān)鍵字。 將結(jié)點(diǎn) 的右兒子作為 的父結(jié)點(diǎn) 的左兒子。,注意：結(jié)點(diǎn) 左兒子必為空 結(jié)點(diǎn) 的父結(jié)點(diǎn)為,200,200,200,200,250,結(jié)論： 先將替身的關(guān)鍵字復(fù)制到被刪結(jié)點(diǎn) 將原替身的另一兒子作為它的父親 結(jié)點(diǎn)的兒子，究竟是作為左兒子還 是右兒子依原替身結(jié)點(diǎn)和其父親結(jié) 點(diǎn)的關(guān)系而定。 釋放原替身結(jié)點(diǎn)的空間。,F,S,C,Q,QL,SL,F,C,Q,QL,S,SL,F,PL、PR皆 空， 直接刪除 。,PL或PR為空，,PL為空，刪除后的情況。,1.刪除法,2.刪除法,2 樹形結(jié)構(gòu)的查找,24 平衡二叉樹簡介 由于二叉排序樹的結(jié)構(gòu)形態(tài)直接影響到查找的效率，所以必須構(gòu)造出平衡二叉樹。只要滿足平衡因子（即任何兩個子樹的高度之差）只能是-1，0，1的，則稱為平衡二叉樹。 通常情況下，平衡二叉樹的深度是很低的，所以其查找效率是最高的。,D,G,E,D,A,B,C,F,E,G,B,A,平衡二叉排序樹,起因：提高查找速度，避免最壞情況出現(xiàn)。如右圖情況的出現(xiàn)。 雖然完全樹的樹型最好，但構(gòu)造困難。常使用平衡樹。,C,F,平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度右子樹的高度。 平衡二叉樹：每個結(jié)點(diǎn)的平衡因子都為 1、1、0 的二叉樹?；蛘哒f每個 結(jié)點(diǎn)的左右子樹的高度最多差一的二叉樹。 注意：完全樹必為平衡樹，平衡樹不一定是完全樹。,平衡樹的 Adelson 算法的本質(zhì)特點(diǎn)： 以插入為例： 在左圖所示的平衡樹中插入關(guān)鍵字為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡排序二叉樹的性質(zhì)不變。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,平衡樹,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度為 0,危機(jī)結(jié)點(diǎn),如何用最簡單、最有效的辦法保持平衡排序二叉樹的性質(zhì)不變？,平衡樹的 Adelson 算法的本質(zhì)特點(diǎn)： 以插入為例： 在左圖所示的平衡樹中插入關(guān)鍵字為 2 的結(jié)點(diǎn)。 插入之后仍應(yīng)保持平衡排序二叉樹的性質(zhì)不變。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度為 0,危機(jī)結(jié)點(diǎn),如何用最簡單、最有效的辦法保持平衡排序二叉樹的性質(zhì)不變？,解決方案： 不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（左圖為 3 ）。 新結(jié)點(diǎn)插入后，找到第一個平衡度不為 0 的結(jié)點(diǎn)（如左圖結(jié)點(diǎn) ）即可。新插入的結(jié)點(diǎn)和 第一個平衡度不為 0 的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為 0 在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如： ），其它結(jié)點(diǎn)不予調(diào)整。 仍應(yīng)保持排序二叉樹的性質(zhì)不變。,9,3,5,9,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度為 0,危機(jī)結(jié)點(diǎn),如何用最簡單、最有效的辦法保持平衡排序二叉樹的性質(zhì)不變？,2,3,5,9,7,12,2,3,5,9,7,12,不可以以結(jié)點(diǎn) 為子樹的根結(jié)點(diǎn)！雖然，對本例來說是可以行得通的。,7,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度為 0,危機(jī)結(jié)點(diǎn),關(guān)鍵：將導(dǎo)致出現(xiàn)危機(jī)結(jié)點(diǎn)的情況全部分析清除，就可以使得平衡排序二叉樹的性質(zhì)保持不變！,14,9,3,2,5,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,12,0,0,2.5 非平衡二叉樹的平衡處理方法,若一棵二叉排序樹是平衡二叉樹，插入某個結(jié)點(diǎn)后，可能會變成非平衡二叉樹，這時，就可以對該二叉樹進(jìn)行平衡處理，使其變成一棵平衡二叉樹。處理的原則應(yīng)該是處理與插入點(diǎn)最近的、而平衡因子又比1大或比-1小的結(jié)點(diǎn)。我們分四種情況討論平衡處理。,1、LL型 的處理(左左型) 如下圖所示，在A的左孩子B上插入一個左孩子結(jié)點(diǎn)C，使A的平衡因子由1變成了2，成為不平衡的二叉樹序樹。這時的平衡處理為：將A順時針旋轉(zhuǎn)，成為B的右子樹，而原來B的右子樹則變成A的左子樹，待插入結(jié)點(diǎn)C作為B的左子樹。(注：圖中結(jié)點(diǎn)旁邊的數(shù)字表示該 結(jié)點(diǎn)的平衡因子)，即左改組。,左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析： 1、LL 情況：（LL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的左子樹上）,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,LL 改組,BL,BR,AR,B,A,0,h,0,h-1,h-1,BL,BR,AR,危機(jī)結(jié)點(diǎn),改組前：高度為 h + 1 中序序列：,A,B,BL,BR,AR,改組后：高度為 h + 1 中序序列：,A,B,BL,BR,AR,注意：改組后 平衡度為 0,A,B,2、LR型的處理(左右型) 如下圖所示，在A的左孩子B上插入一個右孩子C，使的A的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處理為：將C變到B與A 之間，使之成為LL型，然后按第(1)種情形LL型處理。此LR型又存在下列三種情形：,左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析： 2、LR 情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的右子樹上） 情形1：,A,B,+1,h-1,0,+2,-1,h-1,LR 改組,BL,AR,危機(jī)結(jié)點(diǎn),改組前： 高度為 h + 1 中序序列：,注意：改組后 平衡度為 0,0,-1,C,B,C,CL,CR,h-2,h-2,h-1,0,+1,C,B,0,h-1,h-1,BL,AR,A,CR,h-2,CL,h-1,-1,0,A,B,BL,AR,C,CL,CR,改組后： 高度為 h + 1 中序序列：,A,B,BL,AR,C,CL,CR,A,左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析： 2、LR 情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的右子樹上） 情形2：,A,B,+1,h-1,0,+2,-1,h-1,LR 改組,BL,AR,危機(jī)結(jié)點(diǎn),改組前： 高度為 h + 1 中序序列：,注意：改組后 平衡度為 +1,0,0,C,B,C,CR,CL,h-1,h-2,h-2,0,-1,C,B,0,h-1,h-1,BL,AR,A,CR,h-1,CL,h-2,+1,0,A,B,BL,AR,C,CR,CL,改組后： 高度為 h + 1 中序序列：,A,A,B,BL,AR,C,CR,CL,左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）的情況分析： 2、LR 情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的左子樹的右子樹上） 情形3：,A,B,+1,0,+2,-1,LR 改組,危機(jī)結(jié)點(diǎn),改組前： 高度為 2 中序序列：,注意：改組后 平衡度為 0,0,0,C,B,C,0,A,B,C,A,新插入結(jié)點(diǎn),A,B,C,改組后： 高度為 2 中序序列：,C,B,0,A,0,0,四種情況的區(qū)分： 如果 的平衡度為1 則為 LL型改組； 否則為 LR型改組：若 的平衡度為1、1 、0 ；則分別為 LRA、LRB、LRC型改組。,B,C,3、RR型的處理(右右型) 如圖下所示，在A的右孩子B上插入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉(zhuǎn)，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待插入結(jié)點(diǎn)C成為B的右子樹。,4、RL型的處理(右左型) 如下圖所示，在A的右孩子B上插入一個左孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將C變到A與B之間，使之成為RR型，然后按第3 種情形RR型處理。,這里的右改組方法（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的右子樹上進(jìn)行的調(diào)整）的情況分析： 1、RR 情況：（RR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子樹的右子樹上） 處理圖形和 LL 鏡象相似 2、RL 情況：（RL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的右子樹的左子樹上） 1、處理圖形和 LRA 鏡象相似 2、處理圖形和 LRB 鏡象相似 3、處理圖形和 LRC 鏡象相似 。,例2，給定一個關(guān)鍵字序列4,5,7,2,1,3,6，試生成一棵平衡二叉樹。 分析：平衡二叉樹實(shí)際上也是一棵二叉排序樹，故可以按建立二叉排序樹的思想建立，在建立的過程中，若遇到不平衡，則進(jìn)行相應(yīng)平衡處理，最后就可以建成一棵平衡二叉樹。具體生成過程見下圖。,26 平衡二叉樹的查找及性能分析,平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復(fù)雜度O(n)，它的時間復(fù)雜度與二叉排序樹的最好時間復(fù)雜相同，都為O(log2n)。,例3 對例2給定的關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數(shù)及成功的平均查找長度。 分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹和平衡二叉樹都是唯一的,得到的平衡二叉樹見上圖，得到的二叉排序樹見下圖。,從上圖的二叉排序樹可知，查找6需4次，平均查找長度ASL=(1+2+2+3+3+3+4)/7=18/72.57。 從圖8-14的平衡二叉樹可知，查找6需2次，平均查找長度 ASL=(1+2+2+3+3+3+3)=17/72.43。,從結(jié)果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。,1、為什么采用B_ 樹和 B+ 樹： 大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次 訪問外存。但硬盤的驅(qū)動受機(jī)械運(yùn)動的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。 在 1970 年由 R bayer 和 E macreight 提出用B_ 樹作為索引組織文件。提高訪問速度、減少時間。,內(nèi)存,E.G: 用二叉樹組織文件，當(dāng)文件的記錄個數(shù)為 100，000時，要找到給定關(guān)鍵字的記錄，需訪問外存17次（log100,000）,太長了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,數(shù)據(jù)文件,文件頭，可常駐內(nèi)存,文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上,8.2.2 B_ 樹和 B+ 樹,2、B_ 樹是一種多分支數(shù)，首先介紹 m 階 B_ 樹： 定義： m 階 B_ 樹滿足或空，或： A、根結(jié)點(diǎn)要么是葉子，要么至少有兩個兒子 B、除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個結(jié)點(diǎn)的兒子個數(shù)為: m/2 K1 且 Kn 的結(jié)點(diǎn)的地址（指在該 B_ 樹中） 注意：K1 =K2 = . = Kn D、所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點(diǎn)或失敗結(jié)點(diǎn)）。,例如：m = 4 階 B_ 樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個結(jié)點(diǎn)的兒子個數(shù) 至少為 m/2 = 2 個；結(jié)點(diǎn)的關(guān)鍵字個數(shù)至少為 1 。該 B_ 樹的深度為 4。 葉子結(jié)點(diǎn)都在第 4 層上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 層,第 2 層,第 3 層(L層),第 4 層(L1層),3、B_ 樹的查找代價分析： 查找過程，類似于二叉樹的查找。如查找關(guān)鍵字為 KEY 的記錄。 從根開始查找，如果 Ki = KEY 則查找成功，Ri 為關(guān)鍵字為 KEY 的記錄的地址。 若 Ki Kn; 查找 An指向的結(jié)點(diǎn) 若 找到葉子，則查找失敗。 注意：每次查找將去掉 （s-1）/s 個分支，比二分查找快得多。 設(shè)關(guān)鍵字的總數(shù)為 N ，求 m階 B_ 樹的最大層次 L。 層次 結(jié)點(diǎn)數(shù) 關(guān)鍵字的個數(shù)（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：Llog （N+1）/2）+ 1,3、B_ 樹的查找代價分析： 設(shè)關(guān)鍵字的總數(shù)為 N ，求 m階 B_ 樹的最大層次 L。 故：Llog m/2 （N+1）/2）+ 1 設(shè) N 1000，000 且 m256 ，則 L = 3；最多 3 次訪問外存可找到所有的記錄。,4、B_ 樹的插入操作 1、確定插入位置，將結(jié)點(diǎn)插入到第 L 層（注意：第 L+1 層為葉子結(jié)點(diǎn)） 2、找到插入位置，將關(guān)鍵字和其它信息按序插入。 3、若被插入結(jié)點(diǎn)的關(guān)鍵字個數(shù) m-1, 則該結(jié)點(diǎn)滿。必須分裂成兩個結(jié)點(diǎn)。否則不滿結(jié)束。 如結(jié)點(diǎn)原為： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一個關(guān)鍵字之后變?yōu)椋?（m, A0, (K1, A1), (K2, A2), (Km, Am)） 該結(jié)點(diǎn)將進(jìn)行分裂： . (K m/2 , p ) . （m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新結(jié)點(diǎn) p, 將原結(jié)點(diǎn)的后半部分復(fù)制過去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹可能長高一層。,P,P,(K m/2 , p ) 數(shù)據(jù)項插入上層結(jié)點(diǎn)之中,B-樹的插入方法 設(shè)要插入關(guān)鍵值為k的記錄，指向k所在記錄的指針為p。 首先找到k應(yīng)插入的葉子結(jié)點(diǎn)，將 k和p插入。然后，判斷被插入結(jié)點(diǎn)是否滿足m叉B-樹的定義，即插入后結(jié)點(diǎn)的分支數(shù)是否大于m（結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)是否大于m-1)，若不大于，則插入結(jié)束；否則，要把該結(jié)點(diǎn)分裂成兩個。方法是： 申請一個新結(jié)點(diǎn)，由指針p指向，將插入后的結(jié)點(diǎn)按照關(guān)鍵字的值大小分成左、中、右三部分，中間只含一項，左邊的留在原結(jié)點(diǎn)，右邊的移入新結(jié)點(diǎn)，中間的構(gòu)成新的插入項，插入到它們的雙親結(jié)點(diǎn)中，若雙親結(jié)點(diǎn)在插入后也要分裂，則在分裂后再往上插入。,例如：3 階 B_ 樹的插入操作。m=3, m/2 - 1 = 1; 至少 1 個關(guān)鍵字，二個兒子結(jié)點(diǎn)。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,5、B_ 樹的刪除操作 1、查找具有給定鍵值的關(guān)鍵字 Ki 2、如果 在第 L 層，可直接刪除（注意：第 L+1 層為葉子結(jié)點(diǎn)），轉(zhuǎn) 4 。 3、否則，則首先生成 “替身”。用 的右子樹中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即 處于第 L 層上的最小 關(guān)鍵字值取代 。然后，刪除第 L 層上的該關(guān)鍵字。 4、從第 L 層開始進(jìn)行刪除。 A、不動：若刪除關(guān)鍵字值的那個結(jié)點(diǎn)的關(guān)鍵字的個數(shù)仍處于 m/2 -1和 m-1之間。則結(jié)束。 B、借：若刪除關(guān)鍵字值的那個結(jié)點(diǎn)的關(guān)鍵字的個數(shù)原為 m/2 -1 。而它們的左或右鄰居結(jié) 點(diǎn)的關(guān)鍵字的個數(shù) m/2 -1 ; 則借一個關(guān)鍵字過來。處理結(jié)束。 C、并：若該結(jié)點(diǎn)的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個數(shù)為 m/2 -1 ; 則執(zhí)行合并結(jié)點(diǎn)的操作。 如結(jié)點(diǎn)原為： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L ,第 L 層：找到了被刪結(jié)點(diǎn)的替身。,例如：3 階 B_ 樹的刪除操作。m=3, m/2 - 1 = 1; 至少 1 個關(guān)鍵字，二個兒子結(jié)點(diǎn)。,3,24,45,53 90,37,100,50,61，70,被刪關(guān)鍵字,3,24,45,61 90,37,100,53,70,借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn),假定再刪除該關(guān)鍵字,3,24,45,90,37,100,61，70,假定再刪除該關(guān)鍵字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父結(jié)點(diǎn)的一個關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使B_ 樹的深度降低一層！,3 散列查找,由于前兩種查找方法中，記錄在結(jié)構(gòu)中的相對位置是隨機(jī)的，和其關(guān)鍵碼值之間沒有直接的聯(lián)系，因此在進(jìn)行檢索時，必須采用“比較”手段來實(shí)現(xiàn)，顯然，查找的效率依賴于檢索過程中進(jìn)行比較的次數(shù)。 于是，理想的查找是不經(jīng)過任何比較或少經(jīng)過比較就能夠得到所查找的元素，則必須在記錄與其關(guān)鍵字值之間建立一個確定的對應(yīng)關(guān)系h，使得每個關(guān)鍵字和結(jié)構(gòu)中的一個唯一的存儲位置相對應(yīng)，這樣在檢索時，找到給定值K的影象H（K），若記錄中存在關(guān)鍵碼和k相等的記錄，則必然存儲在h(k)的存儲位置上，因此不需要進(jìn)行比較即可直接得到所查找的記錄。通常稱這個對應(yīng)關(guān)系h為散列函數(shù)，采用該散列函數(shù)所建立的表稱為散列表。,3 散列查找,實(shí)踐表明： （1）如果散列表是一一對應(yīng)的函數(shù)，則根據(jù)散列函數(shù)對給定的值進(jìn)行某種運(yùn)算，即可得到待查找元素的位置； （2）散列表占用的空間可能比結(jié)點(diǎn)空間多； （3）散列函數(shù)的構(gòu)造原則：運(yùn)算盡量簡單，而且所占用空間均勻分布； （4）不同的關(guān)鍵字值可能得到相同的函數(shù)值，即可能有沖突產(chǎn)生。,3 散列查找,由此可見：散列查找必須解決兩個問題： （1）構(gòu)造一個盡量簡單但沖突少、“均勻”的“好”散列函數(shù)； （2）正視而且必須解決面臨的“地址沖突”問題。 可見：實(shí)際上第一個問題包容了第二個問題。因?yàn)橐粋€“優(yōu)秀的”散列函數(shù)必須解決地址沖突問題。 所以只要解決了第一個問題即可解決第二個問題。給出較好的散列函數(shù)是由HASH給出的，故散列查找又稱HASH查找。,3 散列查找,【例】11個元素的關(guān)鍵碼分別為 18，27，1，20，22，6，10，13，41，15，25。選取關(guān)鍵碼與元素位置間的函數(shù)為 f(key)=key mod 11 1. 通過這個函數(shù)對11個元素建立查找表如下： 0 1 2 3 4 5 6 7 8 9 10 2. 查找時，對給定值kx依然通過這個函數(shù)計算出地址，再將kx與該地址單元中元素的關(guān)鍵碼比較，若相等，查找成功。,22 | 1 | 13 | 25 | 15 | 27 | 6 | 18 | 41 | 20 | 10,哈希表與哈希方法： 選取某個函數(shù)H，依該函數(shù)按關(guān)鍵碼計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值kx計算地址，將kx與地址單元中元素關(guān)鍵碼進(jìn)行比，確定查找是否成功，這就是哈希方法(雜湊法)； 哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))； 按這個思想構(gòu)造的表稱為哈希表(雜湊表)。,哈希查找的基本思想：在記錄的存儲地址和它的關(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)鍵字,哈希表應(yīng)用哈希函數(shù)，由記錄的關(guān)鍵字確定記錄在表中的地址，并將記錄放入此地址，這樣構(gòu)成的表叫 哈希查找又叫散列查找，利用哈希函數(shù)進(jìn)行查找的過程叫,以編號作關(guān)鍵字， 構(gòu)造哈希函數(shù)：H(key)=key H(1)=1 H(2)=2,以地區(qū)別作關(guān)鍵字，取地區(qū) 名稱第一個拼音字母的序號 作哈希函數(shù)：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,從例子可見： 哈希函數(shù)只是一種映象，所以哈希函數(shù)的設(shè)定很靈活，只要使任何關(guān)鍵字的哈希函數(shù)值都落在表長允許的范圍之內(nèi)即可 沖突：key1key2，但H(key1)=H(key2)的現(xiàn)象叫 同義詞：具有相同函數(shù)值的兩個關(guān)鍵字，叫該哈希函數(shù)的 哈希函數(shù)通常是一種壓縮映象，所以沖突不可避免，只能盡量減少；同時，沖突發(fā)生后，應(yīng)該有處理沖突的方法,哈希函數(shù)的構(gòu)造方法 1、直接定址法 構(gòu)造：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)作哈希地址，即H(key)=key 或 H(key)=akey+b 特點(diǎn) 直接定址法所得地址集合與關(guān)鍵字集合大小相等，不會發(fā)生沖突 實(shí)際中能用這種哈希函數(shù)的情況很少,2、數(shù)字分析法 構(gòu)造：對關(guān)鍵字進(jìn)行分析，取關(guān)鍵字的若干位或其組合作哈希地址 適于關(guān)鍵字位數(shù)比哈希地址位數(shù)大，且可能出現(xiàn)的關(guān)鍵字事先知道的情況,例 有80個記錄，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為2位十進(jìn)制數(shù),分析： 只取8 只取1 只取3、4 只取2、7、5 數(shù)字分布近乎隨機(jī) 所以：取任意兩位或兩位 與另兩位的疊加作哈希地址,3、平方取中法 構(gòu)造：取關(guān)鍵字平方后中間幾位作哈希地址 適于不知道全部關(guān)鍵字情況 折疊法 構(gòu)造：將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的疊加和（舍去進(jìn)位）做哈希地址 種類 移位疊加：將分割后的幾部分低位對齊相加 間界疊加：從一端沿分割界來回折送，然后對齊相加 適于關(guān)鍵字位數(shù)很多，且每一位上數(shù)字分布大致均勻情況,例 關(guān)鍵字為 ：0442205864，哈希地址位數(shù)為4,4、除留余數(shù)法 構(gòu)造：取關(guān)鍵字被某個不大于哈希表表長m的數(shù)p除后所得余數(shù)作哈希地址，即H(key)=key MOD p，pm 特點(diǎn) 簡單、常用，可與上述幾種方法結(jié)合使用 p的選取很重要；p選的不好，容易產(chǎn)生同義詞 5、隨機(jī)數(shù)法 構(gòu)造：取關(guān)鍵字的隨機(jī)函數(shù)值作哈希地址，即H(key)=random(key) 適于關(guān)鍵字長度不等的情況,選取哈希函數(shù)，考慮以下因素： 計算哈希函數(shù)所需時間 關(guān)鍵字長度 哈希表長度（哈希地址范圍） 關(guān)鍵字分布情況 記錄的查找頻率,3.2 處理沖突的方法 開放定址法 方法：當(dāng)沖突發(fā)生時，形成一個探查序列；沿此序列逐個地址探查，直到找到一個空位置（開放的地址），將發(fā)生沖突的記錄放到該地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1) 其中：H(key)哈希函數(shù) m哈希表表長 di增量序列 分類 線性探測再散列：di=1,2,3,m-1 二次探測再散列：di=1,-1,2,-2,3,k(km/2) 偽隨機(jī)探測再散列：di=偽隨機(jī)數(shù)序列,例 表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄， H(key)=key MOD 11,現(xiàn)有第4個記錄，其關(guān)鍵字為38， 按三種處理沖突的方法，將它填入表中,(1) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5+2) MOD 11=7 沖突 H3=(5+3) MOD 11=8 不沖突,38,(2) H(38)=38 MOD 11=5 沖突 H1=(5+1) MOD 11=6 沖突 H2=(5-1) MOD 11=4 不沖突,38,(3) H(38)=38 MOD 11=5 沖突 設(shè)偽隨機(jī)數(shù)序列為9，則： H1=(5+9) MOD 11=3 不沖突,38,再哈希法 方法：構(gòu)造若干個哈希函數(shù)，當(dāng)發(fā)生沖突時，計算下一個哈希地址，即：Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函數(shù) 特點(diǎn)：計算時間增加 鏈地址法 方法：將所有關(guān)鍵字為同義詞的記錄存儲在一個單鏈表中，并用一維數(shù)組存放頭指針,例 已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函數(shù)為：H(key)=key MOD 13, 用鏈地址法處理沖突,3.3 哈希查找過程及分析 哈希查找過程,哈希查找分析 哈希查找過程仍是一個給定值與關(guān)鍵字進(jìn)行比較的過程 評價哈希查找效率仍要用ASL 哈希查找過程與給定值進(jìn)行比較的關(guān)鍵字的個數(shù)取決于： 哈希函數(shù) 處理沖突