第9章檢索

一、檢索的基本概念
二、線性表的檢索
- 2.1 順序檢索
- 2.2 二分法檢索（折半查找）
  - 2.2.1 二分法檢索（非遞回實作）（真題）（演算法）
- 2.3 分塊檢索
  - 2.3.1 分塊檢索索引表存盤結構
三、二叉排序樹
- 3.1 二叉排序樹的存盤結構
- 3.2 基于二叉排序樹檢索演算法（演算法）
- 3.3 基于二叉排序樹的結點的插入演算法（演算法）
- 3.4 生成一顆排序二叉樹
四、豐滿樹和平衡樹
- 4.1 豐滿樹（大綱未規定）
- 4.2 平衡二叉排序樹
- 4.3 AVL樹調整平衡的方法
  - 4.3.1 LL型平衡旋轉
  - 4.3.2 RR型平衡旋轉
  - 4.3.3 LR型平衡旋轉
  - 4.3.4 RL型平衡旋轉
- 4.4 生成一顆平衡二叉排序樹
五、二叉排序樹和Huffman樹
- 5.1 擴充二叉樹（大綱未規定）
- 5.2 二叉排序樹（大綱未規定）
- 5.3 Huffman樹
  - 5.3.1 構造Huffman樹
  - 5.3.2 通過Huffman演算法構造編碼樹
六、B樹
- 6.1 B-樹的定義
- 6.2 B-樹的基本操作
- 6.3 B+樹（大綱未規定）
七、散串列檢索
- 7.1 散列存盤
- 7.2 散列函式的構造
- 7.3 沖突處理
- 7.4 散串列檢索的應用
八、查找演算法的分析及應用（書中未給出）
九、演算法設計題
- 9.1 在給定查找樹中洗掉根結點值為 $a$ 的子樹（演算法）
- 9.2 判斷給定二叉樹是否為二叉排序樹（演算法）
十、錯題集

一、檢索的基本概念

檢索：確定資料元素集合中是否存在資料元素等于特定元素或是否存在元素滿足某種給定特征的程序

二、線性表的檢索

2.1 順序檢索

注：暴力搜索，不多贅述
順序檢索時平均查找次數：$ASL_{seq}=(n+1)/2$

2.2 二分法檢索（折半查找）

線性表結構：二分法檢索需要線性表結點已經按其關鍵字從小到大（或從大到小）排序
二分法檢索時平均查找次數：$ASL_{bins}\approx{log_2(n+1)-1}$

2.2.1 二分法檢索（非遞回實作）（真題）（演算法）

演算法步驟：
1. 獲取二分之后的中間結點的序號 $mid$
2. 讓待查找的資料元素 $key$ 和中間結點 $a[mid]$ 比較，成功則直接回傳
3. 失敗之后，判斷資料元素和中間結點的大小
  1. 如果中間結點大于資料元素，則在前半部分繼續二分檢索，$right$ 變成 $mid-1$（$mid-1$是因為 $mid$ 已經做出過判斷，不需要再次比較）
  2. 如果中間結點小于資料元素，則在后半部分繼續二分檢索，$left$ 變成 $mid+1$

int binsearch(int a[], int left, int right, int x) {
    int mid;
    while (left <= right) {
        mid = (left + right) / 2; // 二分
        if (a[mid] == x) return mid; // 檢索成功回傳
        if (a[mid] > x) right = mid - 1; // 繼續在前半部分進行二分檢索
        else left = mid + 1; // 繼續在后半部分進行二分檢索
    }
    return -1; // 當 left>right 時表示查找區間為空，檢索失敗
}

2.3 分塊檢索

