一、查找的基本概念

ps：查找表可以是線性結(jié)構(gòu)、樹狀結(jié)構(gòu)、圖狀結(jié)構(gòu)等等

評價(jià)一個(gè)查找算法的優(yōu)劣：主要看算法的平均查找長度ASL

舉個(gè)例子，我們現(xiàn)在有如下二叉排序樹

如果你要查的是50，那么從根節(jié)點(diǎn)出發(fā)只需要對比一次關(guān)鍵字就可以了，所以第一項(xiàng)是1 * 1

如果你要查的是第二層的26或者66，你找26總共需要進(jìn)行兩輪對比，找66又需要兩輪對比，所以查第二層元素共需要是2 * 2次對比

第三層同理，長度為3，共4個(gè)數(shù)據(jù)，所以3 * 4

第四層同理，長度為4，共1個(gè)數(shù)據(jù)，所以4 * 1

然后累和除8，這里8是指一共8個(gè)數(shù)據(jù)，平均到每個(gè)數(shù)據(jù)身上是1/8

我們之前還討論過二叉排序樹查找失敗的情況，所以在評價(jià)一個(gè)查找算法的查找效率時(shí)，我們通常會(huì)分開考慮查找成功和查找失敗兩種情況下的平均查找長度

比如同樣的二叉排序樹，查找成功和查找失敗的ASL是不同的：

ASL的數(shù)量級可以直接反映出你的查找算法的時(shí)間復(fù)雜度
ASL的計(jì)算也是考研中的重點(diǎn)，請務(wù)必掌握

二、順序查找和折半查找

2.1順序查找

順序查找顧名思義，就是按照順序一個(gè)個(gè)找，你可以從前往后，也可以從后往前。這個(gè)是最無腦的查找。

代碼如下：

typedef struct{//查找表的數(shù)據(jù)結(jié)構(gòu)（順序表）
    ElemType *elem;//動(dòng)態(tài)數(shù)組基址
    int TableLen;//表的長度
}SSTable;

//順序查找
int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0;i<ST.TableLen&&ST.elem[i]!=key;i++);
    //查找成功，則返回元素下標(biāo)，查找失敗則返回-1
    return i==ST.TableLen?-1:i;
}

還有一種順序查找就是帶哨兵位的，也就是0號位置空出來，放你要找的那個(gè)東西

這種哨兵就是從后往前找，如果找到哨兵的下標(biāo)，也就是這里的0，就說明查找失敗了。

我們前面說過，當(dāng)我們在評價(jià)一個(gè)查找算法時(shí)，我們通常是算它的平均查找長度ASL。而平均查找長度又分為查找成功和查找失敗兩種情況。

查找成功情況：
如果是帶哨兵的實(shí)現(xiàn)方式，我們是從最后的位置開始往前掃描。

如果是找最后一個(gè)關(guān)鍵字，那你所需要對比關(guān)鍵字的次數(shù)就是1。
如果假設(shè)我們找任何一個(gè)關(guān)鍵字概率都是相同的，那么找最后一個(gè)關(guān)鍵字的概率就是1/n
查找長度為1 * (1/n)

如果是找倒數(shù)第二個(gè)關(guān)鍵字，那要對比關(guān)鍵字次數(shù)就是2
查找長度為2 * (1/n)

下面以此類推…

如果是查找失敗，那就是把所有的n個(gè)元素對比完了，還要再和哨兵對比一下。

總之，不管是查找成功還是查找失敗，時(shí)間復(fù)雜度都是O（n）

順序查找的優(yōu)化（對有序表）
如果要查的表本來就是有序的，那我們查找可以進(jìn)一步優(yōu)化

舉個(gè)例子
你要在如下的順序表中進(jìn)行查找21的操作

其實(shí)不用遍歷完所有元素，當(dāng)你遍歷到29發(fā)現(xiàn)還沒找到21，就已經(jīng)可以不用找了，因?yàn)楹竺嫒潜?1大的元素。

順序查找的優(yōu)化（被查概率不相等情況）
如果是被查概率不同的，我們可以把被查找概率更大的元素放在查找相對靠前的位置

如果采取這種策略，可以減少查找成功的平均查找長度
但是對于查找失敗的情況，我們只能從頭掃到尾，來確定是不是查找失敗。
所以，如果你實(shí)際運(yùn)用中如果查找成功更多，用這種方法會(huì)更好一些。

2.3折半查找

2.3.1算法思想

折半查找又稱為二分查找，它只適用于有序的順序表

先看一個(gè)查找成功的例子：
比如現(xiàn)在要在下面的順序表中找33
我們會(huì)先用兩個(gè)指針low和high分別指向我們目前要搜索的區(qū)間范圍

第一輪要檢查的元素是low和high中間的一個(gè)元素，我們用指針mid來指向它
mid的計(jì)算方式也很簡單，就是（low+high）/2
比如這里high=10，low=0，mid=（low+high）/2=5

所以我們第一輪要檢查的元素就是29,對比mid指向的元素29和我們要查的33
發(fā)現(xiàn)29<33，如果33存在，那么肯定是在我們mid的右邊

low=mid+1，
mid=（low+high）/2

第二輪
對比mid指向的元素37和要查找的元素33
33<37，如果33存在，那應(yīng)該在mid左邊

high=mid-1
mid=(low+high)/2

第三輪
對比mid指向的元素32和要查找的元素33
32<33
那么33肯定在mid右邊
low=mid+1
mid=(low+high)/2

下一輪檢查發(fā)現(xiàn)剛好mid指向值等于33，那么查找成功。

再看一個(gè)查找失敗的例子：

還是剛才那個(gè)表，我們現(xiàn)在要查找一個(gè)不存在的元素12

剛開始還是一樣的，low和high指向順序表開頭和結(jié)尾元素
mid=（low+high）/2

第一輪對比，12<29，那么12只會(huì)出現(xiàn)在mid左邊

第二輪對比12<13，如果存在只會(huì)在mid左邊

第三輪對比，7<12，如果存在，12在mid右邊


第四輪對比，10<12，如果存在，12在mid右邊

此時(shí)出現(xiàn)了low>high的情況，那么查找失敗

2.3.2代碼實(shí)現(xiàn)

typedef struct{//查找表的數(shù)據(jù)結(jié)構(gòu)
    ElemType *elem;//動(dòng)態(tài)數(shù)組的基址
    int TableLen;//表的長度
}SSTable;

//折半查找-升序（降序需要對下面的判斷條件進(jìn)行相應(yīng)更改）
int Binary_Search(SSTable L,ElemType key){
    int low=0,high=L.TableLen-1,mid;
    while(low<=high){
       mid=(low+high)/2;
       if(L.elem[mid]==key)
          return mid;
       else if(L.elem[mid]>key)
          high=mid-1;
       else
          low=mid+1;
    }
    return -1;
}

2.3.3查找效率分析

2.3.4折半查找判定樹的構(gòu)造

考研中還是比較喜歡喜歡考察折半查找判斷樹的構(gòu)造，下面我們來進(jìn)行介紹

2.3.5折半查找效率

2.3.6小結(jié)

ps：只能說大部分情況折半查找比順序查找效率更高。
因?yàn)槿绻阋榈脑鼐褪琼樞虮淼谝粋€(gè)元素，順序查找是要更快的。

2.4分塊查找

分塊查找我們主要是介紹算法思想，考試中很少考代碼題，大家會(huì)用手算模擬即可。

比如下面這個(gè)數(shù)組，看起來元素都是亂的

如果仔細(xì)觀察，我們可以把這些元素分成一個(gè)個(gè)小區(qū)間
第一個(gè)區(qū)間：<=10
第二個(gè)區(qū)間：<=20
第三個(gè)區(qū)間：<=30
…

如果單獨(dú)看元素是亂序的，但是如果我們把它們分成一個(gè)個(gè)小區(qū)間后，可以發(fā)現(xiàn)各個(gè)區(qū)間之間其實(shí)是有序的，我們可以給這個(gè)查找表建立上一級索引。

