目錄

一、查找

1、查找概念

2、順序查找

3、折半查找?

4、分塊查找

二、樹

1、B樹?

2、B樹的基本操作

3、B+樹

4、散列查找及其性能分析?

5、散列查找及性能分析

---

一、查找

1、查找概念

?

• 查找：在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找。
• 查找表(查找結(jié)構(gòu))：用于查找的。數(shù)據(jù)集合稱為查找表，它由同一類型的數(shù)據(jù)元素 (或記錄)組成。
• 關(guān)鍵字：數(shù)據(jù)元素中唯一標(biāo)識該元素的某個數(shù)據(jù)項(xiàng)的值，使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)該是唯一的。

如下舉例：?

?

• 查找長度：在查找運(yùn)算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度。
• 平均查找長度(ASL，Average Search Length)：?所有查找過程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值。

2、順序查找

?

• 順序查找，又叫“線性查找”，通常用于線性表算法
• 思想:從頭到 jio 個找 (或者反過來也OK)?

代碼實(shí)現(xiàn)：?

typedef struct{				//查找表的數(shù)據(jù)結(jié)構(gòu)（順序表）ElemType *elem;			//動態(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);// 查找成功返回?cái)?shù)組下標(biāo)，否則返回-1return i=ST.TableLen? -1 : i;
}

哨兵方式代碼實(shí)現(xiàn)：

typedef struct{				//查找表的數(shù)據(jù)結(jié)構(gòu)（順序表）ElemType *elem;			//動態(tài)數(shù)組基址int TableLen;			//表的長度
}SSTable;//順序查找
int Search_Seq(SSTable ST,ElemType key){ST.elem[0]=key;int i;for(i=ST.TableLen;ST.elem[i]!=key;--i)// 查找成功返回?cái)?shù)組下標(biāo)，否則返回0return i;
}

?用查找判定樹分析ASL

• 一個成功結(jié)點(diǎn)的查找長度=自身所在層數(shù)
• 一個失敗結(jié)點(diǎn)的查找長度 =其父節(jié)點(diǎn)所在
• 層數(shù)默認(rèn)情況下，各種失敗情況或成功情況都等概率發(fā)生

3、折半查找?

【折半查找概念】

• 折半查找，又稱“二分查找”，僅適用于有序的順序表

折半查找代碼實(shí)現(xiàn)：?

typedef struct{ElemType *elem;int TableLen;
}SSTable;// 折半查找
int Binary_Search(SSTable L,ElemType key){int low=0,high=L.TableLen,mid;while(low<=high){mid=(low+high)/2;if(L.elem[mid]==key)return mid;else if(L.elem[mid]>key)high=mid-1;					//從前半部分繼續(xù)查找elselow=mid+1;					//從后半部分繼續(xù)查找}return -1;
}

• 折半查找判定樹的構(gòu)造：m i d = ? ( l o w + h i g h ) / 2 ? ，如果當(dāng)前 low 和 high 之間有奇數(shù)個元素，則 mid 分隔后，左右兩部分元素個數(shù)相等；如果當(dāng)前 low 和 high 之間有偶數(shù)個元素，則 mid 分隔后，左半部分?右半部分少?個元素。
• 折半查找的判定樹中，若m i d = ? ( l o w + h i g h ) / 2 ? ，則對于任何?個結(jié)點(diǎn)，必有：右?樹結(jié)點(diǎn)數(shù) - 左?樹結(jié)點(diǎn)數(shù) = 0 或 1。
• 折半查找的判定樹?定是平衡?叉樹。折半查找的判定樹中，只有最下??層是不滿的。因此，元素個數(shù)為 n 時樹? h = ? l o g 2 ( n + 1 ) ? 。
• 判定樹結(jié)點(diǎn)關(guān)鍵字：左<中<右，滿??叉排序樹的定義。失敗結(jié)點(diǎn)：n+1個（等于成功結(jié)點(diǎn)的空鏈域數(shù)量）
• 折半查找的查找效率：折半查找的時間復(fù)雜度 = O ( l o g 2 n ) 。

4、分塊查找

分塊查找所針對的情況：塊內(nèi)?序、塊間有序。

?

?索引表及順序表代碼

// 索引表
typedef struct{ElemType maxValue;int low,high;
}Index;// 順序表存儲實(shí)際元素
ElemType List[100];

• 查找目標(biāo)關(guān)鍵字所在分塊可使用順序查找和折半查找兩種方式。
• 若使用折半查找且索引表中不包含?標(biāo)關(guān)鍵字，則最終要停在 low > high，要在 low 所指分塊中查找目標(biāo)關(guān)鍵字。
• 查找效率分析（ASL）：假設(shè)?度為 n 的查找表被均勻地分為 b 塊，每塊 s 個元素。設(shè)索引查找和塊內(nèi)查找的平均查找?度分別為?ASL=LI?+LS?

二、樹

1、B樹?

B樹，?稱多路平衡查找樹，B樹中所有結(jié)點(diǎn)的孩?個數(shù)的最?值稱為B樹的階，通常?m表示。?棵m階B樹或?yàn)榭諛?#xff0c;或?yàn)闈M?如下特性的m叉樹：