分塊檢索思想：把線性表分成若干塊，每一塊中，結點的存放不一定有序，但塊與塊之間必須是分塊有序的（第一塊中的結點的值都小于第二塊中的結點值；第二塊中的結點值都小于第三塊中的結點值…）
分塊查找時平均查找長度為：假設線性表中共有 $n$ 個元素，且被均分成 $b$ 塊，則每塊中的元素個數 $s=n/b$，待查元素在索引表中的平均查找長度為 $E_1$，塊內查找時所需的平均查找長度為 $E_b$
1. 在順序檢索來確定塊時，分塊查找成功時的平均查找長度為 $ASL_{ids}=E_1+E_b=\frac{b+1}{2}+\frac{s+1}{2}=\frac{n/s+s}{2}+1=\frac{n+s^2}{2s}+1$
  1. 當 $s=\sqrt{n}$ 時，$ASL_{ids}$ 取最小值 $\sqrt{n}+1$ （最佳查找長度）
2. 在二分檢索來確定塊時，分塊查找成功時的平均查找長度為 $ASL'_{ids}=E_1+E_b\approx{log_2(b+1)}-1+\frac{s+1}{2}\approx{log_2(\frac{n}{s}+1)+\frac{s}{2}}$
演算法步驟：
1. 建立索引表（陣列）：
  1. 索引表結點中存盤兩個元素：一個元素表示某一塊在原陣列中的開始下標；另一個元素表示某一塊中最大的值
2. 讓被查找值和最大的值進行比較，獲取查找值在陣列中比較的下標范圍
3. 最后在該范圍內進行順序查找即可
圖分塊檢索：

2.3.1 分塊檢索索引表存盤結構

typedef int datatype;
// 索引表結點型別
typedef struct {
    datatype key;
    int address;
} indexnode;

三、二叉排序樹

二分檢索法的缺陷：二分檢索法雖然有較高的效率，但是要求被查找的一組資料有序，因此在這一組資料中增添洗掉很麻煩
二叉排序樹解決的問題：在檢索程序中不需要被查找的資料有序，即可擁有較高的查找效率，實作在資料查找程序中的增添和洗掉
二叉排序樹的性質：
1. 左子樹非空時，左子樹上的所有結點的值都小于根結點的值
2. 右子樹非空時，右子樹上的所有結點的值都大于根結點的值
3. 它的左、右子樹本身又各是一顆二叉排序樹
注：當二叉排序樹只有左（右）結點時，退化成一個有序的單鏈表（此時應該用二分檢索法進行檢索）
注：對二叉排序樹進行中序遍歷時可以得到按結點值遞增排序的結點序列
注：不同關鍵碼構造出不同的二叉排序樹的可能性有 $\frac{1}{n+1}C_{2n}^{n}$ 種
常用操作：
1. 基于二叉排序樹的結點的洗掉

3.1 二叉排序樹的存盤結構

typedef int datatype;
// 二叉排序樹結點定義
typedef struct node {
    datatype key; // 結點值
    struct node *lchild, *rchild; // 左、右孩子指標
} bsnode;
typedef bsnode *bstree;

3.2 基于二叉排序樹檢索演算法（演算法）

演算法步驟：
1. 當二叉樹為空樹時，檢索失敗
2. 如果二叉排序樹根結點的關鍵字等于待檢索的關鍵字，則檢索成功
3. 如果二叉排序樹根結點的關鍵字小于待檢索的關鍵字，則用相同的方法繼續在根結點的右子樹中檢索
4. 如果二叉排序樹根結點的關鍵字大于待檢索的關鍵字，則用相同的方法繼續在根結點的左子樹中檢索

typedef int datatype;
// 二叉排序樹結點定義
typedef struct node {
    datatype key; // 結點值
    struct node *lchild, *rchild; // 左、右孩子指標
} bsnode;
typedef bsnode *bstree;

// 遞回實作
void bssearch1(bstree t, datatype x, bstree *f, bstree *p) {
    // *p 回傳 x 在二叉排序中的地址；*f 回傳 x 的父結點位置
    *f = NULL;
    *p = t;
    while (*p) {
        if (x == (*p)->key) return;
        *f = *p;
        *p = (x < (*p)->key) ? (*p)->lchild : (*p)->rchild;
    }
    return;
}

