線性表的查找

順序查找

技巧：設(shè)置哨兵，放在下標(biāo)為0的位置。

int Search_Seq(SSTable ST, KeyType key) {
    ST.R[0].key = key;
    for(int i = ST.length; ST.R[i].key != key; i--);
    return i;
}

算法分析

適用于順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)，不要求記錄按關(guān)鍵字有序。
平均查找長(zhǎng)度為(n + 1) / 2，查找效率低。

折半（二分）查找

int Search_Bin(SSTable ST, KeyType key) {
    low = 1; high = ST.length;
    while(low <= high) {
        mid = (low + right) / 2;
        if(key == ST.R[mid].key) return mid;
        else if(key < ST.R[mid].key) high = mid - 1;
        else low = mid + 1;
    }
    return 0;
}

二叉判定樹

當(dāng)前查找區(qū)間的中間位置是根，左子樹和右子樹分別是左子表和右子表。
則查找失敗就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑，比較的關(guān)鍵字個(gè)數(shù)等于路徑上的內(nèi)部結(jié)點(diǎn)個(gè)數(shù)。
當(dāng)n較大時(shí)，ASL = log2(n + 1) - 1

算法分析

要求必須是順序存儲(chǔ)結(jié)構(gòu)，且按關(guān)鍵字有序排列。
對(duì)于長(zhǎng)度為n的有序表，需要比較的關(guān)鍵字個(gè)數(shù)最多是floor(log2(n)) + 1。時(shí)間復(fù)雜度為O(log2(n)).

分塊查找（索引順序查找）

建立一個(gè)索引表，按關(guān)鍵字有序，整個(gè)待查找表有序或者分塊有序。
確定塊的查找可以用順序查找或者折半查找，塊中的查找只能用順序查找（因?yàn)椴灰欢P(guān)鍵字有序）。

算法分析

順序查找：ASL = (1 / 2) * (n / s + s) + 1
折半查找：ASL = log2(n / s + 1) + (s / 2)
便于插入和刪除，可以實(shí)現(xiàn)在快速查找的同時(shí)經(jīng)常動(dòng)態(tài)變化。

散列表（哈希）

相關(guān)定義

1. 散列表：有限連續(xù)的地址空間。
2. 沖突：不同關(guān)鍵字對(duì)應(yīng)同一個(gè)散列地址。
   沖突是不可避免的。
3. 同義詞：發(fā)生沖突的不同關(guān)鍵字。

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

原則

1. 減少?zèng)_突。
2. 散列地址分布均勻。

常用方法

1. 直接定址
   1）條件：已知關(guān)鍵字每一位的數(shù)字分布情況。
   2）操作：從關(guān)鍵字中提取數(shù)字分布比較隨機(jī)的若干位作為散列地址。
2. 平方取中
   取關(guān)鍵字平方后的中間幾位，具體位數(shù)由表長(zhǎng)決定。
3. 折疊
   將關(guān)鍵字分割成位數(shù)相同的多個(gè)部分，疊加求和，舍去進(jìn)位，取與前面相同的位數(shù)。
   適用于散列地址位數(shù)少，關(guān)鍵字位數(shù)多。
   1）移位疊加：最低位對(duì)齊
   2）邊界疊加：按照折疊繩子的方式疊加
4. 除留余數(shù)
   選擇一個(gè)比表長(zhǎng)小的最大素?cái)?shù)取模。

處理沖突

1. 開放地址
   H0發(fā)生沖突時(shí)，基于H0用某方式計(jì)算得到下一個(gè)H，直到不發(fā)生沖突為止。

• 線性探測(cè)法
  假想成一個(gè)循環(huán)表，先從沖突地址下一個(gè)位置進(jìn)行尋找，如果到表尾也沒找到位置，就從表頭開始再找，如果還是找不到，做溢出處理。
• 二次探測(cè)法
  每次從沖突位置的前后k2位置查找。
• 偽隨機(jī)探測(cè)法
  增量序列等于一個(gè)偽隨機(jī)數(shù)序列。

2. 鏈地址
   同義詞鏈表：散列地址相同的關(guān)鍵詞放進(jìn)一個(gè)單鏈表。
   一個(gè)數(shù)組存放頭指針。

分析

1. 線性探測(cè)法

• 優(yōu)點(diǎn)：只要表沒滿，總能找到合適的位置。
• 缺點(diǎn)：二次聚集（第一個(gè)散列地址不同的關(guān)鍵字在尋找后續(xù)散列地址的過程中再次沖突）。

2. 二次探測(cè)法/偽隨機(jī)探測(cè)法

• 優(yōu)點(diǎn)：沒有二次聚集。
• 缺點(diǎn)：不一定找得到位置。

3. 鏈地址
   沒有二次聚集。

散列表查找

算法分析

1. 裝填因子α
   α = 表中填入記錄數(shù) / 散列表長(zhǎng)度
   表示散列表的裝滿程度。α越大，沖突可能性越大，需要比較的關(guān)鍵字個(gè)數(shù)越多。