• 樹中每個結(jié)點(diǎn)?多有 m 棵?樹，即?多含有 m-1 個關(guān)鍵字。
• 若根結(jié)點(diǎn)不是終端結(jié)點(diǎn)，則?少有兩棵?樹。
• 除根結(jié)點(diǎn)外的所有?葉結(jié)點(diǎn)?少有 ? m / 2 ?棵?樹，即?少含有 $\lceil m/2\rceil-1 $個關(guān)鍵字。（為了保證查找效率，每個結(jié)點(diǎn)的關(guān)鍵字不能太少）

• 所有的葉結(jié)點(diǎn)都出現(xiàn)在同?層次上，并且不帶信息（可以視為外部結(jié)點(diǎn)或類似于折半查找判定樹的查找失敗結(jié)點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針為空）。

?

m階B樹的核?特性：

• 根節(jié)點(diǎn)的?樹數(shù)∈ [ 2 , m ] ∈[2, m]∈[2,m]，關(guān)鍵字?jǐn)?shù) ∈ [ 1 , m ? 1 ] ∈[1, m-1]∈[1,m?1]。
• 其他結(jié)點(diǎn)的?樹數(shù)∈ [ ? m / 2 ? , m ] ∈[?m/2? , m]∈[?m/2?,m]；關(guān)鍵字?jǐn)?shù)∈ [ ? 1 , m ? 1 ] ∈[ -1, m-1]∈[?1,m?1]。
• 對任?結(jié)點(diǎn)，其所有?樹?度都相同。
• 關(guān)鍵字的值：?樹0 < 關(guān)鍵字1 < ?樹1 < 關(guān)鍵字2 < ?樹2 <…. (類??叉查找樹左<中<右)

B樹的?度：含 n 個關(guān)鍵字的 m叉B樹，最??度、最??度是多少？

• logm?n+1≤h≤log?m/2??2n+1?+1

2、B樹的基本操作

B樹的查找：

• B樹的查找操作與二叉查找樹類似。B樹的查找包含兩個基本操作：① 在B樹中找結(jié)點(diǎn)；② 在結(jié)點(diǎn)中找關(guān)鍵字。B樹常存儲在磁盤上，因此前一個查找操作在磁盤上進(jìn)行，后一個查找操作在內(nèi)存中進(jìn)行。在B樹中查找到某個結(jié)點(diǎn)后，先在有序表中進(jìn)行查找，若找到則查找成功，否則按照對應(yīng)指針信息到所指的子樹中去查找。查找到葉子結(jié)點(diǎn)（對應(yīng)指針為空指針），則說明樹中沒有對應(yīng)的關(guān)鍵字，查找失敗。

B樹的插入：將關(guān)鍵字 key 插入到B樹的過程：?

• 定位：利用B樹的查找算法，找到插入該關(guān)鍵字的最底層中的某個非葉子結(jié)點(diǎn)。（插入位置一定是最底層的某個非葉子結(jié)點(diǎn)！）
• 插入：B樹中，每個非失敗節(jié)點(diǎn)的關(guān)鍵字個數(shù)都在區(qū)間[ ? m / 2 ? ? 1 , m ? 1 ] [?m/2?- 1,m-1][?m/2??1,m?1]內(nèi)。若插入關(guān)鍵字 key 之后結(jié)點(diǎn)關(guān)鍵字個數(shù)小于m，則可以直接插入；否則必須對結(jié)點(diǎn)進(jìn)行分裂。
• 分裂：從結(jié)點(diǎn)的中間位置（? m / 2 ? ?m/2??m/2?）將其中的關(guān)鍵字分為兩部分，左半部分包含的關(guān)鍵字放到原結(jié)點(diǎn)中，右半部分包含的關(guān)鍵字放到新節(jié)點(diǎn)中，中間位置（? m / 2 ? ?m/2??m/2?）的關(guān)鍵字則插入原節(jié)點(diǎn)的父節(jié)點(diǎn)。若此時父節(jié)點(diǎn)的關(guān)鍵字也超過了上限，則對父節(jié)點(diǎn)繼續(xù)進(jìn)行分裂操作，直到這個過程傳到根節(jié)點(diǎn)為止，進(jìn)而導(dǎo)致B樹的高度增加。

B樹的刪除：

1. 非終端結(jié)點(diǎn)的刪除：使用直接前驅(qū)或者直接后繼來代替被刪除的關(guān)鍵字，轉(zhuǎn)換為刪除終端結(jié)點(diǎn)。
2. 終端結(jié)點(diǎn)的刪除，具體分為三種情況