// 非遞回實作
bstree bssearch2(bstree t, datatype x) {
    if (t == NULL || x == t->key) return t;
    if (x < t->key) return bssearch2(t->lchild, x); // 遞回地在左子樹檢索
    else return bssearch2(t->rchild, x); // 遞回地在右子樹檢索
}

3.3 基于二叉排序樹的結點的插入演算法（演算法）

演算法步驟：
1. 回圈查找插入位置的結點
2. 若二叉排序樹為空，則生成一個關鍵字為 $x$ 的新結點，并令其為二叉排序樹的根結點
3. 否則，將待插入的關鍵字 $x$ 與根結點的關鍵字進行比較，若二者相等，則說明樹中已有關鍵字 $x$，無須插入
4. 若 $x$ 小于根結點的關鍵字，則將 $x$ 插入到該樹的左子樹中，否則將 $x$ 插入到該樹的右子樹
5. 將 $x$ 插入子樹的方法與在整個樹中的插入方法是相同的，如此進行下去，直到 $x$ 作為一個新的葉結點的關鍵字插入到二叉排序樹中，或者直到發現樹中已有此關鍵字為止

typedef int datatype;
// 二叉排序樹結點定義
typedef struct node {
    datatype key; // 結點值
    struct node *lchild, *rchild; // 左、右孩子指標
} bsnode;
typedef bsnode *bstree;

void insertbstree(bstree *t, datatype x) {
    bstree f = NULL, p;
    p = *t;

    // 查找插入位置
    while (p) {
        if (x == p->key) return; // 若二叉排序中已有 x，無需插入
        f = p; // *f 用于保存新結點的最終插入位置
        p = (x < p->key) ? p->lchild : p->rchild;
    }

    // 生成待插入的新結點
    p = (bstree) malloc(sizeof(bsnode));
    p->key = x;
    p->lchild = p->rchild = NULL;

    // 原樹為空
    if (*t == NULL) *t = p;
    else if (x < f->key) f->lchild = p;
    else f->rchild = p;
}

3.4 生成一顆排序二叉樹

演算法步驟：
1. 回圈輸入關鍵字，然后使用 $3.3$ 的插入演算法把關鍵字插入二叉排序樹
圖生成二叉排序樹：

四、豐滿樹和平衡樹

豐滿樹和平衡樹解決的問題：保證在樹中插入或洗掉結點時保持樹的 “平衡”，使之盡可能保持二叉樹的性質又保證樹的高度盡可能地為 $O(log_2n)$

4.1 豐滿樹（大綱未規定）

豐滿樹：任意兩個非雙孩子結點的高度之差的絕對值要小于等于 $1$，即子女結點個數小于 $2$ 的結點只出現在樹的最低兩層中
常用操作：
1. 建立豐滿樹

4.2 平衡二叉排序樹

平衡二叉樹（$AVL$ 樹）：它的左子樹和右子樹都是平衡二叉樹，**且左子樹和右子樹的高度之差的絕對值不超過 $1$ **
平衡因子：結點的左子樹高度與右子樹高度之差（平衡二叉樹的任意結點的平衡因子絕對值小于等于 $1$）
豐滿樹和平衡樹：豐滿樹一定是平衡樹，平衡樹卻不一定是豐滿樹
常用操作：
1. 基于 $AVL$ 樹的結點插入演算法
平衡二叉排序樹最大深度求法：假設 $N_h$ 表示深度為 $h$ 的平衡二叉樹中含有的最少的結點數目，那么，$N_0=0$，$N_1=1$，$N_2=2$，并且 $N_h=N_{h-1}+N_{h-2}+1$

4.3 AVL樹調整平衡的方法

4.3.1 LL型平衡旋轉

$LL$ 型平衡旋轉：
1. 由于在 $A$ 的左孩子的左子樹上插入新結點，使 $A$ 的平衡度由 $1$ 增至 $2$ ，致使以 $A$ 為根的子樹失去平衡，如圖$9.9（a）$ 所
2. 示此時應進行一次順時針旋轉，“提升” $B$ （即 $A$ 的左孩子）為新子樹的根結點
3. $A$ 下降為 $B$ 的右孩子
4. 把 $B$ 原來的右子樹 $B_r$ 調整為 $A$ 的左子樹
圖LL型平衡旋轉