2. 影響平均查找長(zhǎng)度的因素：處理沖突的方法和裝填因子。
   平均查找長(zhǎng)度與α有關(guān)，與n無關(guān)。

線性探測(cè)法 成功(1/2)(1+1/(1-α)) 失敗(1/2)(1+(1-α)2)
二次探測(cè)法/偽隨機(jī)探測(cè)法 成功(-ln(1-α)/α) 失敗(1/(1-α))
鏈地址法 成功(1+α/2) 失敗(α+exp(-α))

二叉排序樹

性質(zhì)：中序遍歷是遞增的

查找

算法實(shí)現(xiàn)

BSTree SearchBST(BSTree T, KeyType key) {
    if(!T || key == T->data) return T;
    else if(key < T->data) return SearchBST(T->lchild, key);
    else return SearchBST(T->rchild, key);
}

算法分析

最壞情況：?jiǎn)沃?ASL=(n+1)/2
平均情況：ASL=log2(n)

插入

時(shí)間復(fù)雜度O(log2(n))

創(chuàng)建

時(shí)間復(fù)雜度O(nlog2(n))

刪除

在不破壞二叉排序樹性質(zhì)的情況下，選擇合理的被刪結(jié)點(diǎn)的左/右孩子對(duì)其進(jìn)行替代。
時(shí)間復(fù)雜度O(log2(n))

平衡二叉樹（AVL樹）

平衡因子（BF）

節(jié)點(diǎn)左右子樹的深度差。
AVL樹的所有節(jié)點(diǎn)的BF為0/1/-1.
查找的時(shí)間復(fù)雜度是O(log2(n))

平衡調(diào)整方法

調(diào)整最小不平衡子樹。
書上總結(jié)了4中旋轉(zhuǎn)方式（LL，RR，RL，LR），但是完全不需要記，因?yàn)楹艹橄蟆４_定好調(diào)整范圍后直接進(jìn)行調(diào)整。

B-樹

定義

B-樹也叫B樹、B_樹（“-”是個(gè)連字符，不是“減”），是適用于外查找（存在外存里的）的平衡多叉查找樹。
適用于磁盤目錄管理、數(shù)據(jù)庫(kù)系統(tǒng)索引等。

1. 每個(gè)結(jié)點(diǎn)至多有m棵子樹（m稱為階，m等于2時(shí)B-樹就是二叉搜索樹）。階數(shù)通常非常大，以保證在存了大量數(shù)據(jù)的情況下，樹的高度不會(huì)過于大。
2. 如果根不是葉子，則至少有兩棵子樹。（可以理解成 根不是葉子節(jié)點(diǎn) 說明根必有子樹 而B-樹的節(jié)點(diǎn)必須先有關(guān)鍵字才能有子樹 且紫薯數(shù)量等于關(guān)鍵字?jǐn)?shù)量加1）
3. 除根之外的所有非葉子結(jié)點(diǎn)至少有ceil(m/2)棵子樹。
4. 失敗結(jié)點(diǎn)：葉子結(jié)點(diǎn)。所有葉子結(jié)點(diǎn)都位于同一層。
5. 非葉子結(jié)點(diǎn)最多有(m-1)個(gè)關(guān)鍵字。（之所以這樣要求，是因?yàn)锽-樹的每個(gè)結(jié)點(diǎn)其實(shí)可以理解成關(guān)鍵字“填補(bǔ)了”子樹的縫隙，子樹存在于兩個(gè)相鄰關(guān)鍵字之間（自己瞎理解的，如果讓你感到迷惑就忽略吧））

特點(diǎn)

1. 平衡：所有葉子都在同一層。
2. 有序：左小右大。
3. 多路：非葉子節(jié)點(diǎn)有多個(gè)關(guān)鍵字和子樹。

查找

存儲(chǔ)結(jié)構(gòu)

#define m 3
typedef struct BTNode {
    int keynum;
    struct BTNode *parent;
    int k[m + 1]; // 關(guān)鍵字
    struct BTNode *ptr[m + 1]; // 子樹指針
    Record *recptr[m + 1]; 
} BTNode, *BTree;
typedef struct {
    BTNode *pt;
    int i; // 關(guān)鍵字序號(hào)
    int tag; // 查找是否成功
} Result;

算法描述

順序/折半查找，將待查值與根節(jié)點(diǎn)各個(gè)關(guān)鍵字比較。

• key == Ki 查找成功。
• key < K1 沿第一個(gè)子樹向下找。
• Ki < key < K(i+1) 沿著第i個(gè)子樹向下找。
• key > Kj 沿著隨后一個(gè)子樹指針向下找。

如果直到葉子節(jié)點(diǎn)也沒有找到，則查找失敗。

PS：“關(guān)鍵字”指的并不是存儲(chǔ)的數(shù)據(jù)，實(shí)際上一個(gè)結(jié)點(diǎn)中存儲(chǔ)的應(yīng)該是很多個(gè)<key, value>鍵值對(duì)，只是為了方便而用關(guān)鍵字來代指鍵值對(duì)。所以在查找、插入、刪除的過程中，真正操作的對(duì)象其實(shí)是“記錄”，也就是鍵值對(duì)。