• 直接刪除關(guān)鍵字：若刪除關(guān)鍵字所在結(jié)點(diǎn)關(guān)鍵字個數(shù) ≥ ? m / 2 ? ≥?m/2?≥?m/2?，則可直接刪除。
• 兄弟夠借：若刪除關(guān)鍵字所在結(jié)點(diǎn)關(guān)鍵字個數(shù) = ? m / 2 ? ? 1 =?m/2?-1=?m/2??1，且與此結(jié)點(diǎn)相鄰的左（或右）兄弟結(jié)點(diǎn)關(guān)鍵字個數(shù) ≥ ? m / 2 ? ≥?m/2?≥?m/2?，則需調(diào)整該節(jié)點(diǎn)、左（或右）兄弟結(jié)點(diǎn)及其雙親結(jié)點(diǎn)（父子換位法）以達(dá)到新的平衡。
• 兄弟不夠接：若刪除關(guān)鍵字所在結(jié)點(diǎn)關(guān)鍵字個數(shù) = ? m / 2 ? ? 1 =?m/2?-1=?m/2??1，且與此結(jié)點(diǎn)相鄰的左（或右）兄弟結(jié)點(diǎn)關(guān)鍵字個數(shù) = ? m / 2 ? ? 1 =?m/2?-1=?m/2??1，則將該節(jié)點(diǎn)、左（或右）兄弟結(jié)點(diǎn)及其雙親結(jié)點(diǎn)中的關(guān)鍵字進(jìn)行合并。
  ?

3、B+樹

一棵m階的B+樹需滿足以下條件：?

• 每個分支節(jié)點(diǎn)最多有m棵子樹（孩子結(jié)點(diǎn)）。
• 非葉根結(jié)點(diǎn)至少有兩顆子樹，其他每個分支結(jié)點(diǎn)至少有? m / 2 ? ?m/2??m/2?棵子樹。
• 結(jié)點(diǎn)的子樹個數(shù)與關(guān)鍵字個數(shù)相同。
• 所有葉子結(jié)點(diǎn)包含所有關(guān)鍵字及指向相應(yīng)記錄的指針，葉子結(jié)點(diǎn)中將關(guān)鍵字按大小排列，并且相鄰葉子結(jié)點(diǎn)按大小順序相互鏈接起來。（說明B+樹支持順序查找）
• 所有分支節(jié)點(diǎn)僅包含它的各個節(jié)點(diǎn)中關(guān)鍵字的最大值及指向其子節(jié)點(diǎn)的指針。
  ?

4、散列查找及其性能分析?

散列表的基本概念

• 散列函數(shù)：一個把查找表中的關(guān)鍵字映射成該關(guān)鍵字對應(yīng)的地址的函數(shù)，記作H a s h ( k e y ) = A d d r Hash(key)=AddrHash(key)=Addr。
• 散列函數(shù)可能會把兩個或兩個以上的不同關(guān)鍵字映射到同一地址，稱這種情況為沖突。發(fā)生碰撞的不同關(guān)鍵字稱為同義詞。
• 散列表：根據(jù)關(guān)鍵字而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。散列表建立了關(guān)鍵字和存儲地址之間的一種直接映射關(guān)系。

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

1. 直接定址法：直接取關(guān)鍵字的某個線性函數(shù)值為散列地址，散列函數(shù)為 H ( k e y ) = k e y? 或 H ( k e y ) = a × k e y + b 。這種方法計(jì)算簡單，不會產(chǎn)生沖突。缺點(diǎn)是空位較多，會造成存儲空間浪費(fèi)。
2. 除留余數(shù)法：假定散列表表長 m，取一個不大于但最接近 m 的質(zhì)數(shù) p，利用散列函數(shù) H ( k e y ) = k e y % p將關(guān)鍵字轉(zhuǎn)換為散列地址。p取質(zhì)數(shù)是因?yàn)檫@樣可以使關(guān)鍵字通過散列函數(shù)轉(zhuǎn)換后等概率地映射到散列空間上的任一地址。
3. 數(shù)字分析法：假設(shè)關(guān)鍵字是 r進(jìn)制數(shù)，而r個數(shù)碼在個位上出現(xiàn)的頻率不一定相同，可能在某些位上分布的均勻一些，而在某些位分布的不均勻。此時應(yīng)選數(shù)碼分布均勻的若干位作為散列地址。
4. 平方取中法：這種方法取關(guān)鍵字平方值的中間幾位作為散列地址，具體取多少位視具體情況而定。這種方法得到的散列地址與關(guān)鍵字的每一位都有關(guān)系，因此使得散列地址分布比較均勻。適用于關(guān)鍵字每位取值都不夠均勻或均小于散列地址所需的位數(shù)。

5、散列查找及性能分析

散列查找執(zhí)行步驟如下

1. 初始化：A d d r = H a s h ( k e y )?
2. 檢測查找表中地址為 Addr 的位置上是否有記錄，若無記錄，返回查找失敗；若有記錄，比較它和 key 的值，若相等則返回查找成功，否則執(zhí)行步驟③。
3. 用給定的處理沖突方式計(jì)算“下一個散列表地址”，并把 Addr 置為此地址，轉(zhuǎn)入步驟②。

平均查找長度（ASL）：散列表查找成功的平均查找長度即找到表中已有表項(xiàng)的平均比較次數(shù)；散列表查找失敗的平均查找長度即找不到待查的表項(xiàng)但能找到插入位置的平均比較次數(shù)。