4.3.2 RR型平衡旋轉

$RR$ 型平衡旋轉：
1. 由于在 $A$ 的右孩子的右子樹上插入新結點，使A的平衡度由 $-1$ 變為 $-2$，致使以 $A$ 為根的子樹失去平衡，如圖 $9.9（b）$ 所示
2. 此時應進行一次逆時針旋轉，“提升” $B$ （即 $A$ 的右孩子）為新子樹的根結點
3. $A$ 下降為 $B$ 的左孩子
4. 把 $B$ 原來的左子樹 $B_L$ 調整為 $A$ 的右子樹
圖RR型平衡旋轉

4.3.3 LR型平衡旋轉

$LR$ 型平衡旋轉（$A$ 的左孩子的右孩子（$LR$）插入 $A$ 和 $A$ 的左孩子 $B$ 之間，之后做 $LL$ 型平衡旋轉）：
1. 由于在 $A$ 的左孩子的右子樹上插入新結點，使 $A$ 的平衡度由 $1$ 變成 $2$，致使以 $A$ 為根的子樹失去平衡，如圖 $9.9（c）$ 所示
2. 此時應進行兩次旋轉操作（先逆時針，后順時針），即 “提升” $C$ （即 $A$ 的左孩子的右孩子）為新子樹的根結點
3. $A$ 下降為 $C$ 的右孩子
4. $B$ 變為 $C$ 的左孩子
5. $C$ 原來的左子樹 $C_L$ 調整為 $B$ 現在的右子樹
6. $C$ 原來的右子樹 $C_r$ 調整為 $A$ 現在的左子樹
圖LR型平衡旋轉

4.3.4 RL型平衡旋轉

$RL$ 型平衡旋轉（$A$ 的右孩子的左孩子（$RL$）插入 $A$ 和 $A$ 的右孩子 $B$ 之間，之后做 $RR型$ 平衡旋轉）：
1. 由于在 $A$ 的右孩子的左子樹上插入新結點，使A的平衡度由 $-1$ 變成 $-2$，致使以 $A$ 為根的子樹失去平衡，如圖 $9.9（d）$所示
2. 此時應進行兩旋轉操作（先順時針，后逆時針），即 “提升” $ C$（即 $A$ 的右孩子的左孩子）為新子樹的根結點
3. $A$ 下降 $C$ 的左孩子
4. $B$ 變為 $C$ 的右孩子
5. $C$ 原來的左子樹 $C_L$ 調整為 $A$ 現在的右子樹
6. $C$ 原來的右子樹 $C_r$ 調整為 $B$ 現在的左子樹，
圖RL型平衡旋轉

4.4 生成一顆平衡二叉排序樹

演算法步驟：
1. 插入：不考慮結點的平衡度，使用在二叉排序樹中插入新結點的方法，把結點 $k$ 插入樹中，同時置新結點的平衡度為 $0$
2. 調整平衡度：假設 $k0，k1，…，km=k$ 是從根 $k_0$ 到插入點 $k$ 路徑上的結點，由于插入了結點 $k$，就需要對這條路徑上的結點的平衡度進行調整（調整平衡度參考上述四種（$LL、RR、LR、RL$）方法）
3. 改組：改組以 $k_j$ 為根的子樹除了滿足新子樹高度要和原來以 $k_j$ 為根子樹的高度相同外，還需使改造后的子樹是一棵平衡二叉排序樹
圖生成一顆AVL樹

五、二叉排序樹和Huffman樹

5.1 擴充二叉樹（大綱未規定）

5.2 二叉排序樹（大綱未規定）

5.3 Huffman樹