看上圖，很好理解。索引表中保存的是每一個(gè)分塊中最大的關(guān)鍵字，還有分塊的存儲區(qū)間。

比如說我們索引表中有個(gè)30，那就說明其中出現(xiàn)最大的關(guān)鍵字是30，然后這個(gè)分塊的存儲區(qū)間是6-8，也就是第三個(gè)分塊下標(biāo)起始到末尾是6到8

所以分塊查找的特點(diǎn)：快內(nèi)無序，快間有序

該索引表數(shù)據(jù)結(jié)構(gòu)如下：

//索引表
typedef struct{
    ElemType maxValue;//每個(gè)表項(xiàng)最大關(guān)鍵字
    int low,high;//分塊的區(qū)間范圍
}Index;

//順序表存儲實(shí)際元素
ElemType List[100];

先來看一個(gè)查找成功的例子：
比如現(xiàn)在查22

先查找索引表，從索引表第一個(gè)元素依次往后找，
第一個(gè)元素10<22，繼續(xù)往下
第二個(gè)元素20<22，繼續(xù)往下
第三個(gè)元素30>=22，如果22存在，一定在此區(qū)間
接下來就從分塊的起始位置，也就是6號下標(biāo)往8號下標(biāo)里找
我們在7號下標(biāo)找到22

再來看一個(gè)查找失敗的例子：
現(xiàn)在要查29，依次遍歷索引表，確定如果29存在是在第三個(gè)分塊內(nèi)

然后我們從第三個(gè)分塊開始查找，第一個(gè)27不滿足

第二個(gè)22不滿足

第三個(gè)30不滿足

再往后，發(fā)現(xiàn)已經(jīng)超出第三個(gè)分塊范圍了，就說明29不存在

剛才在查找索引表時(shí)，我們是按順序查找的方式，也就是從索引表的第一個(gè)元素一個(gè)個(gè)往后找

但是由于索引表中保存的元素是有序的，并且我們索引表是用數(shù)組的方式，也就是順序存儲的方式來實(shí)現(xiàn)的。所以，針對索引表，我們可以采用折半查找，而對每個(gè)分塊內(nèi)的元素（亂序），只能順序查找。

ps：分塊查找又稱為索引順序查找，先索引表，然后順序查找分塊內(nèi)元素嘛

三、樹形查找

3.1二叉排序樹

3.1.1二叉排序樹定義

二叉樹又稱二叉查找樹BST
二叉排序樹的左子樹結(jié)點(diǎn)值<根節(jié)點(diǎn)值<右子樹值，如果用中序遍歷（左根右），就可以得到一個(gè)遞增的序列。

二叉排序樹的左子樹和右子樹也是一棵二叉排序樹

3.1.2查找操作

先看一個(gè)查找成功的例子：
假設(shè)我們現(xiàn)在要在一棵二叉排序樹上找30

從19出發(fā)，19<30，如果30存在，則在19的右子樹

50>30，如果30存在，則在50的左子樹

26<30，如果30存在，則在26的右子樹

成功找到30

再看一個(gè)查找失敗的例子：
比如現(xiàn)在要查12

從19出發(fā)，如果12存在，則在19左子樹

13>12，如果12存在，則在13左子樹

11<12，如果12存在則在11右子樹

但是我們發(fā)現(xiàn)，11沒有右子樹了，說明查找失敗了

查找代碼如下：

//二叉排序樹結(jié)點(diǎn)
typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

//在二叉排序樹中查找值為key的結(jié)點(diǎn)
BSTNode *BST_Search(BSTree T,int key){
    while(T!=NULL&&key!=T->key){//若樹空或等于根節(jié)點(diǎn)值，則結(jié)束循環(huán)
        if(key < T->key){
           T=T->lchild;//key小于當(dāng)前值，如果key存在，在左子樹上
		}
		else{
		   T=T->rchild;//key大于當(dāng)前值，如果key存在，在右子樹上
		}
    }
    return T;
}

上面的算法是用一個(gè)while循環(huán)，來找到目標(biāo)結(jié)點(diǎn)（非遞歸）

下面的算法則是由于二叉排序樹的遞歸特性，我們用遞歸來實(shí)現(xiàn)（遞歸）

//在二叉排序樹中查找值為key的結(jié)點(diǎn)（遞歸實(shí)現(xiàn)）
BSTNode *BSTSearch(BSTree T,int key){
   if(T==NULL){
	 return NULL;//查找失敗
   }
   if(key==T->key){
	 return T;//查找成功
   }
   else if(key < T->key){
	 return BSTSearch(T->lchild,key);//在左子樹查找
   }
   else{
     return BSTSearch(T->rchild,key);//在右子樹查找
   }
}

如果采用非遞歸

顯然，如果采用非遞歸算法，我們只需要常數(shù)級的輔助空間。非遞歸實(shí)現(xiàn)空間復(fù)雜度為O（1）

但是如果用遞歸實(shí)現(xiàn)的話，一棵樹有多高，它就有可能要往下遞歸幾次。而每次遞歸都需要在函數(shù)調(diào)用棧中分配一片空間。遞歸實(shí)現(xiàn)空間復(fù)雜度為O（h）

3.1.3插入操作

對于插入操作，插入新結(jié)點(diǎn)后，我們也需要保證二叉排序樹的一個(gè)特性，所以我們首先也需要用到查找操作的那種邏輯找到我們應(yīng)該插入的具體位置。

比如我們現(xiàn)在要插入12這個(gè)數(shù)據(jù)

12<19，應(yīng)該插到12左子樹

12<13，應(yīng)該插到13的左子樹

12>11，應(yīng)該插到11的右子樹


需要注意，如果我們要插入的這個(gè)關(guān)鍵字本來就存在了，那么不該再插入值重復(fù)的結(jié)點(diǎn)了。另外，每次插入的新結(jié)點(diǎn)必定會(huì)成為一個(gè)葉子結(jié)點(diǎn)。

我們這里采用的是遞歸實(shí)現(xiàn)，所以這種算法的最壞空間復(fù)雜度為O(h)，h為樹的高度

顯然，插入操作也可以用循環(huán)的方式來實(shí)現(xiàn)，也就是用非遞歸的方式實(shí)現(xiàn)，非遞歸算法空間復(fù)雜度會(huì)更低一些。這個(gè)大家自己去練習(xí)

3.1.4二叉排序樹的構(gòu)造

其實(shí)就是不斷插入結(jié)點(diǎn)的過程，插入結(jié)點(diǎn)你調(diào)用剛才介紹的插入函數(shù)就行了

//按照str[]中的關(guān)鍵字序列建立二叉排序樹
void Create_BST(BSTree &T,int str[],int n){
    T=NULL;//初始時(shí)T為空樹
    int i=0;
    while(i<n){//依次將每個(gè)關(guān)鍵字插入到二叉排序樹中
	    BST_Insert(T,str[i]);
	    i++;
	}
}

同樣的數(shù)據(jù)，如果我們把插入順序換一下，也會(huì)得到不同的二叉排序樹


這也是一個(gè)?？嫉膬?nèi)容，就是給你一個(gè)二叉排序樹序列，讓你構(gòu)造一個(gè)二叉排序樹。

3.1.5二叉排序樹的刪除

也就是要?jiǎng)h除某個(gè)指定值的結(jié)點(diǎn)，那第一步肯定是要找到那個(gè)要?jiǎng)h除的結(jié)點(diǎn)。
接下來要分下面幾種情況：

1.要?jiǎng)h除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)

刪除葉子結(jié)點(diǎn)后依然可以保證二叉排序樹的特性，你直接刪就行了

2.要?jiǎng)h除的結(jié)點(diǎn)只有左子樹或者右子樹

比如13這個(gè)結(jié)點(diǎn)，它只有左子樹，那你把13刪了之后，
把原先13的左孩子接到原先13的位置就行了。


3.要?jiǎng)h除的結(jié)點(diǎn)有左子樹，有右子樹

比如50這個(gè)結(jié)點(diǎn)

你要?jiǎng)h50，還得保證刪除50后的二叉排序樹還是一棵二叉排序樹