算法實(shí)現(xiàn)

Result SearchBTree(BTree T, int key) {
    p = T, q = NULL, found = false, i = 0;
    while(p && !found) {
        i = Search(p, key);
        if(i > 0 && p->k[i] == key) found = true;
        else q = p, p = p->ptr[i];
    }
    return (found) ? (p, i, 1) : (q, i, 0);
}

算法分析

B-樹查找的兩種基本操作是在樹上找結(jié)點(diǎn)和在結(jié)點(diǎn)中找關(guān)鍵字。由于B-樹通常存在磁盤上，所以前者是在磁盤上執(zhí)行的，后者是在內(nèi)存中執(zhí)行的。所以磁盤中的查找次數(shù)，也就是待查關(guān)鍵字在B-樹上的層數(shù)（深度）決定了查找效率。
查找可能在非葉子結(jié)點(diǎn)結(jié)束，整棵樹中查找一次的效率逼近二分查找。

插入

算法描述

• 如果待插入key存在，就用新的value替換舊的value。
• 如果待插入key不存在，就在葉子結(jié)點(diǎn)中插入；插入之后判斷當(dāng)前結(jié)點(diǎn)key數(shù)是否小于等于m-1，如果不滿足，則取當(dāng)前結(jié)點(diǎn)的中間結(jié)點(diǎn)（如果是偶數(shù)就取中間左側(cè)或右側(cè)任意一個(gè)結(jié)點(diǎn)）放到其上一層結(jié)點(diǎn)的正確位置，也就是“結(jié)點(diǎn)分裂”。

算法分析

如果所有關(guān)鍵字都事先排序后再插入，會(huì)導(dǎo)致結(jié)點(diǎn)空間利用率很低，最差只有50%（因?yàn)楦附Y(jié)點(diǎn)對(duì)應(yīng)關(guān)鍵字與其右側(cè)關(guān)鍵字之間的整數(shù)個(gè)數(shù)可能小于子結(jié)點(diǎn)的空間，比如父節(jié)點(diǎn)27與30之間的子樹，最多只能有28和29兩個(gè)結(jié)點(diǎn)，而空間很可能大于2）。

刪除

算法描述

1. 如果待刪結(jié)點(diǎn)位于非葉子結(jié)點(diǎn)，先將其替換到葉子中再進(jìn)行刪除。
2. 刪除之后判斷當(dāng)前結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)是否大于等于ceil(m/2)-1，如果是就結(jié)束操作。
3. 如果不是，先看其兄弟結(jié)點(diǎn)是否可以對(duì)其進(jìn)行支援（挪過一個(gè)關(guān)鍵字并不影響兄弟結(jié)點(diǎn)自身的合法性），如果可以就做，如果不可以，從其父結(jié)點(diǎn)中取出關(guān)鍵字并與其及其兄弟結(jié)點(diǎn)進(jìn)行結(jié)點(diǎn)合并。

B+樹

B+樹與B樹的區(qū)別

1. B+樹的非葉子結(jié)點(diǎn)只存儲(chǔ)關(guān)鍵字，不存儲(chǔ)數(shù)據(jù)，可以減少結(jié)點(diǎn)數(shù)從而減小樹的高度，進(jìn)而查找過程中需要進(jìn)行的磁盤操作次數(shù)就更少。
2. B+樹的葉子結(jié)點(diǎn)按照從小到大的順序依次連接。
3. B+樹除根之外的所有非葉子結(jié)點(diǎn)至少有ceil(m/2)個(gè)關(guān)鍵字（注意B樹除根之外的所有非葉子結(jié)點(diǎn)至少有ceil(m/2)棵子樹）。

查找

與B-樹類似，只是如果非葉子結(jié)點(diǎn)上的關(guān)鍵字等于待查關(guān)鍵字，不會(huì)終止查找，而是繼續(xù)向下直到找到對(duì)應(yīng)的葉子結(jié)點(diǎn)。也就是說，不會(huì)像B-樹一樣時(shí)間效率不穩(wěn)定。由于B+樹所有葉子都位于同一高度，所以查找的時(shí)間復(fù)雜度穩(wěn)定在O(logn)。

插入和刪除

都只在葉子結(jié)點(diǎn)中進(jìn)行。如果插入/刪除之后導(dǎo)致出現(xiàn)溢出/關(guān)鍵字不夠，就操作對(duì)應(yīng)結(jié)點(diǎn)及其兄弟/父結(jié)點(diǎn)進(jìn)行結(jié)點(diǎn)分裂/合并。

為什么用B+樹而不用B樹？

1. IO次數(shù)更少。每個(gè)結(jié)點(diǎn)能存的關(guān)鍵字?jǐn)?shù)量更多，所以高度更低，需要的磁盤IO次數(shù)更少。
2. 便于范圍查詢。只需要掃描一遍所有葉子就可以完成給定上下限的范圍查詢，而B樹需要進(jìn)行中序遍歷。
3. 查詢效率更穩(wěn)定。由于每次查詢都是從根到葉子，所以查詢復(fù)雜度穩(wěn)定為樹的高度。