帶權外部路徑長度：$WPL=\sum_{i=1}^{n}W_{ki}*(\lambda{k_i})$
1. $n$ 個結點 $k_1,k_2,\cdots,k_n$，它們的權分別是 $W(k_i)$
2. $\lambda{k_i}$ 是從根結點到達外部結點 $k_i$ 的路徑長度
$huffman$ 樹：具有最小帶權外部路徑長度的二叉樹
演算法步驟：
1. 根據給定的 $n$ 個權值 $\{w_1,w_2,\cdots,w_n\}$ 構造 $n$ 棵二叉樹的集合 $F=\{T_1,T_2,\cdots,T_n\}$，其中每棵二叉樹 $T_i$ 中只有一個帶權為 $w_i$ 的根結點，其左、右子樹均為空
2. 在 $F$ 中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點權值為其左、右子樹根結點的權值之和
3. 在 $F$ 中用新得到的二叉樹代替這兩棵樹
4. 重復步驟 $2、3$，直到 $F$ 中只含有一棵樹為止

5.3.1 構造Huffman樹

對于結點序列 $6、10、16、20、30、24$ ，構造 $huffman$ 樹的程序如下：
圖構造huffman樹：

5.3.2 通過Huffman演算法構造編碼樹

注：出現頻率越大的字符其編碼越短
圖huffman編碼：
字符平均編碼長度為：$((6+10)*4+16*3+(20+24+30)*2)/106=2.45$

六、B樹

B樹：稱為多路平衡查找樹，也稱為 “B-樹”，主要針對較大的、存放在外存盤器上的檔案，適合在磁盤等直接存取設備上組織動態的索引表

6.1 B-樹的定義

B-樹：一種平衡的多路查找樹，一顆 $m(m\geq{3})$ 階的B-樹，或為空樹，或為滿足下列特性的 $m$ 叉樹
1. 樹中的每個結點至多有 $m$ 棵子樹
2. 若根結點不是葉子結點，則至少有兩棵子樹
3. 所有的非終端結點中包含下列資訊 $(sn,p_0,k_1,p_1,k_2,p_2,\ldots,k_n,p_n)$
  1. 其中 $k_i(1\leq{i}\leq{n})$ 為關鍵字，且 $k_i<k_i+1(1\leq{i}\leq{n})$
  2. $p_j(0\leq{j}\leq{n})$ 為指向子樹根結點的指標，且 $p_j(0\leq{j}<n)$ 所指子樹中所有結點的關鍵字均小于 $k_j+1$
  3. $p_n$ 所指子樹中所有結點的關鍵字均大于 $k_n$
  4. $n(\lceil{m/2}\rceil-1\leq{n}\leq{m-1})$ 為關鍵字的個數（$n+1$ 為子樹個數）
4. 除根結點之外所有非終端結點至少有棵子樹，也即每個非根結點至少應有 $\lceil{m/2}\rceil-1$ 個關鍵字
5. 所有的葉子結點都出現在同一層上，并且不帶資訊（可以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指標為空）
圖3階B-樹：

6.2 B-樹的基本操作

基于B-樹的查找
基于B-樹的插入運算
基于B-樹的洗掉運算

6.3 B+樹（大綱未規定）

七、散串列檢索

7.1 散列存盤

散列存盤的基本思想：以關鍵碼的值為變數，通過一定的函式關系（稱為散列（$Hash$）函式），計算出對應的函式值，以這個值作為結點的存盤地址
沖突：兩個不同的關鍵字具有相同的存放地址
負載因子：$\frac{散串列中結點的數目}{基本區域能容納的結點樹}$
1. 注：負載因子越小，空間浪費越多；負載因子越大，沖突可能性越高（負載因子大于 $1$ 時，一定會有沖突）

7.2 散列函式的構造