法1：從要?jiǎng)h除的結(jié)點(diǎn)的右子樹中，找出一個(gè)最小的結(jié)點(diǎn)——右子樹中最左邊的結(jié)點(diǎn)

所以，如果要?jiǎng)h50，我們可以把50右子樹中的最小結(jié)點(diǎn)60換上來，如下圖：

法2：從要?jiǎng)h除的結(jié)點(diǎn)的左子樹中，找出一個(gè)最大的結(jié)點(diǎn)——左子樹中最右邊的結(jié)點(diǎn)

所以，要?jiǎng)h50，我們可以讓50左子樹中最大結(jié)點(diǎn)30換上來

3.1.6查找效率分析

3.1.7小結(jié)

3.2平衡二叉樹的插入

3.2.1引子

我們在上小節(jié)說過，如果要讓二叉排序樹保持平衡，就可以保證這棵二叉排序樹的查找效率可以達(dá)到O（Log₂n）這個(gè)數(shù)量級

那我們下面要研究的就是，如何在插入一個(gè)新結(jié)點(diǎn)后保持二叉樹的平衡？

如下圖，我們插入67這個(gè)結(jié)點(diǎn)后，這個(gè)新插入結(jié)點(diǎn)的所有祖先的平衡因子都受到了影響：

要讓新插入結(jié)點(diǎn)后的二叉樹恢復(fù)平衡的方法：我們從新插入的結(jié)點(diǎn)往上找，找到第一個(gè)不平衡結(jié)點(diǎn)。在上圖中就是70這個(gè)結(jié)點(diǎn)。

我們把以70為根的這棵子樹稱為最小的不平衡子樹
為什么稱為最?。恳?yàn)槟闳绻麖?0繼續(xù)往上找，66為根的子樹也是不平衡的，但是70為根的樹是60為根的樹的子樹，所以70為根的子樹是最小的不平衡子樹。

所以，我們只要調(diào)整最小的不平衡子樹就可以了。調(diào)整效果如下：

下面我們就是討論如何調(diào)整最小的不平衡子樹，讓它恢復(fù)平衡

3.2.2LL

在A結(jié)點(diǎn)的左孩子的左子樹中插入了一個(gè)新結(jié)點(diǎn)導(dǎo)致不平衡

我們用一些方形的框來抽象的表示各個(gè)部分子樹，H表示子樹的高度
（當(dāng)前各個(gè)子樹是平衡的）

現(xiàn)在在B結(jié)點(diǎn)的左子樹插入了一個(gè)新結(jié)點(diǎn)，導(dǎo)致了A結(jié)點(diǎn)不平衡。其實(shí)就是因?yàn)锽結(jié)點(diǎn)的左子樹長高了。

原先A左子樹高度為H+1，現(xiàn)在左子樹長高1，那么左子樹高度變?yōu)镠+2

但是A右子樹高度還是H，則A平衡因子變成了（H+2）-（H）=2，也就是A不平衡了

可能有同學(xué)會(huì)問：“你憑啥就認(rèn)為A右子樹高度是H，我認(rèn)為A右子樹高度為H+1，一開始A這個(gè)樹不也是平衡的嗎？”

解釋如下：
如果A右子樹高度為H+1，那么A原本平衡因子應(yīng)該是0，你左邊是H+1，右邊也是H+1嘛。然后你

你要是設(shè)一開始A右子樹高度是H+1。那么你A左子樹左孩子高度+1，A左子樹高度其實(shí)就變成了H+2。A的平衡因子是（H+2）-（H+1）=1，其實(shí)這還是平衡的。

但是我們討論的是加了結(jié)點(diǎn)后不平衡的情況，所以這種情況不考慮。

有同學(xué)又要問了：“A右子樹高度是H+1不可以，A右子樹高度為H-1可以不”

這其實(shí)也是不可以的，因?yàn)槟阕笞訕涓叨仁荋+1，你右子樹高度是H-1，那么一開始就是不平衡的。

我們要求的是一開始平衡，加了個(gè)結(jié)點(diǎn)之后不平衡。所以這種情況也不可以。

有同學(xué)又要問了：“那我一開始設(shè)B的右子樹高度為H-1可以不？”

如果是這樣的話，那么B一開始的平衡因子是（H）-（H-1）=1，

你在B左子樹上高度+1，那么B左子樹高度就變成了H+1，B右子樹高度還是H-1，B的平衡因子就變成了（H+1）-（H-1）=2，那么B就成了最小不平衡子樹了。

我們要探討的是A是最小不平衡子樹，所以B的右子樹高度也只能是H

下面回到主線劇情，如何調(diào)整這個(gè)最小的不平衡子樹
那調(diào)整后我們要得到的樹需要滿足：1.恢復(fù)平衡，2仍然是一棵二叉排序樹

顯然，B左子樹的值<B<B右子樹的值<A<A右子樹的值

那我們具體做法，就是讓B結(jié)點(diǎn)右上旋轉(zhuǎn)，代替A成為根結(jié)點(diǎn)，
然后A結(jié)點(diǎn)要成為B的右子樹的根節(jié)點(diǎn)，也就是A要成為B的右孩子

然后BL<B，所以只能把BL放B左邊

BR原先在B右邊的，但是你B右邊已經(jīng)掛了A了，所以BL不能掛B右邊了
BL原先是在A左邊，也就是BL<A,我們把BL放A左邊

AR>A，然后以前的AR繼續(xù)掛A右邊就行了

這樣我們就可以讓加入結(jié)點(diǎn)后不平衡的的子樹繼續(xù)平衡，且保證二叉排序樹的特性。

LL小結(jié)：在A左孩子的左子樹插入一個(gè)新結(jié)點(diǎn)導(dǎo)致不平衡，我們采用A左孩子右旋一次

3.2.3RR

如果在A的右孩子的右子樹加入一個(gè)結(jié)點(diǎn)導(dǎo)致不平衡
（我們這里也是假設(shè)了在進(jìn)行加結(jié)點(diǎn)操作后，A是最小的不平衡子樹，所以AL=BL=BR=H）

對于這種情況，我們采用的是左旋一次

也就是讓B左上旋轉(zhuǎn)，讓A左下旋轉(zhuǎn)
B變成根，A變成B左孩子

然后就是把剩余的AL,BL,BR掛上去

BR是大于B的，我們放B右邊

AL是小于A的，我們放A左邊即可

還剩一個(gè)BL，BL小于B但是大于A，我們就放A右邊就行

RR小結(jié)：在A右孩子的右子樹插入一個(gè)新結(jié)點(diǎn)導(dǎo)致不平衡，我們采用A右孩子左旋一次

LL和RR的代碼思路

3.2.4LR

LR就是在A結(jié)點(diǎn)的左孩子的右子樹插入一個(gè)結(jié)點(diǎn)導(dǎo)致A結(jié)點(diǎn)變成最小不平衡子樹的根節(jié)點(diǎn)

為了方便討論，我們需要把BR進(jìn)行展開。我們假設(shè)B的右孩子是叫C的結(jié)點(diǎn)，C的左子樹稱為CL，右子樹稱為CR。由于B右子樹整個(gè)高度是H，所以CL和CR高度我們可以假設(shè)H-1

那么現(xiàn)在C這個(gè)子樹長高了，我們可以假設(shè)把新結(jié)點(diǎn)插入在CR，導(dǎo)致CR高度為H
你假設(shè)插在CL也是一樣的，處理方法都一樣

對于這種情況，我們要先讓C左旋頂替B的位置；接下來再讓C右旋頂替A的位置

如何把結(jié)點(diǎn)左旋/右旋，方法和前面講LL和RR是一樣的

首先是讓C左旋替代B，B<C,那么B成為C的左孩子

然后由于BL<B,所以BL在B左邊

CR>C,就放C右邊

B<CL<C，就放B右邊

所以，把C左旋后如下圖，但是此時(shí)A仍然不平衡

接下來就是把C右旋替換A的位置
就是把C右孩子變成A左孩子，
A變成C右孩子