除余法（大概率）：使用略小于 $Hash$ 地址集合中地址個數 $m$ 的質數 $p$ 來除關鍵字
1. 散列函式： $H(key) = key\%p$
2. 注：除余法的 $p$ 的選擇不當，容易發生沖突
平方取中法：取關鍵字平方后的中間幾位為 $Hash$ 地址，所取的位數和 $Hash$ 地址位數相同
折疊法：讓關鍵字分割成位數相同的幾部分，然后選取這幾部分的疊加和作為 $Hash$ 地址
數字分析法：對于關鍵字的位數比存盤區域的地址碼位數多的情況下，對關鍵字分析，丟掉分布不均勻的位，留下分布均勻的位作為 $Hash$ 地址
直接地址法（大概率）：取關鍵字或關鍵字的某個線性函式值為哈希地址
1. 散列函式：$H(key)=key\,或\,H(key)=a*key+b$
2. 注：直接地址法對于不同的關鍵字，不會產生沖突，容易造成空間的大量浪費

7.3 沖突處理

開放定址法：發生沖突時，按照某種方法繼續探測基本表中的其他存盤單元，直到找到一個開放的地址（空位置）為止
1. 開放定址法的一般形式：$H_i(k) = (H(k)+d_i)\,mod\,m$，其中 $H(k)$ 為關鍵字為 $k$ 的直接哈希地址，$m$ 為哈希表長，$d_i$ 為每次再探測時的地址增量
  1. 線性探測再散列：$d_i = 1,2,3,\cdots,m-1$
  2. 二次探測再散列：$d_i=1^2,{-1}^2,2^2,{-2}^2,\cdots,k^2,{-k}^2(k\leq{m/2})$
  3. 隨機探測再散列：$d_i = 亂數序列$
2. 聚集：幾個 $Hash$ 地址不同的關鍵字爭奪同一個后繼 $Hash$ 地址的現象
3. 開放定址法容易發生聚集現象，尤其是采用線性探測再散列
4. 圖開放定址法：
再哈希法：某個元素 $k$ 在原散列函式 $H(k)$ 的映射下與其他資料發生碰撞時，采用另外一個 $Hash$ 函式 $H_i(k)$ 計算 $k$ 的存盤地址
1. 注：該方法不容易發生 “聚集”，但增加了計算的時間
拉鏈法：把所有關鍵字為同義詞的結點鏈接在同一個單鏈表中，若選定的散串列長度為 $m$，則可以把散串列定義為一個由 $m$ 個頭指標組成的指標陣列 $T[0\ldots{m-1}]$，凡是散列地址為 $i$ 的結點，均插入到以 $T[i]$ 為頭指標的單鏈表中
1. 注：拉鏈法的指標需要額外的空間，因此當結點規模較小時，開放定址法更加節省空間
2. 圖拉鏈法：

開放定址法、再哈希法、拉鏈法的比較

	開放定址法	再哈希法	拉鏈法
優點	不需要額外的計算時間和空間	不易 “聚集”	無 “聚集”；非同義詞不會沖突
缺點	容易發生 “聚集” 現象	增加了計算時間	需要額外的空間

7.4 散串列檢索的應用

將關鍵字序列 $(7、8、30、11、18、9、14)$ 散列存盤到散串列中，散串列的存盤空間是一個下標從 $0$ 開始的一維陣列，散列函式為： $H(key) = (key*3) MOD 7$，處理沖突采用線性探測再散列法，要求裝載因子為 $0.7$
1. 請畫出所構造的散串列
2. 分別計算等概率情況下查找成功和查找不成功的平均查找長度

八、查找演算法的分析及應用（書中未給出）

九、演算法設計題

9.1 在給定查找樹中洗掉根結點值為 $a$ 的子樹（演算法）

設 $T$ 是一棵給定的查找樹，試撰寫一個在樹 $T$ 中洗掉根結點值為 $a$ 的子樹的程式，要求在洗掉的程序中釋放該子樹中所有結點所占用的存盤空間，這里假設樹 T 中的結點采用二叉鏈表存盤結構

演算法步驟：
1. 注：洗掉二叉樹可以采用后序遍歷方法，先洗掉左子樹，再洗掉右子樹，最后洗掉根結點
2. 先在指定的樹中查找值為 a 的結點，找到后洗掉該棵子樹

typedef int datatype;
// 二叉樹結點定義
typedef struct node {
    datatype data;
    struct node *lchild, *rchild;
} bintnode;
typedef bintnode *bintree;

// 洗掉以 t 為根的二叉樹
void deletetree(bintree *t) {
    if (*t) {
        deletetree(&(*t)->lchild); // 遞回洗掉左子樹
        deletetree(&(*t)->rchild);// 遞回洗掉右子樹
        free(*t); // 洗掉根結點
    }
}

// 洗掉二叉樹中以根結點值為 a 的子樹
void deletea(bintree *t, datatype a) {
    bintree pre = NULL, p = *t;

    // 查找值為 a 的結點
    while (p && p->data != a)
    {
        pre = p;
        p = (a < p->data) ? p->lchild : p->rchild;
    }
    
    if (!pre) *t = NULL;    // 樹根
    else  // 非樹根
    if (pre->lchild == p) pre->lchild = NULL;
    else pre->rchild = NULL;
    deletetree(&p); // 洗掉以 p 為根的子樹
}

9.2 判斷給定二叉樹是否為二叉排序樹（演算法）

試寫一演算法判別給定的二叉樹是否為二叉排序樹，設此二叉樹以二叉鏈表為存盤結構，且樹中結點的關鍵字均不相同

演算法步驟：
1. 判定二叉樹是否為二叉排序樹可以建立在二叉樹中序遍歷的基礎上，
2. 在遍歷中附設一指標 $pre$ 指向樹中當前訪問結點的中序直接前驅，
3. 每訪問一個結點就比較前驅結點 $pre$ 和此結點是否有序
4. 若遍歷結束后各結點和其中序直接前驅均滿足有序，則此二叉樹即為二叉排序樹，否則不是二叉排序樹

typedef int datatype;
typedef struct node {
    datatype data;
    struct node *lchild, *rchild;
} bintnode;
typedef bintnode *bintree;

// 函式 bisorttree()用于判斷二叉樹 t 是否為二叉排序樹，
// 初始時 pre=NULL；flag=1；
// 結束時若 flag==1，則此二叉樹為二叉排序樹，否則此二叉樹不是二叉排序樹，
void bisorttree(bintree t, bintree *pre, int *flag) {
    if (t && *flag == 1) {
        bisorttree(t->lchild, pre, flag); // 判斷左子樹
        // 訪問中序序列的第一個結點時不需要比較
        if (pre == NULL) {
            *flag = 1;
            *pre = t;
        } else { // 比較 t 與中序直接前驅 pre 的大小（假定無相同關鍵字）
            if ((*pre)->data < t->data) {
                *flag = 1;
                *pre = t;
            } else *flag = 0; //  pre 與 t 無序
        }
        bisorttree(t->rchild, pre, flag); // 判斷右子樹
    }
}

十、錯題集

設順序存盤的線性表共有 $123$ 個元素，按分塊查找的要求等分成 $3$ 塊，若對索引表采用順序查找來確定塊，并在確定的塊中進行順序查找（尋找確定的塊還需要 $2$ 步），則在查找概率相等的情況下，分塊查找成功時的平均查找長度為 $23$
有資料 ${53，30，37，12，45，24，96}$ ，從空二叉樹開始逐步插入資料形成二叉排序樹，若希望高度最小，則應該選擇下列的序列輸入，答案 $37,24,12,30,53,45,96$
1. 要創建一顆高度最小的二叉排序樹，就必須讓左右子樹的結點個數越接近越好
  1. 由于給定的是一個關鍵字有序序列 $a[start\ldots{end}]$，讓其中間位置的關鍵字 $a[mid]$ 作為根結點
  2. 左序列 $a[start\dots{mid-1}]$
    構造左子樹
  3. 右序列 $a[mid+1\ldots{end}]$ 構造右子樹
若在 $9$ 階 B-樹中插入關鍵字引起結點分裂，則該結點在插入前含有的關鍵字個數為 $8$
1. 注：如果是 $m$ 階，答案是 $m-1$
下列敘述中，不符合 $m$ 階B樹定義要求的是葉結點之間通過指標鏈接