LR小結(jié)：在A左孩子的右子樹插入一個(gè)新結(jié)點(diǎn)導(dǎo)致不平衡，我們采用A左孩子的右孩子左旋一次，再右旋一次

3.2.5RL

最后RL思路同理LR
RL小結(jié)：在A右孩子的左子樹插入一個(gè)新結(jié)點(diǎn)導(dǎo)致不平衡，我們采用A右孩子的左孩子右旋一次，再左旋一次

3.2.5小結(jié)

3.3平衡二叉樹的刪除

平衡二叉樹的第一個(gè)特性就是具有排序樹的特性，也就是左<中<右

第二個(gè)特性就是：在二叉排序的基礎(chǔ)上，要保證每個(gè)結(jié)點(diǎn)都是平衡的，也就是左右子樹高度之差不超過1

在上一節(jié)介紹二叉排序樹插入一個(gè)結(jié)點(diǎn)導(dǎo)致不平衡的四種情況如何解決。
該小節(jié)則是介紹二叉排序樹刪除一個(gè)結(jié)點(diǎn)導(dǎo)致不平衡的四種情況如何解決。
這四種情況和上節(jié)對應(yīng)，依然是LL，RR，LR，RL

先來看一下刪除的規(guī)則，具體怎么用我們下面會(huì)舉例給大家詳細(xì)講解：

對于5.不平衡向上傳導(dǎo)，如果出現(xiàn)這種情況那么題目給的樹就一定非常復(fù)雜，并且會(huì)出現(xiàn)多種解決方案，解題過于繁瑣，所以考試中百分之99是不會(huì)考的，我們這里只介紹一些較為簡單的例子

例1：現(xiàn)在刪除下面樹的9

單純刪除結(jié)點(diǎn)操作和二叉排序樹是一樣的，由于9這個(gè)階段是葉子結(jié)點(diǎn)，我們直接刪除就可以了。

接下來要判斷，刪除這個(gè)元素之后，它上面的祖先結(jié)點(diǎn)有沒有出現(xiàn)不平衡的現(xiàn)象。
所以下面要做的就是“一路向北”，一路向上看是否有不平衡子樹出現(xiàn)，如果沒有不平衡子樹，那么就可以結(jié)束算法了。

刪除9之后，對于13，平衡因子是-1，仍然平衡

對于25，平衡因子是1，仍然平衡

對于50，平衡因子是-1，仍然平衡

這就說明，剛才的刪除操作并沒有導(dǎo)致它的任何一個(gè)祖先出現(xiàn)不平衡現(xiàn)象，到此為止，刪除操作結(jié)束。

例2：現(xiàn)在刪除下面樹的55

55這個(gè)結(jié)點(diǎn)是二叉排序樹的葉子，我們可以直接刪掉

接下來就是要看55的祖先有沒有出現(xiàn)不平衡的現(xiàn)象

那么我們可以發(fā)現(xiàn)，55刪了之后，75是出現(xiàn)了不平衡現(xiàn)象，平衡因子-2

由于產(chǎn)生了不平衡現(xiàn)象，我們就要進(jìn)入第三步，找到最小不平衡子樹下，個(gè)頭最高的兒子、孫子

75有兩個(gè)兒子，60高度為1，80高度為3，所以最高的兒子是80

再從最高的兒子往下找最高的孫子，77高度為1,90高度為2，所以最高的孫子是90

接下來進(jìn)入第四步，根據(jù)孫子位置，調(diào)整平衡

顯然，孫子是在爺爺RR的位置，也就是90在75RR的位置

當(dāng)孫子在RR的位置，我們就是要讓兒子左旋一次
左旋右旋在上節(jié)平衡二叉樹講過了，忘記了自己去回顧一下

下面就是讓80左旋到75的位置

接下來第五步需要檢查不平衡是否向上傳導(dǎo)
考試基本不可能出現(xiàn)向上傳導(dǎo)的情況，我們這里是為了介紹，防止大家有疑問。

什么叫檢查不平衡向上傳導(dǎo)？在調(diào)整平衡前，這個(gè)不平衡的子樹高度是4

調(diào)整后原先那棵不平衡子樹高度從4變成了3

而這棵子樹高度出現(xiàn)變化，就有可能導(dǎo)致它上面的樹也產(chǎn)生不平衡。這就是所謂的不平衡向上傳導(dǎo)。
顯然這里是沒有出現(xiàn)不平衡向上傳導(dǎo)的。

例3：現(xiàn)在刪除下面樹的32

首先根據(jù)二叉排序樹的刪除方法進(jìn)行操作，32是葉子結(jié)點(diǎn)我們可以直接刪除

刪除32之后，可以發(fā)現(xiàn)44是出現(xiàn)了不平衡現(xiàn)象

找到了最小不平衡子樹，接下來就是找最高的兒子和孫子
可以確定78是最高的兒子，50是最高的孫子

然后50是44的RL，那我們就讓50右旋再左旋

發(fā)現(xiàn)沒有出現(xiàn)不平衡向上傳導(dǎo)，刪除操作結(jié)束

（基本不可能考不平衡向上傳導(dǎo)，如果你感興趣可以自己去研究，會(huì)發(fā)現(xiàn)如果出現(xiàn)不平衡向上傳導(dǎo)，那個(gè)樹將非常非常復(fù)雜，并且答案有很多種。我這里就介紹考試會(huì)考的幾個(gè)例子）

當(dāng)然會(huì)有人好奇，出現(xiàn)不平衡向上傳導(dǎo)的例子，就比如下面的樹，要?jiǎng)h除32
有時(shí)間，感興趣自己研究

四、B樹和B+樹

4.1B樹

考試中對B樹的考察一般側(cè)重考性質(zhì)、插入、刪除、查找操作，代碼基本不會(huì)出現(xiàn)。

所以我們下面將重點(diǎn)介紹B樹的性質(zhì)還有手算方法。

先來回顧一下我們前面學(xué)的二叉查找樹，也叫二叉排序樹的特點(diǎn)。

如果我們要查的目標(biāo)比當(dāng)前結(jié)點(diǎn)值更小，我們會(huì)往左子樹這邊查找，如果比當(dāng)前結(jié)點(diǎn)更大，就往右子樹查找。

所以二叉查找樹無非就是用一個(gè)關(guān)鍵字，把一個(gè)我們有可能搜索到的目標(biāo)關(guān)鍵字范圍分割成兩份。

比如剛開始我們要搜索的范圍是(-∞，∞)，
那么根結(jié)點(diǎn)29就把(-∞，∞)劃分為了(-∞，29)和(29，∞)

(-∞，29)就去左子樹找，(29，∞)就去右子樹找

問題來了：能否把二叉查找樹拓展成m叉查找樹？

舉個(gè)例子：現(xiàn)在有圖示的5叉查找樹

其實(shí)我們雖然把它拓展成了5叉查找樹，但是原理和2叉查找樹一樣的。

第一個(gè)根節(jié)點(diǎn)是22
如果當(dāng)前要查找的元素比22小，就往左走
如果當(dāng)前要查找的元素比22大，就往右走

假設(shè)我們要找的那個(gè)值比22更大，接下來就應(yīng)該在22的右子樹去找，即(29，∞)里面找

往下找發(fā)現(xiàn)當(dāng)前結(jié)點(diǎn)又出現(xiàn)了兩個(gè)關(guān)鍵字：36和45，
就相當(dāng)于我們在這個(gè)區(qū)間內(nèi)又插入了兩個(gè)隔板。又把(29，∞)劃分為3個(gè)區(qū)間
(29，36)、(36，45)、(45，∞)

綜上，5叉排序樹里面這些關(guān)鍵字還有關(guān)鍵字之間的指針，信息其實(shí)和二叉查找樹是非常類似的。數(shù)據(jù)結(jié)構(gòu)定義如下：

每個(gè)結(jié)點(diǎn)最多可以包含4個(gè)關(guān)鍵字，最多5個(gè)孩子，也就是5棵子樹。然后用一個(gè)num變量記錄當(dāng)前結(jié)點(diǎn)一共多少個(gè)關(guān)鍵字。

像上圖這種5叉查找樹，在一個(gè)結(jié)點(diǎn)中，我們最少可以允許有1個(gè)關(guān)鍵字，2個(gè)分叉；最多允許4個(gè)關(guān)鍵字，5個(gè)分叉
一個(gè)關(guān)鍵字會(huì)把一個(gè)查找區(qū)間分割成兩個(gè)部分

圖中給出的紫色結(jié)點(diǎn)，其是就查找失敗的情況，比如下面圈出的失敗結(jié)點(diǎn)，就是對應(yīng)的（15,22）這個(gè)范圍

下面我們進(jìn)行5叉查找樹的查找成功的舉例：

假設(shè)我們現(xiàn)在要查找9
根節(jié)點(diǎn)中第一個(gè)被保存的關(guān)鍵字是22

顯然9要比22更小，所以下面要選22左邊的路

到新的結(jié)點(diǎn)，我們會(huì)順序掃描一個(gè)結(jié)點(diǎn)中的各個(gè)關(guān)鍵字
第一個(gè)關(guān)鍵字5要比9更小，往右檢查下一個(gè)關(guān)鍵字

第二個(gè)關(guān)鍵字11又要比9大，所以9在11左邊的路線上

到了新的結(jié)點(diǎn)，我們還是一樣的從左往右依次掃描，然后掃描3次找到9

ps：剛才在查找每個(gè)結(jié)點(diǎn)中的數(shù)據(jù)時(shí)，是用的順序查找。
但是由于每個(gè)結(jié)點(diǎn)中數(shù)據(jù)是有序排放的，所以在查找每個(gè)階段數(shù)據(jù)時(shí)，你也可以用折半查找

下面我們進(jìn)行5叉查找樹的查找失敗的舉例：

比如我們要找41，現(xiàn)在從根節(jié)點(diǎn)出發(fā)

22要比41更小，我們指針右移，發(fā)現(xiàn)當(dāng)前指針?biāo)肝恢靡呀?jīng)超出這個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)了，所以如果41存在，我們應(yīng)該往回找這個(gè)指針，然后指針往下走

來到下一層結(jié)點(diǎn)，第一個(gè)元素36<41，指針往右

第二個(gè)元素45>41，如果41存在，則在45左邊的指針?biāo)附Y(jié)點(diǎn)中

到新的結(jié)點(diǎn)，第一個(gè)元素40<41，指針右移

第二個(gè)元素42要比41更大，如果41存在，則在42左邊指針指向的結(jié)點(diǎn)

但是你發(fā)現(xiàn)，如果沿著42左邊指針往下走，居然是一個(gè)失敗結(jié)點(diǎn)，那么就說明查找失敗

ps：雖說是失敗結(jié)點(diǎn)，其實(shí)就是一個(gè)NULL

剛才我們提出的5叉排序樹，我們只是規(guī)定了每一個(gè)結(jié)點(diǎn)中最多有5個(gè)分叉。

那么如果我們每個(gè)結(jié)點(diǎn)只保留一個(gè)關(guān)鍵字，也就是每個(gè)結(jié)點(diǎn)只有2個(gè)分叉的情況。

如上圖所示，這個(gè)5叉查找樹就退化成了2叉查找樹。
在這種情況下，由于每個(gè)結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量變少，
所以，如果關(guān)鍵字總數(shù)相同，這個(gè)樹會(huì)變成“細(xì)狗”，也就是又細(xì)又高的樹。
而查找樹越高，我們在進(jìn)行查找時(shí)就需要更多層的結(jié)點(diǎn)，效率也會(huì)更低

那么如何保證5叉查找樹的效率？
我們可以規(guī)定：在m叉查找樹中，除了根節(jié)點(diǎn)，其他任何一個(gè)結(jié)點(diǎn)都至少有?m/2?個(gè)分叉

比如5叉查找樹，m/2向上取整應(yīng)該是?5/2?=3
所以，對于5叉查找樹，我們可以規(guī)定每個(gè)階段至少3個(gè)分叉，也就是2個(gè)關(guān)鍵字

這樣就可以保證每個(gè)階段中關(guān)鍵字個(gè)數(shù)不會(huì)太少，就可以保證這棵樹不會(huì)變的很高，層數(shù)不會(huì)太多，相應(yīng)的查找效率也可以得到保證

這里可能大家會(huì)有疑惑，為什么除了根結(jié)點(diǎn)之外呢？我們讓根結(jié)點(diǎn)也有3個(gè)分叉不行？

想法不錯(cuò)，但是實(shí)際是做不到的。
比如現(xiàn)在5叉查找樹，剛開始只有1個(gè)元素，1個(gè)關(guān)鍵字。

那么這種情況下，就只有一個(gè)根節(jié)點(diǎn)（一個(gè)關(guān)鍵字）
就一個(gè)關(guān)鍵字，你那里來能放2個(gè)關(guān)鍵字呢？

再來看另一個(gè)問題：下面這棵二叉樹，你覺得它優(yōu)秀不？

上面這個(gè)5叉查找樹已經(jīng)滿足了我們剛才提出的特性：根節(jié)點(diǎn)除外，每個(gè)結(jié)點(diǎn)有3個(gè)或3個(gè)以上的分叉。

但是這棵樹有一個(gè)問題：它不平衡

這種不平衡的特性，顯然也會(huì)導(dǎo)致我們的5叉查找樹長的很高。

和剛才一樣，如果樹長得太高，就會(huì)導(dǎo)致我們查找的過程中要查很多層的結(jié)點(diǎn)，從而導(dǎo)致效率降低。

我們可以規(guī)定：對于每個(gè)結(jié)點(diǎn)，它的左右子樹高度都相同

如果能做到各個(gè)結(jié)點(diǎn)的子樹都沒有高度差，就可以保證我們的多叉查找樹是平衡的，也就保證了它不會(huì)有太多層，從而保證查找效率。

如果能滿足上面提到的兩個(gè)策略，那么就是B樹

我們通常會(huì)把失敗結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，而最下面一層含有實(shí)際數(shù)據(jù)的結(jié)點(diǎn)，我們稱為終端結(jié)點(diǎn)。

注：由于平衡要求，我們是讓樹中所有結(jié)點(diǎn)子樹高度都相同。那么就會(huì)導(dǎo)致，失敗結(jié)點(diǎn)（葉子結(jié)點(diǎn)）一定會(huì)出現(xiàn)在最下層（同一層）

B樹中所有結(jié)點(diǎn)孩子個(gè)數(shù)的最大值稱為B數(shù)的階，也就是這個(gè)B樹你最多看到多少個(gè)分叉
如下圖，最多是有5個(gè)分叉。
所以，所謂的5階B樹其實(shí)就是一個(gè)5叉查找樹

然后，根節(jié)點(diǎn)如果不是終端結(jié)點(diǎn)，則至少兩個(gè)子樹。
這個(gè)特性就是保證每個(gè)結(jié)點(diǎn)都平衡，所以對于根節(jié)點(diǎn)來說，如果這個(gè)根節(jié)點(diǎn)不是終端結(jié)點(diǎn)，那么它必須是要有兩棵子樹，不然它自己不平衡啊。

還有一個(gè)特性，就是所有非葉子結(jié)點(diǎn)的結(jié)構(gòu)如下：其實(shí)就是我們剛才給出的那個(gè)數(shù)據(jù)結(jié)構(gòu)的定義。

如下圖：
p0，p1，p2…pn指的是結(jié)點(diǎn)當(dāng)中的一個(gè)個(gè)指針，總共有n+1個(gè)指針
而k1，k2，…kn指的是結(jié)點(diǎn)的關(guān)鍵字，總共是n個(gè)關(guān)鍵字
n記錄實(shí)際關(guān)鍵字是幾個(gè)

pi-1的所指結(jié)點(diǎn)的所有關(guān)鍵字<ki<pi的所指結(jié)點(diǎn)的所有關(guān)鍵字

下面是對B樹特性的總結(jié)：