在分塊檢索中，對 $256$ 個元素的線性表分成多少 $16$ 塊最好，每塊的最佳長度（平均查找長度）為 $17$，若每塊

的長度為 $8$，其平均檢索的長度在順序檢索時為 $21$，在二分檢索時為 $9$

 1. 假設線性表中共有 $n$ 個元素，且被均分成 $b$ 塊，則每塊中的元素個數 $s=n/b$，待查元素在索引表中的平均查找長度為 $E_1$，塊內查找時所需的平均查找長度為 $E_b$
 2. 在順序檢索來確定塊時，分塊查找成功時的平均查找長度為 $ASL_{ids}=E_1+E_b=\frac{b+1}{2}+\frac{s+1}{2}=\frac{n/s+s}{2}+1=\frac{n+s^2}{2s}+1$
  	1. 當 $s=\sqrt{n}$ 時，$ASL_{ids}$ 取最小值 $\sqrt{n}+1$

在二分檢索來確定塊時，分塊查找成功時的平均查找長度為 $ASL'_{ids}=E_1+E_b\approx{log_2(b+1)}-1+\frac{s+1}{2}\approx{log_2(\frac{n}{s}+1)+\frac{s}{2}}$

設有關鍵碼 A、B、C 和 D，按照不同的輸入順序，共可能組成 $14$ 種不同的二叉排序樹
1. 使用公式：不同關鍵碼構造出不同的二叉排序樹的可能性有 $\frac{1}{n+1}C_{2n}^{n}$ 種
含有 $12$ 個結點的平衡二叉樹的最大深度是多少 $4$（設根結點深度為 $0$）、$5$（設根結點深度為 $1$），并畫出一棵這樣的樹
1. 假設 $N_h$ 表示深度為 $h$ 的平衡二叉樹中含有的最少的結點數目
2. 那么，$N_0=0$，$N_1=1$，$N_2=2$，并且 $N_h=N_{h-1}+N_{h-2}+1$，根據平衡二叉樹平衡二叉樹的這一性質，$N_5=12$，如果根結點深度為 $0$，則最大深度為 $4$
3. 圖習題9-6：

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/155597.html

標籤：其他

上一篇：第8章圖

下一篇：請問dragonboard 410c的android原始碼有沒有好的下載方法

第9章 檢索

第9章 檢索

一、檢索的基本概念

二、線性表的檢索

2.1 順序檢索

2.2 二分法檢索（折半查找）

2.2.1 二分法檢索（非遞回實作）（真題）（演算法）

2.3 分塊檢索

2.3.1 分塊檢索索引表存盤結構

三、二叉排序樹

3.1 二叉排序樹的存盤結構

3.2 基于二叉排序樹檢索演算法（演算法）

3.3 基于二叉排序樹的結點的插入演算法（演算法）

3.4 生成一顆排序二叉樹

四、豐滿樹和平衡樹

4.1 豐滿樹（大綱未規定）

4.2 平衡二叉排序樹

4.3 AVL樹調整平衡的方法

4.3.1 LL型平衡旋轉

4.3.2 RR型平衡旋轉

4.3.3 LR型平衡旋轉

4.3.4 RL型平衡旋轉

4.4 生成一顆平衡二叉排序樹

五、二叉排序樹和Huffman樹

5.1 擴充二叉樹（大綱未規定）

5.2 二叉排序樹（大綱未規定）

5.3 Huffman樹

5.3.1 構造Huffman樹

5.3.2 通過Huffman演算法構造編碼樹

六、B樹

6.1 B-樹的定義

6.2 B-樹的基本操作

6.3 B+樹（大綱未規定）

七、散串列檢索

7.1 散列存盤

7.2 散列函式的構造

7.3 沖突處理

7.4 散串列檢索的應用

八、查找演算法的分析及應用（書中未給出）

九、演算法設計題

9.1 在給定查找樹中洗掉根結點值為 \(a\) 的子樹（演算法）

9.2 判斷給定二叉樹是否為二叉排序樹（演算法）

十、錯題集

第9章檢索

第9章檢索