下面我們根據(jù)B樹的特性來看一下B樹有多高
注：大多數(shù)學(xué)校在計(jì)算B樹高度時(shí)，都是不包括最下面的失敗結(jié)點(diǎn)的，因?yàn)槭〗Y(jié)點(diǎn)本質(zhì)就是一個(gè)NULL

先來看一下最小高度是多少

如果要讓樹高最小，那么在關(guān)鍵字?jǐn)?shù)量不變的情況下，我們應(yīng)該盡可能讓每一個(gè)結(jié)點(diǎn)都填滿關(guān)鍵字。

那么對于m階B樹，每個(gè)結(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字，有m個(gè)分叉。
最上層的根節(jié)點(diǎn)只有一個(gè)（注意，我這里說的是結(jié)點(diǎn)數(shù)量是1，不是關(guān)鍵字?jǐn)?shù)量是1），根結(jié)點(diǎn)有m個(gè)分叉。

由于第一層下來m個(gè)分叉，所以第二層有m個(gè)結(jié)點(diǎn)

第三層，又會(huì)由第二層m個(gè)結(jié)點(diǎn)下來m²個(gè)結(jié)點(diǎn)（每個(gè)結(jié)點(diǎn)m個(gè)分叉）

如果有h層，那么就應(yīng)該是m^h-1

也就是有h層，有（1+m+…+m^h-1）個(gè)結(jié)點(diǎn)

而每個(gè)結(jié)點(diǎn)有m-1個(gè)關(guān)鍵字，所以共（m-1）（1+m+…+m^h-1）個(gè)關(guān)鍵字

那么n個(gè)關(guān)鍵字的B樹高度為h，那么n的范圍肯定是小于等于我們剛才給出的數(shù)值

下面來看一下最大高度是多少
要讓一棵樹長的盡可能的高，就要讓這顆數(shù)的分叉盡可能的少。
對于根節(jié)點(diǎn)最少2個(gè)分叉，對于其他結(jié)點(diǎn)則是最少?m/2?個(gè)分叉

對于m叉樹來說：
在分叉最少的情況下，第一層只有1個(gè)根節(jié)點(diǎn)，2個(gè)分叉
第二層有2個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)?m/2?個(gè)分叉，也就是2[m/2]個(gè)分叉
第三層有2[m/2]個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)?m/2?個(gè)分叉，也就是2[m/2]²個(gè)分叉
…
第h層2[m/2]^h-2個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)?m/2?個(gè)分叉，也就是2[m/2]^h-1個(gè)分叉

再往下推，葉子結(jié)點(diǎn)（失敗結(jié)點(diǎn)）也就是h+1層，至少有2[m/2]^h-1個(gè)結(jié)點(diǎn)

補(bǔ)充重要特性：對于n個(gè)關(guān)鍵字的B樹，必然有n+1個(gè)葉子結(jié)點(diǎn)
解釋：B樹中n個(gè)關(guān)鍵字，相當(dāng)于是在（-∞，+∞）這個(gè)區(qū)間內(nèi)插入n個(gè)關(guān)鍵字，這n個(gè)關(guān)鍵字會(huì)把整個(gè)數(shù)值區(qū)間切分為n+1個(gè)部分。

這n+1個(gè)部分就對應(yīng)了n+1種失敗的情況。

所以，n個(gè)關(guān)鍵字的B樹必有n+1個(gè)葉子結(jié)點(diǎn)，而m階B樹的葉子結(jié)點(diǎn)下限應(yīng)該是2[m/2]^h-1
n+1>=2[m/2]^h-1




小貼士：關(guān)于為什么B樹叫B樹，B樹這個(gè)數(shù)據(jù)結(jié)構(gòu)的發(fā)明者也沒有說明，個(gè)人覺得是balance，平衡的意思。

4.2B樹的插入刪除

4.2.1插入

下面我們從零開始建立一棵B樹，
并且規(guī)定我們這個(gè)B樹是5階B樹，也就是關(guān)鍵字個(gè)數(shù)最少不能少于2個(gè)，最多不能多于4個(gè)

我們插入第一個(gè)元素25，直接放入根節(jié)點(diǎn)中

插38，38>25，放25后面即可

插49，49>38，放38后面

插60，60>49，放49后面

到目前為止，根節(jié)點(diǎn)可以存放的結(jié)點(diǎn)個(gè)數(shù)達(dá)到上限
接下來如果繼續(xù)往里面插入一個(gè)元素，比如80，此時(shí)就導(dǎo)致根節(jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)超過4

對于這種情況，需要把當(dāng)前這個(gè)結(jié)點(diǎn)分裂成兩個(gè)結(jié)點(diǎn)。

我們會(huì)以中間位置，也就是?m/2? 位置的關(guān)鍵字，把原有的結(jié)點(diǎn)拆分為左右兩部分，然后?m/2? 位置的關(guān)鍵字提到父節(jié)點(diǎn)中。

該例子中也就是第三個(gè)元素49提到父節(jié)點(diǎn)位置

接下來插入90這個(gè)元素
注意：我們每次新插入的元素一定是插入到最底層的終端結(jié)點(diǎn)。
可以用上小節(jié)介紹的查找規(guī)則來確定我們應(yīng)該插入到什么位置。

從根節(jié)點(diǎn)出發(fā)，90大于49，而49右邊已經(jīng)沒有元素了，所以順著49右邊指針往下找

接下來檢查新結(jié)點(diǎn)關(guān)鍵字，60<90，80<90，所以90應(yīng)該插到80右邊


所以，我們其實(shí)是通過一次查找來確定我們新元素應(yīng)該插到什么位置。
再次強(qiáng)調(diào)：每次插入的新元素一定是插到最底層的終端結(jié)點(diǎn)中！

接下來再插99

接下來插88，我們用肉眼掃一下可以發(fā)現(xiàn)，88應(yīng)該插在80和90之間

到這里又會(huì)導(dǎo)致當(dāng)前這個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)又超出上限了

處理方法和剛才一樣，用?m/2? 位置的關(guān)鍵字，這里是?5/2? =3位置的關(guān)鍵字提到父節(jié)點(diǎn)，
然后把3位置的關(guān)鍵字左右兩邊元素分別放到其左右子樹上。具體做法如下：

ps：這么做可以保證二叉樹的特性，也就是一個(gè)階段的左子樹結(jié)點(diǎn)值<當(dāng)前結(jié)點(diǎn)值<右子樹結(jié)點(diǎn)值

再接下來插入83，插入87，沒啥好說的，直接插終端結(jié)點(diǎn)

再接下來插入70，肉眼掃一下應(yīng)該插80和83中間，那么又會(huì)溢出，該結(jié)點(diǎn)又需要分裂

把中間元素80提到父節(jié)點(diǎn)，兩邊元素放左右子樹
而這里中間元素80>49，80<88，所以我們把80放49和88之間

如果一個(gè)關(guān)鍵字，它因?yàn)樾枰至讯岬礁腹?jié)點(diǎn)中，我們需要把這個(gè)關(guān)鍵字放到它所屬結(jié)點(diǎn)這條指針的右邊

這樣做可以保證我們的樹仍然保持B樹的特性

接下來再插入4個(gè)新元素92,93,94,99
那么又有結(jié)點(diǎn)需要分裂了

還是一樣的辦法，把中間的93提到父節(jié)點(diǎn)中88的右邊
（把93放到指向當(dāng)前結(jié)點(diǎn)這個(gè)指針對應(yīng)點(diǎn)的右邊，也就是88的右邊）

然后93左右成為左子樹和右子樹

如果再往樹里面插入73,74,75
那么結(jié)點(diǎn)又需要分裂了，我們需要把73提到指向該結(jié)點(diǎn)指針右邊的位置

但是這里我們會(huì)發(fā)現(xiàn)，73提上去之后，根節(jié)點(diǎn)又不夠用了

這種情況，我們就需要把這個(gè)父節(jié)點(diǎn)繼續(xù)向上分裂，由于根節(jié)點(diǎn)上面已經(jīng)沒有父節(jié)點(diǎn)了，所以我們創(chuàng)一個(gè)新結(jié)點(diǎn)

這里根節(jié)點(diǎn)是可以只有一個(gè)關(guān)鍵字的，其他結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)n必須滿足2<=n<=4

下面是B樹插入的總結(jié)

4.2.2刪除

比如我們現(xiàn)在要?jiǎng)hB樹的60

由于60是在終端結(jié)點(diǎn)中，我們直接刪了，然后把60所在結(jié)點(diǎn)的其他關(guān)鍵字左移一下
需要注意的是，你刪了一個(gè)結(jié)點(diǎn)之后，要保證這個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)還是>=?m/2?-1

這里刪完60還剩3個(gè)關(guān)鍵字，沒有低于一個(gè)結(jié)點(diǎn)最少關(guān)鍵字個(gè)數(shù)，是合法的

再比如，我們現(xiàn)在要?jiǎng)h80，80刪了之后根節(jié)點(diǎn)就空了。

那我們可以找出80這個(gè)元素的直接前驅(qū)或者直接后繼來頂替80的位置

如果用直接前驅(qū)來頂替

80的直接前驅(qū)就是80左子樹中最大的，你就找左子樹中最右邊的元素，也就是77

上面的操作，就相當(dāng)于我們把非終端結(jié)點(diǎn)的刪除轉(zhuǎn)換成了終端結(jié)點(diǎn)的刪除。

如果用直接前驅(qū)來頂替
現(xiàn)在要?jiǎng)h根節(jié)點(diǎn)的77，那么我們可以找77右子樹中最小的來頂替77，也就是找右子樹中最左邊的元素82

前面我們探討的情況都很簡單，也就是我們刪除一個(gè)終端結(jié)點(diǎn)關(guān)鍵字時(shí)，這個(gè)終端結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)量還沒有低于它的下限，那么我們下面來介紹一些低于下限的情況：

比如刪38

你刪了38之后，下圖所指結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)小于B樹規(guī)定的最小值2了

那么我們需要分為多種情況來考慮

情況1：被刪結(jié)點(diǎn)它的兄弟可以借
什么意思？當(dāng)前結(jié)點(diǎn)關(guān)鍵字?jǐn)?shù)量不夠了，但是它的右兄弟關(guān)鍵字?jǐn)?shù)量還夠。

可能會(huì)有同學(xué)會(huì)想直接把右兄弟的一個(gè)關(guān)鍵字放到當(dāng)前結(jié)點(diǎn)，但是這樣是有問題的

你直接把70放過去，會(huì)導(dǎo)致70>49，而我們B樹是要求左子樹值<根值<右子樹值
這樣就矛盾了。

解決辦法是先將49拉下來，然后70去頂替49的位置


上面的解決方案可以做一個(gè)小總結(jié)：如果右兄弟的手頭寬裕，我們可以找到當(dāng)前結(jié)點(diǎn)的后繼、后繼的后繼來填補(bǔ)空缺

舉個(gè)例子，當(dāng)前這個(gè)結(jié)點(diǎn)，也就是25這個(gè)元素的后繼是49

而25后繼的后繼，也就是49的后繼應(yīng)該是70，即49右邊指針?biāo)B結(jié)點(diǎn)的第一個(gè)元素

所以，這就是用當(dāng)前結(jié)點(diǎn)后繼、后繼的后繼去頂替它們所需要頂替的位置

上面例子是借右兄弟的例子，下面我們介紹借左兄弟的例子

比如現(xiàn)在要?jiǎng)h90這個(gè)關(guān)鍵字

而刪完90之后，發(fā)現(xiàn)右兄弟已經(jīng)不寬裕了，但是左兄弟還寬裕

具體做法：如果左兄弟的手頭寬裕，我們可以找到當(dāng)前結(jié)點(diǎn)的前驅(qū)、前驅(qū)的前驅(qū)來填補(bǔ)空缺

92的直接前驅(qū)是88，也就是順著指向當(dāng)前結(jié)點(diǎn)的指針左邊的元素

而92前驅(qū)的前驅(qū)是87，也就是88的前驅(qū)，應(yīng)該是88左子樹最右邊的元素

我們用88和87填補(bǔ)所需位置

上面都是介紹了左兄弟或者右兄弟寬裕的情況，下面我們介紹左兄弟和右兄弟都不寬裕的情況
情況2：被刪結(jié)點(diǎn)它的兄弟不可以借

比如現(xiàn)在要?jiǎng)h49

刪完之后當(dāng)前結(jié)點(diǎn)關(guān)鍵字已經(jīng)不夠了，但是右兄弟也不寬裕了

我們的策略是讓當(dāng)前結(jié)點(diǎn)和它的右兄弟合并

合并時(shí)，還需要把這兩個(gè)結(jié)點(diǎn)中間的關(guān)鍵字也一起合并，這樣才能滿足B樹特性

合并過程如下動(dòng)圖：

但是這里又出現(xiàn)問題了，由于我們從父節(jié)點(diǎn)拿走一個(gè)元素，父節(jié)點(diǎn)的關(guān)鍵字又不夠了
所以我們接下來繼續(xù)要合并

合并過程如下動(dòng)圖

而此時(shí)，根結(jié)點(diǎn)已經(jīng)沒有任何關(guān)鍵字了，刪掉它

考試不會(huì)考5階以上的B樹插入刪除，上面介紹的已經(jīng)是比較難的例子，掌握好應(yīng)對考試足矣

4.2.3小結(jié)

4.3B+樹

對于B+樹，考研不會(huì)考很深，基本都是概念的東西

細(xì)心的同學(xué)可能會(huì)發(fā)現(xiàn)，B+樹和我們的分塊查找比較類似

在分塊查中，我們會(huì)把這些元素分成一個(gè)個(gè)塊，在索引表中，我們會(huì)保存每個(gè)塊中最大的關(guān)鍵字。

再回頭看B+樹，其實(shí)也是保存了每個(gè)塊的最大關(guān)鍵字

然后每層索引往上，都是一樣的規(guī)律

4.3.1定義

下面是B+樹的定義

1.每個(gè)分支結(jié)點(diǎn)最多m棵子樹
比如這里的4階B+樹，它最多就是有4個(gè)子樹

2.非葉根節(jié)點(diǎn)至少有兩棵子樹，其他分支結(jié)點(diǎn)至少有?m/2?棵子樹
什么叫非葉根節(jié)點(diǎn)？
首先要明確的是，我們在B+樹中，把最下面一層稱為葉子結(jié)點(diǎn)

下面三個(gè)例子中，第一個(gè)例子，只有一個(gè)根節(jié)點(diǎn)，它同時(shí)也是葉子結(jié)點(diǎn)。
而第三個(gè)例子，根節(jié)點(diǎn)并不是最下面一層的結(jié)點(diǎn)，也就是非葉子結(jié)點(diǎn)，它至少有2棵子樹才能算是B+樹

而第二個(gè)例子，根節(jié)點(diǎn)只有左子樹沒有右子樹，不符合B+樹的定義，它不是B+樹

因?yàn)槲覀兿Ｍ鸅+樹高度盡可能低，所以我們會(huì)追求絕對平衡——所有子樹高度相同
所以，我們會(huì)要求非葉根節(jié)點(diǎn)至少兩棵子樹

另外，我們還要求其他每個(gè)分支結(jié)點(diǎn)至少有?m/2?棵子樹，這里m=4，也就是至少要有2棵子樹

至于為啥這樣，這個(gè)原因和B樹是一樣的，我們要保證每個(gè)結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)（結(jié)點(diǎn)個(gè)數(shù)）不要過少，因?yàn)槿绻總€(gè)結(jié)點(diǎn)子樹數(shù)量太少，就會(huì)導(dǎo)致這棵B+樹長得很高，這樣查找效率就低了。

3.結(jié)點(diǎn)子樹個(gè)數(shù)和關(guān)鍵字個(gè)數(shù)相等（重要）
這一點(diǎn)比較容易在選擇題中進(jìn)行考察，因?yàn)檫@也是B+樹和B樹比較大的一點(diǎn)區(qū)別

比如下面這個(gè)結(jié)點(diǎn)，對應(yīng)3個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字也對應(yīng)1個(gè)分支

所以B+樹當(dāng)中一個(gè)結(jié)點(diǎn)里面，它含有多少個(gè)關(guān)鍵字，對應(yīng)的它就有多少個(gè)分支，有多少個(gè)子樹。

ps：B樹中，如果一個(gè)結(jié)點(diǎn)有2個(gè)關(guān)鍵字，那它是對應(yīng)3個(gè)分支

4.所有葉結(jié)點(diǎn)包含全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，葉結(jié)點(diǎn)中將關(guān)鍵字按大小順序排列，并且相鄰葉結(jié)點(diǎn)按大小順序相互鏈接起來。

在B+樹中，我們可以通過指針p，從第一個(gè)葉子結(jié)點(diǎn)開始，一個(gè)個(gè)往后遍歷，把所有葉子結(jié)點(diǎn)都遍歷完。

也就是說，B+樹是支持順序查找的

5.所有分支結(jié)點(diǎn)中僅包含它的各個(gè)子結(jié)點(diǎn)中關(guān)鍵字的最大值及指向其子節(jié)點(diǎn)的指針。
這個(gè)和分塊查找原理很類似，這里不再贅述

4.3.2B+樹的查找

先看一個(gè)查找成功的例子：
比如現(xiàn)在要查編號9的學(xué)生對應(yīng)信息

從根節(jié)點(diǎn)出發(fā)，9<15，15表示的是它所指向的一整個(gè)分塊中最大的關(guān)鍵字是15

所以如果9存在，一定是在15的分塊中


3<9，指針后移

第二個(gè)正好是9，那么9是在當(dāng)前關(guān)鍵字所指結(jié)點(diǎn)中
ps：如果在B+樹查找中，我們在分支結(jié)點(diǎn)中找到我們所需關(guān)鍵字，其實(shí)整個(gè)查找并沒有結(jié)束。
你得找到最下面一層葉子結(jié)點(diǎn)才能知道相關(guān)記錄信息。

指針繼續(xù)往下移，到葉子結(jié)點(diǎn)了

從左往右依次檢查，就可以在這個(gè)葉子結(jié)點(diǎn)中找到9這個(gè)關(guān)鍵字

那么通過9，就可以找到9號學(xué)生對應(yīng)的相關(guān)信息了

再看一個(gè)查找失敗的例子：
比如我們要查找的關(guān)鍵字是7，

那么從根結(jié)點(diǎn)出發(fā)，7<15，應(yīng)該往15所指結(jié)點(diǎn)找

3<7，7肯定不在3所指結(jié)點(diǎn)內(nèi)，指針右移

7<9，如果7存在，肯定在9所指結(jié)點(diǎn)內(nèi)

檢查下一個(gè)結(jié)點(diǎn)，6<7，指針右移

下一個(gè)元素是8,8>7

注意！這里已經(jīng)是最下面一層的葉子結(jié)點(diǎn)了，到這里沒找到7就說明7不存在了。

B+樹中無論是查找成功還是查找失敗，都要找到最下面一層的葉子結(jié)點(diǎn)。

除了根節(jié)點(diǎn)往下找，還可以通過葉子結(jié)點(diǎn)那里保存的指針p進(jìn)行順序查找

4.3.3B+樹和B樹的對比

4.3.4小結(jié)

五、散列表

5.1散列表的基本概念

5.1.1散列表、散列函數(shù)

我們根據(jù)散列函數(shù)可以計(jì)算出一個(gè)數(shù)據(jù)元素在散列表中的存儲地址。
比如這里散列函數(shù)是H（key）=key%13
那么如果你給我19，H（19）=19%13=6，我就可以立馬知道如果19存在，則存放在6號位置

再比如你給我16，H（16）=16%13=3，我就可以立馬知道如果16存在，則存放在3號位置

可以看到，在理想情況下，我們散列表查找一個(gè)元素時(shí)間復(fù)雜度只需要O（1）

5.1.2沖突、同義詞

我們并不希望沖突頻繁發(fā)生，沖突越少，散列表性能越高

5.1.3關(guān)于散列表，有待解決的問題

5.2散列函數(shù)的構(gòu)造

散列函數(shù)的作用是把一個(gè)關(guān)鍵字映射到與之對應(yīng)的存儲地址上。

當(dāng)我們設(shè)計(jì)一個(gè)散列函數(shù)時(shí)，應(yīng)盡可能減少不同關(guān)鍵字之間發(fā)生沖突的情況。

該小節(jié)將介紹4種散列函數(shù)構(gòu)造方式：

考試中最常考、現(xiàn)實(shí)中最常用的都是除留余數(shù)法

5.2.1除留余數(shù)法

5.2.2直接定址法

這種方法適用于關(guān)鍵字分布基本連續(xù)

5.2.3數(shù)字分析法

5.2.4平方取中法

5.2.5小結(jié)

5.3處理沖突的方法——拉鏈法

散列表通常不考代碼，著重掌握手算分析方法

散列表中沖突這種現(xiàn)象是無法避免的，可能會(huì)有多個(gè)元素映射到同一個(gè)散列地址。
這些元素在插入時(shí)就會(huì)發(fā)生沖突

我們第一種解決沖突的方式就是拉鏈法

我們把這些同義詞用一個(gè)鏈表連起來

5.3.1插入

現(xiàn)有如下的空散列表，長度13，散列函數(shù)H（key）=key%13，我們用拉鏈法解決沖突

5.3.2查找

5.3.3刪除

5.3.4小結(jié)

5.4處理沖突的方法——開放定址法

5.4.1基本原理

散列表中沖突是不可避免的，我們可以用拉鏈法，也可以用開放定址法

舉個(gè)例子，我們有散列函數(shù)H（key）=key%13，現(xiàn)在14已結(jié)占了1的位置，如果現(xiàn)在1再進(jìn)來，想占據(jù)1的位置怎么辦？

我們可以讓給1找另一個(gè)空閑位置。

所謂開放定址法，就是一個(gè)散列地址，既對同義詞開放，也對非同義詞開放。

那么問題也隨之而來，發(fā)生沖突時(shí)，我們要給新元素找另一個(gè)位置，那這個(gè)位置怎么確定？

假設(shè)我們現(xiàn)在原始地址發(fā)生沖突了，我們從原始地址往右偏移1位

如果還發(fā)生沖突，就去探索一下原始位置左邊是否有沖突

如果還發(fā)生沖突，去原始地址右邊兩位看看有沒有空位

如果還沖突，就探索原位置左邊兩位有沒有空位。。。

也就是說，當(dāng)發(fā)生沖突時(shí)，我們可以設(shè)計(jì)這樣一個(gè)序列：0，1，-1，2，-2，3，-3…
來規(guī)定發(fā)生沖突時(shí)我們探測每個(gè)位置的順序。

5.4.2線性探測法

對于散列表的插入，就是你先根據(jù)散列函數(shù)算出一個(gè)原始地址，然后根據(jù)那個(gè)探測法去探測原始地址周圍的位置。

而對于散列表的查找，和插入基本一樣，也就先算原始地址，然后根據(jù)對應(yīng)探測法去探測。
但是對于查找有個(gè)需要注意的地方，就是如果你探測下來，探測到空位置還沒探測到，說明原先就沒有這個(gè)關(guān)鍵字。那么查找失敗。

5.4.3平方探測法

5.4.3雙散列法

對于雙散列法，需要設(shè)計(jì)第二個(gè)散列函數(shù)，發(fā)生沖突時(shí)，需要根據(jù)關(guān)鍵字的值去確定第二個(gè)散列函數(shù)的計(jì)算結(jié)果。

不同關(guān)鍵字的探測序列也是不同的

5.4.4偽隨機(jī)序列法

5.4.5刪除

需要注意，刪除元素時(shí)會(huì)有一個(gè)坑！以下是刪除的錯(cuò)誤示范?。。?/font>
比如我們現(xiàn)在用線性探測法，要?jiǎng)h15

首先應(yīng)該查找15
第一次定位15%13=2，但是2號位已經(jīng)被占了，往右1位，找到15

然后刪15