規(guī)則：

• 左指針指向第一個孩子

• 右指針指向自己的第一個兄弟

森林和二叉樹的轉(zhuǎn)換：

• 本質(zhì)：用二叉鏈表存儲森林

• 規(guī)則：

  • 各個樹的根結(jié)點視為兄弟關(guān)系

  • 左指針指向第一個孩子

  • 右指針指向自己的第一個兄弟

樹和森林的遍歷

樹的先根遍歷：

• 先根遍歷：若樹非空，先訪問根結(jié)點，再依次對每棵子樹進(jìn)行先根遍歷。

• 樹的先根遍歷序列與這棵樹相應(yīng)二叉樹的先序序列相同。

樹的后根遍歷：

• 后根遍歷：若樹非空，先依次對每棵子樹進(jìn)行后根遍歷，最后再訪問根結(jié)點

• 樹的后根遍歷序列與這棵樹相應(yīng)二叉樹的中序序列相同

• 也被稱為深度優(yōu)先遍歷

樹的層次遍歷：

• 用隊列實現(xiàn)，又被稱為廣度優(yōu)先遍歷

• 步驟

  • 若樹非空，則根結(jié)點入隊

  • 若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊

  • 重復(fù)第二步直到隊列為空

森林的先序遍歷：

• 若森林為非空，則按如下規(guī)則進(jìn)行遍歷：

  • 訪問森林中第一棵樹的根結(jié)點。

  • 先序遍歷第一棵樹中根結(jié)點的子樹森林。

  • 先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

• 效果等同于依次對各個樹進(jìn)行先根遍歷

• 用孩子兄弟表示法轉(zhuǎn)換為二叉樹，效果等同于依次對二叉樹的先序遍歷

森林的中序遍歷：

• 若森林為非空，則按如下規(guī)則進(jìn)行遍歷：

  • 中序遍歷森林中第一棵樹的根結(jié)點的子樹森林。

  • 訪問第一棵樹的根結(jié)點。

  • 中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。

• 效果等同于依次對各個樹進(jìn)行后根遍歷

• 用孩子兄弟表示法轉(zhuǎn)換為二叉樹，效果等同于依次對二叉樹的中序遍歷

二叉排序樹（BST）

定義：

• 二叉排序樹，又稱二叉查找樹（BST，Binary Search Tree）

• 一棵二叉樹或者是空二叉樹，或者是具有如下性質(zhì)的二叉樹：

  • 左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字

  • 右子樹上所有結(jié)點的關(guān)鍵字均大于根結(jié)點的關(guān)鍵字

  • 左子樹和右子樹又各是一棵二叉排序樹

• 即左子樹結(jié)點值< 根結(jié)點值< 右子樹結(jié)點值

• 進(jìn)行中序遍歷，可以得到一個遞增的有序序列

• 二叉排序樹可用于元素的有序組織、搜索

BST的查找：

• 若樹非空，目標(biāo)值與根結(jié)點的值比較：

  • 若相等，則查找成功

  • 若小于根結(jié)點，則在左子樹上查找，否則在右子樹上查找。

  • 查找成功，返回結(jié)點指針；

  • 查找失敗返回NULL

• 遞歸實現(xiàn)的最壞空間復(fù)雜度為O(h),普通實現(xiàn)的最壞空間復(fù)雜度為O(1)

BST的插入：

• 若原二叉排序樹為空，則直接插入結(jié)點；

• 否則，若關(guān)鍵字k小于根結(jié)點值，則插入到左子樹，若關(guān)鍵字k大于根結(jié)點值，則插入到右子樹

• 遞歸實現(xiàn)的最壞空間復(fù)雜度為O(h)

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

注意：不同的關(guān)鍵字序列可能得到同款二叉排序樹，也可能得到不同款二叉排序樹

二叉排序樹的刪除：

• 先搜索找到目標(biāo)結(jié)點：

  • 若被刪除結(jié)點z是葉結(jié)點，則直接刪除，不會破壞二叉排序樹的性質(zhì)。

  • 若結(jié)點z只有一棵左子樹或右子樹，則讓z的子樹成為z父結(jié)點的子樹，替代z的位置。

  • 若結(jié)點z有左、右兩棵子樹，則令z的直接后繼（或直接前驅(qū)）替代z，然后從二叉排序樹中刪去這個直接后繼（或直接前驅(qū)），這樣就轉(zhuǎn)換成了第一或第二種情況。

    • z的后繼：z的右子樹中最左下結(jié)點，是右子樹最小的結(jié)點（該結(jié)點一定沒有左子樹）

    • z的前驅(qū)：z的左子樹中最右下結(jié)點，是左子樹中最大的結(jié)點（該結(jié)點一定沒有右子樹）

查找效率分析：

• 查找長度：在查找運算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度，反映了查找操作時間復(fù)雜度

• 查找成功的平均查找長度ASL（Average Search Length）：（各層（層數(shù)*層結(jié)點個數(shù)）相加）/總結(jié)點個數(shù)

• 最壞情況：每個結(jié)點只有一個分支，樹高h(yuǎn)=結(jié)點數(shù)n。平均查找長度=O(n)

• 最好情況：n個結(jié)點的二叉樹最小高度為(log2n)+ 1。平均查找長度= O(log2n)

平衡二叉樹（AVL）

定義：

• 平衡二叉樹（Balanced Binary Tree），簡稱平衡樹（AVL樹）——樹上任一結(jié)點的左子樹和右子樹的高度之差不超過1

• 結(jié)點的平衡因子=左子樹高-右子樹高

• 平衡二叉樹結(jié)點的平衡因子的值只可能是?1、0或1

• 只要有任一結(jié)點的平衡因子絕對值大于1，就不是平衡二叉樹

平衡二叉樹的插入：

• 在二叉排序樹中插入新結(jié)點后，如何保持平衡？

  • 查找路徑上的所有結(jié)點都有可能受到影響

  • 從插入點往回找到第一個不平衡結(jié)點，調(diào)整以該結(jié)點為根的子樹

  • 每次調(diào)整的對象都是“最小不平衡子樹”

  • 在插入操作中，只要將最小不平衡子樹調(diào)整平衡，則其他祖先結(jié)點都會恢復(fù)平衡

  • 插入操作導(dǎo)致“最小不平衡子樹”高度+1，經(jīng)過調(diào)整后高度恢復(fù)

• 調(diào)整最小不平衡子樹

調(diào)整最小不平衡子樹：

• 只有假設(shè)所有子樹的高度都是H才能保證出現(xiàn)最小不平衡子樹恒定

• 目標(biāo)：

  • 恢復(fù)平衡

  • 保持二叉排序樹特性

• 二叉排序樹的特性：左子樹結(jié)點值< 根結(jié)點值< 右子樹結(jié)點值

• LL平衡旋轉(zhuǎn)（右單旋轉(zhuǎn)）

  • 由于在結(jié)點A的左孩子（L）的左子樹（L）上插入了新結(jié)點，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要一次向右的旋轉(zhuǎn)操作

  • 將A的左孩子B向右上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向右下旋轉(zhuǎn)成為B的右子樹的根結(jié)點，而B的原右子樹則作為A結(jié)點的左子樹

• RR平衡旋轉(zhuǎn)（左單旋轉(zhuǎn)）

  • 由于在結(jié)點A的右孩子（R）的右子樹（R）上插入了新結(jié)點，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要一次向左的旋轉(zhuǎn)操作

  • 將A的右孩子B向左上旋轉(zhuǎn)代替A成為根結(jié)點，將A結(jié)點向左下旋轉(zhuǎn)成為B的左子樹的根結(jié)點，而B的原左子樹則作為A結(jié)點的右子樹

• 右旋和左旋的代碼實現(xiàn)思路

• LR平衡旋轉(zhuǎn)（先左后右雙旋轉(zhuǎn)）

  • 由于在A的左孩子（L）的右子樹（R）上插入新結(jié)點，A的平衡因子由1增至2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先左旋轉(zhuǎn)后右旋轉(zhuǎn)

  • 先將A結(jié)點的左孩子B的右子樹的根結(jié)點C向左上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該C結(jié)點向右上旋轉(zhuǎn)提升到A結(jié)點的位置

• RL平衡旋轉(zhuǎn)（先右后左雙旋轉(zhuǎn)）

  • 由于在A的右孩子（R）的左子樹（L）上插入新結(jié)點，A的平衡因子由-1減至-2，導(dǎo)致以A為根的子樹失去平衡，需要進(jìn)行兩次旋轉(zhuǎn)操作，先右旋轉(zhuǎn)后左旋轉(zhuǎn)

  • 先將A結(jié)點的右孩子B的左子樹的根結(jié)點C向右上旋轉(zhuǎn)提升到B結(jié)點的位置，然后再把該C結(jié)點向左上旋轉(zhuǎn)提升到A結(jié)點的位置

查找效率分析：

• 若樹高為h，則最壞情況下，查找一個關(guān)鍵字最多需要對比h次，即查找操作的時間復(fù)雜度不可能超過O(h)

• 平衡二叉樹——樹上任一結(jié)點的左子樹和右子樹的高度之差不超過1

• 假設(shè)以nh表示深度為h的平衡樹中含有的最少結(jié)點數(shù)。

• 則有n0 = 0, n1 = 1, n2 = 2，并且有nh = n(h?1) + n(h?2) + 1

• 可以證明含有n個結(jié)點的平衡二叉樹的最大深度為O(log2n) ，平衡二叉樹的平均查找長度為O(log2n)

哈夫曼樹

帶權(quán)路徑長度：

• 結(jié)點的權(quán)：有某種現(xiàn)實含義的數(shù)值（如：表示結(jié)點的重要性等）

• 結(jié)點的帶權(quán)路徑長度：從樹的根到該結(jié)點的路徑長度（經(jīng)過的邊數(shù)）與該結(jié)點上權(quán)值的乘積

• 樹的帶權(quán)路徑長度：樹中所有葉結(jié)點的帶權(quán)路徑長度之和（WPL, Weighted Path Length）

哈夫曼樹的定義：

在含有n個帶權(quán)葉結(jié)點的二叉樹中，其中帶權(quán)路徑長度（WPL）最小的二叉樹稱為哈夫曼樹，也稱最優(yōu)二叉樹

哈夫曼樹的構(gòu)造：

• 給定n個權(quán)值分別為w1, w2,…, wn的結(jié)點，構(gòu)造哈夫曼樹的算法描述如下：

  • 將這n個結(jié)點分別作為n棵僅含一個結(jié)點的二叉樹，構(gòu)成森林F。

  • 構(gòu)造一個新結(jié)點，從F中選取兩棵根結(jié)點權(quán)值最小的樹作為新結(jié)點的左、右子樹，并且將新結(jié)點的權(quán)值置為左、右子樹上根結(jié)點的權(quán)值之和。

  • 從F中刪除剛才選出的兩棵樹，同時將新得到的樹加入F中。

  • 重復(fù)步驟2和3，直至F中只剩下一棵樹為止。

• 每個初始結(jié)點最終都成為葉結(jié)點，且權(quán)值越小的結(jié)點到根結(jié)點的路徑長度越大

• 哈夫曼樹的結(jié)點總數(shù)為2n ? 1

• 哈夫曼樹中不存在度為1的結(jié)點。

• 哈夫曼樹并不唯一，但WPL必然相同且為最優(yōu)

哈夫曼編碼：

• 固定長度編碼：每個字符用相等長度的二進(jìn)制位表示

• 可變長度編碼：允許對不同字符用不等長的二進(jìn)制位表示

• 若沒有一個編碼是另一個編碼的前綴，則稱這樣的編碼為前綴編碼，如果沒有前綴編碼容易出現(xiàn)歧義

• 由哈夫曼樹得到哈夫曼編碼：字符集中的每個字符作為一個葉子結(jié)點，各個字符出現(xiàn)的頻度作為結(jié)點的權(quán)值，根據(jù)之前介紹的方法構(gòu)造哈夫曼樹

并查集

定義：

并查集（Disjoint Set）是邏輯結(jié)構(gòu)集合的一種具體實現(xiàn)，只進(jìn)行“并”和“查”兩種基本操作

并查集的基本操作：

• Find：查操作，確定一個指定元素所屬集合

• Union：并操作，將兩個不相交的集合合并為一個

初始化：

S[]實際上就是樹的雙親表示法，里面的值就是自己對應(yīng)根結(jié)點的下標(biāo)

并、查：

時間復(fù)雜度分析：

• Find操作最壞時間復(fù)雜度O(n)

• Union操作時間復(fù)雜度O(1)

Union操作的優(yōu)化：

• 在每次Union操作構(gòu)建樹的時候，盡量讓樹不長高

• 用根結(jié)點的絕對值表示樹的結(jié)點總數(shù)（根結(jié)點從-1改成-（樹的總結(jié)點））

• Union操縱，讓小樹合并到大樹

• 該方法構(gòu)造的樹高不超過[log2n]+1

• Find最壞時間復(fù)雜度變?yōu)镺(log2n)

并查集的壓縮路徑

• 核心想法就是讓樹越來越“矮”

• Find操作先找到根結(jié)點，再將查找路徑上所有結(jié)點都掛到根結(jié)點下

• 這樣的操縱可以讓樹的告訴不超過O(α(n))

• O(α(n))是一個增長很緩慢的函數(shù)，對于常見的n值，O(α(n))通常<=4

• 因此優(yōu)化后的并查集Find、Union操作時間開銷都很低

圖

圖的基本概念

定義：

• 圖G由頂點集V和邊集E組成，記為G = (V, E)，其中V(G)表示圖G中頂點的有限非空集；

• E(G)表示圖G中頂點之間的關(guān)系（邊）集合。

• 若V = {v1, v2, … , vn}，則用|V|表示圖G中頂點的個數(shù)，也稱圖G的階，E = {(u, v) | u∈V, v∈V}，用|E|表示圖G中邊的條數(shù)。

• 注意：線性表可以是空表，樹可以是空樹，但圖不可以是空，即V一定是非空集

無向圖、有向圖：

無向圖：

• 若E是無向邊（簡稱$）的有限集合時，則圖G為無向圖。

• 邊是頂點的無序?qū)Γ洖?v, w)或(w, v)，因為(v, w) = (w, v)，其中v、w是頂點?？梢哉f頂點w和頂點v互為鄰接點。

• 邊(v, w)依附于頂點w和v，或者說邊(v, w)和頂點v、w相關(guān)聯(lián)。

有向圖：

• 若E是有向邊（也稱!）的有限集合時，則圖G為有向圖。

• 弧是頂點的有序?qū)?，記?lt;v, w>，其中v、w是頂點，v稱為弧尾，w稱為弧頭，<v, w>稱為從頂點v到頂點w的弧，也稱v鄰接到w，或w鄰接自v。

• 注意：<v, w> ≠ <w, v>

簡單圖、多重圖：

數(shù)據(jù)結(jié)構(gòu)課程只探討“簡單圖”

簡單圖：

• 不存在重復(fù)邊

• 不存在頂點到自身的邊

多重圖：

• 圖G中某兩個結(jié)點之間的邊數(shù)多于一條又允許頂點通過同一條邊和自己關(guān)聯(lián)，則G為多重圖

頂點的度、入度、出度：

• 對于無向圖：

  • 頂點v的度是指依附于該頂點的邊的條數(shù)，記為TD(v)。

  • 在具有n個頂點、e條邊的無向圖中，無向圖的全部頂點的度的和等于邊數(shù)的2倍

• 對于有向圖：

  • 入度是以頂點v為終點的有向邊的數(shù)目，記為ID(v)；

  • 出度是以頂點v為起點的有向邊的數(shù)目，記為OD(v)。

  • 頂點v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)。

頂點-頂點的關(guān)系描述：

• 路徑：頂點vp到頂點vq之間的一條路徑是指頂點序列，

• 回路：第一個頂點和最后一個頂點相同的路徑稱為回路或環(huán)

• 簡單路徑：在路徑序列中，頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑。

• 簡單回路：除第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路稱為簡單回路。

• 路徑長度：路徑上邊的數(shù)目

• 點到點的距離：從頂點u出發(fā)到頂點v的最短路徑若存在，則此路徑的長度稱為從u到v的距離。若從u到v根本不存在路徑，則記該距離為無窮（∞）。

• 無向圖中，若從頂點v到頂點w有路徑存在，則稱v和w是連通的

• 有向圖中，若從頂點v到頂點w和從頂點w到頂點v之間都有路徑，則稱這兩個頂點是強連通的

連通圖、強連通圖：

• 若圖G中任意兩個頂點都是連通的，則稱圖G為連通圖，否則稱為非連通圖。

• 對于n個頂點的無向圖G，

  • 若G是連通圖，則最少有n-1條邊

  • 若G是非連通圖，則最多可能有

    

    條邊

• 若圖中任何一對頂點都是強連通的，則稱此圖為強連通圖。

• 對于n個頂點的有向圖G，

• 若G是強連通圖，則最少有n條邊（形成回路）

研究圖的局部——子圖：

• 設(shè)有兩個圖G = (V, E)和G￠ = (V', E')，若V￠是V的子集，且E'是E的子集，則稱G'是G的子圖

• 若有滿足V(G') = V(G)的子圖G'，則稱其為G的生成子圖

• 注意：并非任意挑幾個點、幾條邊都能構(gòu)成子圖

連通分量：

• 無向圖中的極大聯(lián)通子圖稱為連通分量

• 子圖必須連通，且包含盡可能多的頂點和邊

強連通分量：

• 有向圖中的極大強聯(lián)通子圖成為有向圖的強連通分量

• 子圖必須強連通，同時保留盡可能多的邊

生成樹：

• 連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖

• 邊盡可能的少，但要保持連通

• 若圖中頂點數(shù)為n，則它的生成樹含有n-1條邊。對生成樹而言，若砍去它的一條邊，則會變成非連通圖，若加上一條邊則會形成一個回路。

生成森林：

在非連通圖中，連通分量的生成樹構(gòu)成了非連通圖的生成森林。

邊的權(quán)、帶權(quán)圖/網(wǎng)：

• 邊的權(quán)：在一個圖中，每條邊都可以標(biāo)上具有某種含義的數(shù)值，該數(shù)值稱為該邊的權(quán)值。

• 帶權(quán)圖/網(wǎng)——邊上帶有權(quán)值的圖稱為帶權(quán)圖，也稱網(wǎng)。

• 帶權(quán)路徑長度——當(dāng)圖是帶權(quán)圖時，一條路徑上所有邊的權(quán)值之和，稱為該路徑的帶權(quán)路徑長度

幾種特殊形態(tài)的圖：

• 無向完全圖：無向圖中任意兩個頂點之間都存在邊

• 有向完全圖：有向圖中任意兩個頂點之間都存在方向相反的兩條弧

• 邊數(shù)很少的圖稱為稀疏圖

• 反之稱為稠密圖

• 沒有絕對的界限，一般來說|E| < |V|log|V|時，可以將G視為稀疏圖

• 樹：不存在回路，且連通的無向圖

• 有向樹：一個頂點的入度為0、其余頂點的入度均為1的有向圖，稱為有向樹

  • n個頂點的樹，必有n-1條邊。

  • n個頂點的圖，若|E|>n-1，則一定有回路

鄰接矩陣法

定義：

• 無向圖：

  • 第i個結(jié)點的度=第i行（或第i列）的非零元素個數(shù)

• 有向圖：

  • 第i個結(jié)點的出度=第i行的非零元素個數(shù)

  • 第i個結(jié)點的入度=第i列的非零元素個數(shù)

  • 第i個結(jié)點的度=第i行、第i列的非零元素個數(shù)之和

• 鄰接矩陣法求頂點的度/出度/入度的時間復(fù)雜度為O(|V|)

鄰接矩陣法存儲帶權(quán)圖（網(wǎng)）：

鄰接矩陣法的性能分析：

• 空間復(fù)雜度：O(|V|^2) ——只和頂點數(shù)相關(guān)，和實際的邊數(shù)無關(guān)

• 適合用于存儲稠密圖

• 無向圖的鄰接矩陣是對稱矩陣，可以壓縮存儲（只存儲上三角區(qū)/下三角區(qū)）

鄰接矩陣法的性質(zhì)：

鄰接表法

為什么要使用鄰接表：

• 鄰接矩陣是使用數(shù)組實現(xiàn)的順序存儲，空間復(fù)雜度高，不適合存儲稀疏圖

• 鄰接表是順序+鏈?zhǔn)酱鎯?/p>

定義：

• 其實這和樹的孩子表示法是類似的，孩子表示法：順序存儲各個結(jié)點，每個結(jié)點中保存孩子鏈表頭指針

• 邊結(jié)點的數(shù)量是2|E|，整體空間復(fù)雜度為O(|V| + 2|E|)

• 邊結(jié)點的數(shù)量是|E|，整體空間復(fù)雜度為O(|V| + |E|)

• 只要確定了頂點編號，圖的鄰接矩陣表示方式唯一，圖的鄰接表表示方式并不唯一

鄰接矩陣和鄰接表的對比：

十字鏈表、鄰接多重表

關(guān)系：

• 十字鏈表儲存有向圖

• 鄰接多重表儲存無向圖

十字鏈表存儲有向圖：

• 空間復(fù)雜度：O(|V|+|E|)

• 如何找到指定頂點的所有出邊？順著綠色線路找

• 如何找到指定頂點的所有入邊？順著橙色線路找

鄰接矩陣、鄰接表存儲無向圖：

• 鄰接表每條邊對應(yīng)兩份冗余信息，刪除頂點、刪除邊等操作時間復(fù)雜度高

• 臨接矩陣空間復(fù)雜度高O(|V|2)

臨接多重表儲存無向圖：

• 空間復(fù)雜度：O(|V|+|E|)

• 刪除邊、刪除結(jié)點等操作很方便，只需要讓各指針指向下一個對應(yīng)的指向即可

總結(jié)：

圖的基本操作

• Adjacent(G,x,y)：判斷圖G是否存在邊<x, y>或(x, y)。

• Neighbors(G,x)：列出圖G中與結(jié)點x鄰接的邊。

• InsertVertex(G,x)：在圖G中插入頂點x。

• DeleteVertex(G,x)：從圖G中刪除頂點x。

• AddEdge(G,x,y)：若無向邊(x, y)或有向邊<x, y>不存在，則向圖G中添加該邊。

• RemoveEdge(G,x,y)：若無向邊(x, y)或有向邊<x, y>存在，則從圖G中刪除該邊。

• FirstNeighbor(G,x)：求圖G中頂點x的第一個鄰接點，若有則返回頂點號。若x沒有鄰接點或圖中不存在x，則返回-1。

• NextNeighbor(G,x,y)：假設(shè)圖G中頂點y是頂點x的一個鄰接點，返回除y之外頂點x的下一個鄰接點的頂點號，若y是x的最后一個鄰接點，則返回-1。

• Get_edge_value(G,x,y)：獲取圖G中邊(x, y)或<x, y>對應(yīng)的權(quán)值。

• Set_edge_value(G,x,y,v)：設(shè)置圖G中邊(x, y)或<x, y>對應(yīng)的權(quán)值為v。

• 注意：上面的操作都只針對鄰接矩陣和鄰接表

圖的廣度優(yōu)先遍歷（BFS）

樹和圖的廣度優(yōu)先遍歷：

• 樹的廣度優(yōu)先遍歷：通過根結(jié)點，可以找到下一層的結(jié)點2，3，4.通過234又可以找到再下一層的結(jié)點5678

  • 若樹非空，則根結(jié)點入隊

  • 若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩字依次入隊

  • 重復(fù)第二步直到隊列為空

• 圖的廣度優(yōu)先遍歷類似于樹的廣度優(yōu)先遍歷（層序遍歷）

• 區(qū)別：

  • 樹不存在“回路”，搜索相鄰的結(jié)點時，不可能搜到已經(jīng)訪問過的結(jié)點

  • 圖搜索相鄰的頂點時，有可能搜到已經(jīng)訪問過的頂點

代碼實現(xiàn)：

• 找到與一個頂點相鄰的所有頂點

  • FirstNeighbor(G,x)：求圖G中頂點x的第一個鄰接點，若有則返回頂點號。若x沒有鄰接點或圖中不存在x，則返回-1。

  • NextNeighbor(G,x,y)：假設(shè)圖G中頂點y是頂點x的一個鄰接點，返回除y之外頂點x的下一個鄰接點的頂點號，若y是x的最后一個鄰接點，則返回-1。

  • 使用上面兩個基本操作

• 標(biāo)記哪些頂點被訪問過

  • 

  • 都初始化為false

• 需要一個輔助隊列

遍歷序列的可變性：

• 同一個圖的鄰接矩陣表示方式唯一，因此廣度優(yōu)先遍歷序列唯一

• 同一個圖鄰接表表示方式不唯一，因此廣度優(yōu)先遍歷序列不唯一

算法存在的問題和解決方案：

如果是非連通圖，則無法遍歷完所有結(jié)點

• 空間復(fù)雜度：最壞情況，輔助隊列大小為 O(|V|)

• 鄰接矩陣存儲的圖：

  • 訪問 |V| 個頂點需要O(|V|)的時間

  • 查找每個頂點的鄰接點都需要O(|V|)的時間，而總共有|V|個頂點

  • 時間復(fù)雜度= O(|V|^2)

• 鄰接表存儲的圖：

  • 訪問 |V| 個頂點需要O(|V|)的時間

  • 查找各個頂點的鄰接點共需要O(|E|)的時間

  • 時間復(fù)雜度= O(|V|+|E|)

廣度優(yōu)先生成樹：

• 廣度優(yōu)先生成樹由廣度優(yōu)先遍歷過程確定。

• 由于鄰接表的表示方式不唯一，因此基于鄰接表的廣度優(yōu)先生成樹也不唯一

• 對非連通圖的廣度優(yōu)先遍歷，可得到廣度優(yōu)先生成森林

圖的深度優(yōu)先遍歷（DFS）

樹和圖的深度優(yōu)先遍歷：

• 樹的深度優(yōu)先遍歷（先根、后根）：

  • 從根結(jié)點出發(fā)，能往更深處走就盡量往深處走。

  • 每當(dāng)訪問一個結(jié)點的時候，要檢查是否還有與當(dāng)前結(jié)點相鄰的且沒有被訪問過的結(jié)點，如果有的話就往下一層鉆。

• 圖的深度優(yōu)先遍歷類似于樹的先根遍歷。

• 圖的深度優(yōu)先遍歷是遞歸實現(xiàn)的，廣度優(yōu)先辦理是隊列實現(xiàn)的

圖的深度優(yōu)先遍歷：

算法存在的問題和解決方案：

如果是非連通圖，則無法遍歷完所有結(jié)點

復(fù)雜度分析：

• 空間復(fù)雜度：

  • 來自函數(shù)調(diào)用棧，最壞情況，遞歸深度為O(|V|)

  • 最好情況，O(1)

• 時間復(fù)雜度：

  • 時間復(fù)雜度=訪問各結(jié)點所需時間+探索各條邊所需時間

  • 鄰接矩陣存儲的圖：

    • 訪問 |V| 個頂點需要O(|V|)的時間

    • 查找每個頂點的鄰接點都需要O(|V|)的時間，而總共有|V|個頂點

    • 時間復(fù)雜度= O(|V|^2)

  • 鄰接表存儲的圖：

    • 訪問 |V| 個頂點需要O(|V|)的時間

    • 查找各個頂點的鄰接點共需要O(|E|)的時間

    • 時間復(fù)雜度= O(|V|+|E|)

深度優(yōu)先序列：

• 和圖的鄰接表是一個原理，樹中各個孩子結(jié)點在鄰接表中出現(xiàn)的順序是可變的

• 因此如果采用這種數(shù)據(jù)結(jié)構(gòu)存儲樹，那么可能會有不同的遍歷序列

深度優(yōu)先生成樹：

• 同一個圖的鄰接矩陣表示方式唯一，因此深度優(yōu)先遍歷序列唯一，深度優(yōu)先生成樹也唯一

• 同一個圖鄰接表表示方式不唯一，因此深度優(yōu)先遍歷序列不唯一，深度優(yōu)先生成樹也不唯一

• 對無向圖進(jìn)行BFS/DFS遍歷

圖的遍歷與圖的連通性：

• 調(diào)用BFS/DFS函數(shù)的次數(shù)=連通分量數(shù)

• 對于連通圖，只需調(diào)用1次 BFS/DFS

• 對有向圖進(jìn)行BFS/DFS遍歷

• 調(diào)用BFS/DFS函數(shù)的次數(shù)要具體問題具體分析，若起始頂點到其他各頂點都有路徑，則只需調(diào)用1次BFS/DFS 函數(shù)

• 對于強連通圖，從任一結(jié)點出發(fā)都只需調(diào)用1次 BFS/DFS

最小生成樹

生成樹：

• 連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖。

• 若圖中頂點數(shù)為n，則它的生成樹含有n-1條邊。對生成樹而言，若砍去它的一條邊，則會變成非連通圖，若加上一條邊則會形成一個回路

最小生成樹（最小代價樹）：

• 對于一個帶權(quán)連通無向圖G = (V, E)，生成樹不同，每棵樹的權(quán)（即樹中所有邊上的權(quán)值之和）也可能不同

• 設(shè)R為G的所有生成樹的集合，若T為R中邊的權(quán)值之和最小的生成樹，則T稱為G的最小生成樹（Minimum-Spanning-Tree, MST）

• 最小生成樹可能有多個，但邊的權(quán)值之和總是唯一且最小的

• 最小生成樹的邊數(shù) = 頂點數(shù) - 1

• 砍掉一條則不連通，增加一條邊則會出現(xiàn)回路

• 如果一個連通圖本身就是一棵樹，則其最小生成樹就是它本身

• 只有連通圖才有生成樹，非連通圖只有生成森林

Prim 算法（普里姆）：

算法思想：

• 從某一個頂點開始構(gòu)建生成樹；

• 每次將代價最小的新頂點納入生成樹，直到所有頂點都納入為止。

• 時間復(fù)雜度：O(|V|^2)，適合用于邊稠密圖

數(shù)據(jù)結(jié)構(gòu)：

實現(xiàn)步驟：

• 從V0開始，總共需要 n-1 輪處理

• 循環(huán)遍歷所有個結(jié)點，找到lowCost最低的，且還沒加入樹的頂點，isJoin對應(yīng)結(jié)點標(biāo)記為true

• 再次循環(huán)遍歷，更新還沒加入的各個頂點的lowCost值

• 重復(fù)上面步驟，直到所有結(jié)點都加入樹，生成的樹即為最小生成樹

Kruskal 算法（克魯斯卡爾）

算法思想：

• 每次選擇一條權(quán)值最小的邊，使這條邊的兩頭連通（原本已經(jīng)連通的就不選）

• 直到所有結(jié)點都連通

• 時間復(fù)雜度：O( |E|log2|E| )，適合用于邊稀疏圖

數(shù)據(jù)結(jié)構(gòu)：

讓各條邊按照權(quán)值順序排序

實現(xiàn)步驟：

• 共執(zhí)行 e 輪，每輪判斷兩個頂點是否屬于同一集合

• 檢查第e條邊的兩個頂點是否連通（是否屬于同一個集合）

• 若不聯(lián)通則連起來

• 若聯(lián)通則不操作

• 重復(fù)上面的步驟直到所有邊都被遍歷過

最短路徑問題之BFS算法

介紹：

• 無權(quán)圖可以視為一種特殊的帶權(quán)圖，只是每條邊的權(quán)值都為1

• BFS一般只適用于無權(quán)圖的最短路徑問題

代碼實現(xiàn)：

• d數(shù)組表示u到各個結(jié)點的最短路徑

• path數(shù)組表示該結(jié)點回到u結(jié)點的最短前驅(qū)結(jié)點

• 由此生成的生成樹同時也反應(yīng)了起點到任意結(jié)點的距離

最短路徑問題之Dijkstra算法

BFS算法的局限性：

• 帶權(quán)路徑長度——當(dāng)圖是帶權(quán)圖時，一條路徑上所有邊的權(quán)值之和，稱為該路徑的帶權(quán)路徑長度

• BFS算法求單源最短路徑只適用于無權(quán)圖，或所有邊的權(quán)值都相同的圖

算法思想：

• 初始：從V0開始，初始化三個數(shù)組信息

• 循環(huán)遍歷所有結(jié)點，找到還沒確定最短路徑，且dist 最小的頂點Vi，令final[i]=ture。

• 檢查所有鄰接自 Vi 的頂點，若其 final 值為false，則更新 dist 和 path 信息

• 重復(fù)上述步驟，知道所有結(jié)點的final都標(biāo)記為true

代碼實現(xiàn)思路：

• 初始：

  • 若從V0開始，令 final[0]=ture; dist[0]=0; path[0]=-1。

• n-1輪處理

  • 循環(huán)遍歷所有頂點，找到還沒確定最短路徑，且dist 最小的頂點Vi，令final[i]=ture。

  • 并檢查所有鄰接自Vi 的頂點，對于鄰接自Vi 的頂點 Vj ，若 final[j]==false 且 dist[i]+arcsi < dist[j]，則令 dist[j]=dist[i]+arcsi; path[j]=i。

  • 注：arcsi表示Vi 到Vj 的弧的權(quán)值

• 時間復(fù)雜度：O(n2)即O(|V|2)

用于負(fù)權(quán)值帶權(quán)圖：

Dijkstra 算法不適用于有負(fù)權(quán)值的帶權(quán)圖

最短路徑問題之Floyd算法

算法思想：

• Floyd算法：求出每一對頂點之間的最短路徑

• 使用動態(tài)規(guī)劃思想，將問題的求解分為多個階段

• 對于n個頂點的圖G，求任意一對頂點 Vi —> Vj 之間的最短路徑可分為如下幾個階段：

  • 初始：不允許在其他頂點中轉(zhuǎn)，最短路徑是？

  • 0：若允許在 V0 中轉(zhuǎn)，最短路徑是？

  • 1：若允許在 V0、V1 中轉(zhuǎn)，最短路徑是？

  • 2：若允許在 V0、V1、V2 中轉(zhuǎn)，最短路徑是？

  • …

  • n-1：若允許在 V0、V1、V2 …… Vn-1 中轉(zhuǎn)，最短路徑是？

實現(xiàn)步驟：

代碼實現(xiàn)：

注意點：

• Floyd算法可以用于負(fù)權(quán)圖

• Floyd 算法不能解決帶有“負(fù)權(quán)回路”的圖（有負(fù)權(quán)值的邊組成回路），這種圖有可能沒有最短路徑（每走一圈路徑越小）

總結(jié)：

有向無環(huán)圖（DAG圖）的描述表達(dá)式

定義：

若一個有向圖中不存在環(huán)，則稱為有向無環(huán)圖，簡稱DAG圖（Directed Acyclic Graph）

例子：

轉(zhuǎn)換前：

轉(zhuǎn)換后：

解題方法：

• 把各個操作數(shù)不重復(fù)地排成一排

• 標(biāo)出各個運算符的生效順序（先后順序有點出入無所謂）

• 按順序加入運算符，注意“分層”

• 從底向上逐層檢查同層的運算符是否可以合體

拓?fù)渑判?/h4>

AOV網(wǎng)：

• AOV網(wǎng)(Activity On Vertex NetWork，用頂點表示活動的網(wǎng))

• 用DAG圖（有向無環(huán)圖）表示一個工程。頂點表示活動，有向邊<Vi, Vj>表示活動Vi必須先于活動Vj進(jìn)行

拓?fù)渑判颍?/strong>

• 拓?fù)渑判颍涸趫D論中，由一個有向無環(huán)圖的頂點組成的序列，當(dāng)且僅當(dāng)滿足下列條件時，稱為該圖的一個拓?fù)渑判颍?/p>

  • 每個頂點出現(xiàn)且只出現(xiàn)一次。

  • 若頂點A在序列中排在頂點B的前面，則在圖中不存在從頂點B到頂點A的路徑。

• 或定義為：

  • 拓?fù)渑判蚴菍τ邢驘o環(huán)圖的頂點的一種排序，它使得若存在一條從頂點A到頂點B的路徑，則在排序中頂點B出現(xiàn)在頂點A的后面。

• 每個AOV網(wǎng)都有一個或多個拓?fù)渑判蛐蛄小?/p>

• 簡單來說拓?fù)渑判蚓褪钦业阶鍪碌南群箜樞?/p>

• 拓?fù)渑判虻膶崿F(xiàn)：

  • 從AOV網(wǎng)中選擇一個沒有前驅(qū)（入度為0）的頂點并輸出。

  • 從網(wǎng)中刪除該頂點和所有以它為起點的有向邊。

  • 重復(fù)前面的步驟直到當(dāng)前的AOV網(wǎng)為空或當(dāng)前網(wǎng)中不存在無前驅(qū)的頂點為止。

代碼實現(xiàn)：

• 時間復(fù)雜度：O(|V|+|E|)

• 若采用鄰接矩陣，則需O(|V|^2)

逆拓?fù)渑判颍?/strong>

• 對一個AOV網(wǎng)，如果采用下列步驟進(jìn)行排序，則稱之為逆拓?fù)渑判颍?/p>

  • 從AOV網(wǎng)中選擇一個沒有后繼（出度為0）的頂點并輸出。

  • 從網(wǎng)中刪除該頂點和所有以它為終點的有向邊。

  • 重復(fù)上面步驟直到當(dāng)前的AOV網(wǎng)為空。

• 用鄰接表實現(xiàn)會更簡單一些

• 使用逆鄰接表：鄰接表的頂點對應(yīng)儲存的信息是指向該頂點的邊的信息

• 使用深度優(yōu)先算法實現(xiàn)逆拓?fù)渑判?，頂點輸出的序列就是逆拓?fù)渑判蛐蛄?/p>

• DFS實現(xiàn)逆拓?fù)渑判颍涸陧旤c退棧前輸出

關(guān)鍵路徑

AOE網(wǎng)：

• 在帶權(quán)有向圖中，以頂點表示事件，以有向邊表示活動，以邊上的權(quán)值表示完成該活動的開銷（如完成活動所需的時間）

• 稱之為用邊表示活動的網(wǎng)絡(luò)，簡稱AOE網(wǎng) (Activity On Edge NetWork)

• AOE網(wǎng)具有以下兩個性質(zhì)：

  • 只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始；

  • 只有在進(jìn)入某頂點的各有向邊所代表的活動都已結(jié)束時，該頂點所代表的事件才能發(fā)生。

  • 另外，有些活動是可以并行進(jìn)行的

關(guān)鍵路徑：

• 從源點到匯點的有向路徑可能有多條，所有路徑中，具有最大路徑長度的路徑稱為關(guān)鍵路徑，而把關(guān)鍵路徑上的活動稱為關(guān)鍵活動

• 完成整個工程的最短時間就是關(guān)鍵路徑的長度，若關(guān)鍵活動不能按時完成，則整個工程的完成時間就會延長

• 事件vk的最早發(fā)生時間ve(k)：決定了所有從vk開始的活動能夠開工的最早時間

• 活動ai的最早開始時間e(i)：指該活動弧的起點所表示的事件的最早發(fā)生時間

• 事件vk的最遲發(fā)生時間vl(k)：它是指在不推遲整個工程完成的前提下，該事件最遲必須發(fā)生的時間。

• 活動ai的最遲開始時間l(i)：它是指該活動弧的終點所表示事件的最遲發(fā)生時間與該活動所需時間之差。

• 活動ai的時間余量d(i)=l(i)-e(i)，表示在不增加完成整個工程所需總時間的情況下，活動ai可以拖延的時間

• 若一個活動的時間余量為零，則說明該活動必須要如期完成，d(i)=0即l(i) = e(i)的活動ai是關(guān)鍵活動，

• 由關(guān)鍵活動組成的路徑就是關(guān)鍵路徑

求關(guān)鍵路徑的步驟：

• 求所有事件的最早發(fā)生時間 ve( )

  • 按拓?fù)渑判蛐蛄?，依次求各個頂點的 ve(k):

  • ve(源點) = 0

  • ve(k) = Max{ve(j) + Weight(vj, vk)}, vj為vk 的任意前驅(qū)

• 求所有事件的最遲發(fā)生時間 vl( )

  • 按逆拓?fù)渑判蛐蛄校来吻蟾鱾€頂點的 vl(k):

  • vl(匯點) = ve(匯點)

  • vl(k) = Min{vl(j) - Weight(vk, vj)} , vj為vk的任意后繼

• 求所有活動的最早發(fā)生時間 e( )

  • 若邊<vk, vj>表示活動ai，則有e(i) = ve(k)

• 求所有活動的最遲發(fā)生時間 l( )

  • 若邊<vk, vj>表示活動ai，則有l(wèi)(i) = vl(j) - Weight(vk, vj)

• 求所有活動的時間余量 d( )

  • d(i) = l(i) - e(i)

• d(i)=0的活動就是關(guān)鍵活動, 由關(guān)鍵活動可得關(guān)鍵路徑

關(guān)鍵活動、關(guān)鍵路徑的特性：

• 若關(guān)鍵活動耗時增加，則整個工程的工期將增長

• 縮短關(guān)鍵活動的時間，可以縮短整個工程的工期

• 當(dāng)縮短到一定程度時，關(guān)鍵活動可能會變成非關(guān)鍵活動

• 可能有多條關(guān)鍵路徑，只提高一條關(guān)鍵路徑上的關(guān)鍵活動速度并不能縮短整個工程的工期，只有加快那些包括在所有關(guān)鍵路徑上的關(guān)鍵活動才能達(dá)到縮短工期的目的。

查找

查找的基本概念

• 查找： 在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)元素的過程稱為查找

• 查找表（查找結(jié)構(gòu)）：用于查找的數(shù)據(jù)集合稱為查找表，它由同一類型的數(shù)據(jù)元素（或記錄）組成

• 關(guān)鍵字： 數(shù)據(jù)元素中唯一標(biāo)識該元素的某個數(shù)據(jù)項的值，使用基于關(guān)鍵字的查找，查找結(jié)果應(yīng)該是唯一的。

對查找表的常見操作：

• 查找符合條件的數(shù)據(jù)元素

  • 靜態(tài)查找表

  • 僅關(guān)注查找速度即可

• 插入、刪除某個數(shù)據(jù)元素

  • 動態(tài)查找表

  • 除了查找速度，也要關(guān)注插/刪操作是否方便實現(xiàn)

查找算法的評價指標(biāo)：

• 查找長度：在查找運算中，需要對比關(guān)鍵字的次數(shù)稱為查找長度

• 平均查找長度（ASL, Average Search Length ）：所有查找過程中進(jìn)行關(guān)鍵字的比較次數(shù)的平均值

• ASL的數(shù)量級反應(yīng)了查找算法的時間復(fù)雜度

• 評價一個查找算法的效率時，通?？紤]查找成功、查找失敗兩種情況的ASL

順序查找

定義：

順序查找，又叫“線性查找”，通常用于線性表。

算法思想：從頭到尾依次往后找

順序查找的實現(xiàn)：

順序查找的實現(xiàn)（哨兵）：

優(yōu)點：無需判斷是否越界，效率更高

順序查找的優(yōu)化（對有序表）：

用查找判定樹分析ASL：

• 一個成功結(jié)點的查找長度 = 自身所在層數(shù)

• 一個失敗結(jié)點的查找長度 = 其父結(jié)點所在層數(shù)

• 默認(rèn)情況下，各種失敗情況或成功情況都等概率發(fā)生

順序查找的優(yōu)化（被查概率不相等）：

折半查找

算法思想：

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

查找成功：

注意：下面的mid向下取整

查找失?。?/p>

代碼實現(xiàn)：

查找效率分析：

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

• 如果當(dāng)前l(fā)ow和high之間有偶數(shù)個元素，則 mid 分隔后，左半部分比右半部分少一個元素

• 如果當(dāng)前l(fā)ow和high之間有奇數(shù)個元素，則 mid 分隔后，左右兩部分元素個數(shù)相等

• 折半查找的判定樹中,mid = [(low + high)/2]則對于任何一個結(jié)點，必有：右樹結(jié)點數(shù)-左子樹結(jié)點數(shù)=0或1

• 折半查找的判定樹一定是平衡二叉樹

• 折半查找的判定樹中，只有最下面一層是不滿的因此，元素個數(shù)為n時樹高h(yuǎn) = [log2(n + 1)]

• 判定樹結(jié)點關(guān)鍵字：左<中<右，滿足二叉排序樹的定義

• 失敗結(jié)點：n+1個（等于成功結(jié)點的空鏈域數(shù)量）

• 折半查找的時間復(fù)雜度 = O(log2n)

分塊查找

算法思想：

• 特點：塊內(nèi)無序、塊間有序

• 分塊查找，又稱索引順序查找，算法過程如下：

  • 在索引表中確定待查記錄所屬的分塊（可順序、可折半）

  • 在塊內(nèi)順序查找

用折半查找查索引：

若查找目標(biāo)與索引表值相同：

若查找目標(biāo)與索引值不同：

• 若索引表中不包含目標(biāo)關(guān)鍵字，則折半查找索引表最終停在 low>high，要在low所指分塊中查找

• 原因：最終low左邊一定小于目標(biāo)關(guān)鍵字，high右邊一定大于目標(biāo)關(guān)鍵字。而分塊存儲的索引表中保存的是各個分塊的最大關(guān)鍵字

查找失敗的例子：

查找效率分析：

B樹

m叉查找樹：

• 實際上就是二叉查找樹的拓展，結(jié)點多少有多少個分叉就是多少叉查找樹

• 每個結(jié)點關(guān)鍵字的查找可以用順序查找也可以用折半查找

如何保證查找效率：

• 若每個結(jié)點內(nèi)關(guān)鍵字太少，導(dǎo)致樹變高，要查更多層結(jié)點，效率低

  • 策略：m叉查找樹中，規(guī)定除了根結(jié)點外，任何結(jié)點至少有?m/2?個分叉，即至少含有?m/2? ? 1 個關(guān)鍵字

  • 為什么不能保證根結(jié)點至少有?m/2?個分叉：如果整個樹只有1個元素，根結(jié)點只能有兩個分叉

• 不夠“平衡”，樹會很高，要查很多層結(jié)點

  • 策略：m叉查找樹中，規(guī)定對于任何一個結(jié)點，其所有子樹的高度都要相同。

B樹的定義：

• B樹，又稱多路平衡查找樹，B樹中所有結(jié)點的孩子個數(shù)的最大值稱為B樹的階，通常用m表示。一棵m階B樹或為空樹，或為滿足如下特性的m叉樹：

  • 樹中每個結(jié)點至多有m棵子樹，即至多含有m-1個關(guān)鍵字。

  • 若根結(jié)點不是終端結(jié)點，則至少有兩棵子樹。

  • 除根結(jié)點外的所有非葉結(jié)點至少有?m/2?棵子樹，即至少含有 ?m/2?-1個關(guān)鍵字。

  • 所有非葉結(jié)點的結(jié)構(gòu)如下：

    • 

    • 其中，Ki（i = 1, 2,…, n）為結(jié)點的關(guān)鍵字，且滿足K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）為指向子樹根結(jié)點的指針，且指針Pi-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki，Pi所指子樹中所有結(jié)點的關(guān)鍵字均大于Ki，n（?m/2?- 1≤n≤m - 1）為結(jié)點中關(guān)鍵字的個數(shù)。

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

B樹的高度：

最大高度的另一種推導(dǎo)方法：

B樹的插入刪除

B樹的插入：

• 新元素一定是插入到最底層“終端結(jié)點”，用“查找”來確定插入位置

• 在插入key后，若導(dǎo)致原結(jié)點關(guān)鍵字?jǐn)?shù)超過上限，則從中間位置（?m/2?）將其中的關(guān)鍵字分為兩部分

• 左部分包含的關(guān)鍵字放在原結(jié)點中，右部分包含的關(guān)鍵字放到新結(jié)點中，中間位置（?m/2?）的結(jié)點插入原結(jié)點的父結(jié)點

• 若此時導(dǎo)致其父結(jié)點的關(guān)鍵字個數(shù)也超過了上限，則繼續(xù)進(jìn)行這種分裂操作，直至這個過程傳到根結(jié)點為止，進(jìn)而導(dǎo)致B樹高度增1。

B樹的刪除：

• 若被刪除關(guān)鍵字在終端結(jié)點，則直接刪除該關(guān)鍵字（要注意結(jié)點關(guān)鍵字個數(shù)是否低于下限 ?m/2? ? 1）

• 若被刪除關(guān)鍵字在非終端結(jié)點，則用直接前驅(qū)或直接后繼來替代被刪除的關(guān)鍵字

  • 直接前驅(qū)：當(dāng)前關(guān)鍵字左側(cè)指針?biāo)缸訕渲小白钣蚁隆钡脑?/p>

  • 直接后繼：當(dāng)前關(guān)鍵字右側(cè)指針?biāo)缸訕渲小白钭笙隆钡脑?/p>

• 若被刪除關(guān)鍵字所在結(jié)點刪除前的關(guān)鍵字個數(shù)低于下限，且與此結(jié)點右（或左）兄弟結(jié)點的關(guān)鍵字個數(shù)還很寬裕，則需要調(diào)整該結(jié)點、右（或左）兄弟結(jié)點及其雙親結(jié)點（父子換位法）

  • 當(dāng)右兄弟很寬裕時，用當(dāng)前結(jié)點的后繼（比當(dāng)前結(jié)點大一位）、后繼的后繼（比當(dāng)前結(jié)點大兩位）來填補空缺

  • 當(dāng)左兄弟很寬裕時，用當(dāng)前結(jié)點的前驅(qū)（比當(dāng)前結(jié)點小一位）、前驅(qū)的前驅(qū)（比當(dāng)前結(jié)點小兩位）來填補空缺

• 若被刪除關(guān)鍵字所在結(jié)點刪除前的關(guān)鍵字個數(shù)低于下限，且此時與該結(jié)點相鄰的左、右兄弟結(jié)點的關(guān)鍵字個數(shù)均=?m/2? ? 1，則將關(guān)鍵字刪除后與左（或右）兄弟結(jié)點及雙親結(jié)點中的關(guān)鍵字進(jìn)行合并

B+樹

定義和性質(zhì)：

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

• 每個分支結(jié)點最多有m棵子樹（孩子結(jié)點）。

• 非葉根結(jié)點至少有兩棵子樹，其他每個分支結(jié)點至少有?m/2?棵子樹。

  • 可以理解為：要追求“絕對平衡”，即所有子樹高度要相同

• 結(jié)點的子樹個數(shù)與關(guān)鍵字個數(shù)相等。

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

• 所有分支結(jié)點中僅包含它的各個子結(jié)點中關(guān)鍵字的最大值及指向其子結(jié)點的指針。

B+樹的查找：

B+樹中，無論查找成功與否，最終一定都要走到最下面一層結(jié)點，因為只有葉子結(jié)點才有關(guān)鍵字對應(yīng)的記錄

B+樹和B樹區(qū)別：

• 典型應(yīng)用：關(guān)系型數(shù)據(jù)庫的“索引”（如MySQL）

• 在B+樹中，非葉結(jié)點不含有該關(guān)鍵字對應(yīng)記錄的存儲地址。

• 可以使一個磁盤塊可以包含更多個關(guān)鍵字，使得B+樹的階更大，樹高更矮，讀磁盤次數(shù)更少，查找更快

散列（哈希）查找

定義：

• 散列表（Hash Table），又稱哈希表

• 是一種數(shù)據(jù)結(jié)構(gòu)，特點是：數(shù)據(jù)元素的關(guān)鍵字與其存儲地址直接相關(guān)

• 通過哈希函數(shù)建立關(guān)鍵字和存儲地址的聯(lián)系

• 若不同的關(guān)鍵字通過散列函數(shù)映射到同一個值，則稱它們?yōu)椤巴x詞”

• 通過散列函數(shù)確定的位置已經(jīng)存放了其他元素，則稱這種情況為“沖突”

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

• 用拉鏈法（又稱鏈接法、鏈地址法）處理“沖突”：把所有“同義詞”存儲在一個鏈表中

• 最理想情況：散列查找時間復(fù)雜度可到達(dá)O(1)

• “沖突”越多，查找效率越低

• 實際上就是順序表和鏈表的結(jié)合結(jié)合兩者優(yōu)點，比如順序表的隨機存取，然后用鏈表的解決沖突問題，又規(guī)避了順序表的一系列缺點

• 在插入新元素時，保持關(guān)鍵字有序，可微微提高查找效率

常見的散列函數(shù)：

• 散列函數(shù)的設(shè)計目的：

  • 讓不同關(guān)鍵字的沖突盡可能的少

  • 散列查找是典型的“用空間換時間”的算法，只要散列函數(shù)設(shè)計的合理，則散列表越長，沖突的概率越低。

• 除留余數(shù)法：H(key) = key % p

  • 散列表表長為m，取一個不大于m但最接近或等于m的質(zhì)數(shù)p

  • 質(zhì)數(shù)又稱素數(shù)。指除了1和此整數(shù)自身外,不能被其他自然數(shù)整除的數(shù)

  • 用質(zhì)數(shù)取模，分布更均勻，沖突更少。參見《數(shù)論》

  • 注意：散列函數(shù)的設(shè)計要結(jié)合實際的關(guān)鍵字分布特點來考慮，不要教條化

• 直接定址法 ： H(key) = key 或 H(key) = a*key + b

  • 其中，a和b是常數(shù)。這種方法計算最簡單，且不會產(chǎn)生沖突。它適合關(guān)鍵字的分布基本連續(xù)的情況，若關(guān)鍵字分布不連續(xù)，空位較多，則會造成存儲空間的浪費。

  • 例如：存儲同一個班級的學(xué)生信息

• 數(shù)字分析法：選取數(shù)碼分布較為均勻的若干位作為散列地址

  • 設(shè)關(guān)鍵字是r進(jìn)制數(shù)（如十進(jìn)制數(shù)），而r個數(shù)碼在各位上出現(xiàn)的頻率不一定相同，可能在某些位上分布均勻一些，每種數(shù)碼出現(xiàn)的機會均等；

  • 而在某些位上分布不均勻，只有某幾種數(shù)碼經(jīng)常出現(xiàn)，此時可選取數(shù)碼分布較為均勻的若干位作為散列地址。這種方法適合于已知的關(guān)鍵字集合，若更換了關(guān)鍵字，則需要重新構(gòu)造新的散列函數(shù)。

  • 例如：以“手機號碼”作為關(guān)鍵字設(shè)計散列函數(shù)

• 平方取中法：取關(guān)鍵字的平方值的中間幾位作為散列地址。

  • 具體取多少位要視實際情況而定。

  • 這種方法得到的散列地址與關(guān)鍵字的每位都有關(guān)系，因此使得散列地址分布比較均勻，適用于關(guān)鍵字的每位取值都不夠均勻或均小于散列地址所需的位數(shù)。

  • 例如：要存儲整個學(xué)校的學(xué)生信息，以“身份證號”作為關(guān)鍵字設(shè)計散列函數(shù)

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

• 所謂開放定址法，是指可存放新表項的空閑地址既向它的同義詞表項開放，又向它的非同義詞表項開放。其數(shù)學(xué)遞推公式為：

  • Hi = (H(key) + di) % m

  • i = 0, 1, 2,…, k（k≤m - 1），m表示散列表表長；di為增量序列；

  • i 可理解為“第i次發(fā)生沖突”

• 線性探測法

  • di = 0, 1, 2, 3, …, m-1；即發(fā)生沖突時，每次往后探測相鄰的下一個單元是否為空，為空則可以插入數(shù)值

  • 查找也是類似，先通過公式得到Hi再依次往后查找，若遇到空的位置則說明查找失敗，所以越早遇到空位置，就可以越早確定查找失敗

  • 刪除結(jié)點不能簡單地將被刪結(jié)點的空間置為空，否則將截斷在它之后填入散列表的同義詞結(jié)點的查找路徑，可以做一個“刪除標(biāo)記”，進(jìn)行邏輯刪除

  • 線性探測法由于沖突后再探測一定是放在某個連續(xù)的位置，很容易造成同義詞、非同義詞的“聚集（堆積）”現(xiàn)象，嚴(yán)重影響查找效率

• 平方探測法

  • 當(dāng)di = 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2時，稱為平方探測法，又稱二次探測法，其中k≤m/2

  • 比起線性探測法更不易產(chǎn)生“聚集（堆積）”問題

  • 注意：負(fù)數(shù)的模運算，(-3)%27 = 24，而不是3

  • 模運算的規(guī)則：a MOD m == (a+km) MOD m , 其中，k為任意整數(shù)

  • 散列表長度m必須是一個可以表示成4j + 3的素數(shù)，才能探測到所有位置

• 偽隨機序列法

  • di 是一個偽隨機序列，如 di= 0, 5, 24, 11, …

處理沖突的方法——再散列法：

• 除了原始的散列函數(shù) H(key) 之外，多準(zhǔn)備幾個散列函數(shù)

• 當(dāng)散列函數(shù)沖突時，用下一個散列函數(shù)計算一個新地址，直到不沖突為止：

• Hi = RHi(Key)

• i=1,2,3….,k

排序

排序的基本概念

定義：

• 排序（Sort），就是重新排列表中的元素，使表中的元素滿足按關(guān)鍵字有序的過程。

• 輸入：n個記錄R1, R2,…, Rn，對應(yīng)的關(guān)鍵字為k1, k2,…, kn。

• 輸出：輸入序列的一個重排R1?, R2?,…, Rn?，使得有k1?≤k2?≤…≤kn?（也可遞減）

排序算法的評價指標(biāo)：

• 時間復(fù)雜度

• 空間復(fù)雜度

• 算法的穩(wěn)定性：

  • 若待排序表中有兩個元素Ri和Rj，其對應(yīng)的關(guān)鍵字相同即keyi = keyj，且在排序前Ri在Rj的前面

  • 若使用某一排序算法排序后，Ri仍然在Rj的前面

  • 則稱這個排序算法是穩(wěn)定的，否則稱排序算法是不穩(wěn)定的。

排序算法的分類：

• 內(nèi)部排序：數(shù)據(jù)都在內(nèi)存中，關(guān)注如何使算法時、空復(fù)雜度更低

• 外部排序：數(shù)據(jù)太多，無法全部放入內(nèi)存，還要關(guān)注如何使讀/寫磁盤次數(shù)更少

插入排序

算法思想：

每次將一個待排序的記錄按其關(guān)鍵字大小插入到前面已排好序的子序列中，直到全部記錄插入完成。

代碼實現(xiàn)：

算法效率分析：

• 空間復(fù)雜度：O(1)

• 時間復(fù)雜度：主要來自對比關(guān)鍵字、移動元素，若有 n 個元素，則需要 n-1 趟處理

  • 最好時間復(fù)雜度：O(n) 共n-1趟處理，每一趟只需要對比關(guān)鍵字1次，不用移動元素

  • 最壞時間復(fù)雜度：O(n^2) 共n-1趟處理，每一趟都需要從尾移到到頭（全部逆序）

• 算法穩(wěn)定性：穩(wěn)定

優(yōu)化——折半插入排序：

思路：

• 先用折半查找找到應(yīng)該插入的位置，再移動元素

• 當(dāng) low>high 時折半查找停止，應(yīng)將 [low, i-1] 內(nèi)的元素全部右移，并將 A[0] 復(fù)制到 low 所指位置

• 當(dāng) A[mid]==A[0] 時，為了保證算法的“穩(wěn)定性”，應(yīng)繼續(xù)在 mid 所指位置右邊尋找插入位置

代碼實現(xiàn)：

比起“直接插入排序”，比較關(guān)鍵字的次數(shù)減少了，但是移動元素的次數(shù)沒變，整體來看時間復(fù)雜度依然是O(n^2)

對鏈表進(jìn)行插入排序：

• 使用鏈表不需要對序列進(jìn)行依次友誼，移動元素的次數(shù)變少了

• 但是關(guān)鍵字對比的次數(shù)依然是O(n^2) 數(shù)量級，整體來看時間復(fù)雜度依然是O(n^2)

希爾排序

算法思想：

• 先追求表中元素部分有序，再逐漸逼近全局有序

• 先將待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表，對各個子表分別進(jìn)行直接插入排序?？s小增量d，重復(fù)上述過程，直到d=1為止。

代碼實現(xiàn)：

算法性能分析：

• 空間復(fù)雜度：O(1)

• 時間復(fù)雜度：

  • 和增量序列 d1, d2, d3… 的選擇有關(guān)，目前無法用數(shù)學(xué)手段證明確切的時間復(fù)雜度

  • 最壞時間復(fù)雜度為 O(n^2)，當(dāng)n在某個范圍內(nèi)時，可達(dá)O(n^1.3)

• 穩(wěn)定性：不穩(wěn)定

• 適用性：僅適用于順序表，不適用于鏈表

冒泡排序

交換排序分類：

• 冒泡排序

• 選擇排序

算法思想：

• 從后往前（或從前往后）兩兩比較相鄰元素的值，若為逆序（即A[i-1]>A[i]），則交換它們，直到序列比較完

• 這樣過程稱為“一趟”冒泡排序

• 第n趟結(jié)束后，最小的n個元素會“冒”到最前邊

• 若某一趟排序沒有發(fā)生“交換”，說明此時已經(jīng)整體有序。

• 可以從后往前冒泡，也可以沖前往后冒泡

代碼實現(xiàn)：

算法性能分析：

• 空間復(fù)雜度：O(1)

• 時間復(fù)雜度：

  • 最好情況（有序）：O(n)

  • 最壞情況（逆序）：O(n^2)

  • 平均情況：O(n^2)

• 穩(wěn)定性：穩(wěn)定

• 適用性：順序表、鏈表都可以

快速排序

算法思想：

• 在待排序表L[1…n]中任取一個元素pivot作為樞軸（或基準(zhǔn)，通常取?元素）

• 通過一趟排序?qū)⒋判虮韯澐譃楠毩⒌膬刹糠諰[1…k-1]和L[k+1…n]

• 使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot

• 則pivot放在了其最終位置L(k)上，這個過程稱為一次“劃分”

• 然后分別遞歸地對兩個子表重復(fù)上述過程，直至每部分內(nèi)只有一個元素或空為止，即所有元素放在了其最終位置上

代碼實現(xiàn)：

算法性能分析：

• n個結(jié)點的二叉樹

  • 最小高度 = ?log2n? + 1

  • 最大高度 = n

• 時間復(fù)雜度=O(n*遞歸層數(shù))

  • 最好時間復(fù)雜度=O(nlog2n)

    • 每次選的樞軸元素都能將序列劃分成均勻的兩部分

  • 最壞時間復(fù)雜度=O(n^2)

    • 若序列原本就有序或逆序，則時、空復(fù)雜度最高（可優(yōu)化，盡量選擇可以把數(shù)據(jù)中分的樞軸元素。）

• 空間復(fù)雜度=O(遞歸層數(shù))

  • 最好空間復(fù)雜度=O(log2n)

  • 最壞空間復(fù)雜度=O(n)

• 若每一次選中的“樞軸”將待排序序列劃分為很不均勻的兩個部分，則會導(dǎo)致遞歸深度增加，算法效率變低

• 若初始序列有序或逆序，則快速排序的性能最差（因為每次選擇的都是最靠邊的元素）

• 快速排序算法優(yōu)化思路：盡量選擇可以把數(shù)據(jù)中分的樞軸元素。

  • 選頭、中、尾三個位置的元素，取中間值作為樞軸元素；

  • 隨機選一個元素作為樞軸元素

• 快速排序是所有內(nèi)部排序算法中平均性能最優(yōu)的排序算法

• 穩(wěn)定性：不穩(wěn)定

簡單選擇排序

選擇排序分類：

• 簡單選擇排序

• 堆排序

算法思想：

每一趟在待排序元素中選取關(guān)鍵字最?。ɑ蜃畲螅┑脑兀恳惶舜判蛐蛄虚L度-1）加入有序子序列（每一趟有序序列長度+1）

代碼實現(xiàn)：

算法性能分析：

• 無論有序、逆序、還是亂序，一定需要 n-1 趟處理

• 總共需要對比關(guān)鍵字 (n-1)+(n-2)+…+1=[n(n-1)]/2次

• 元素交換次數(shù) < n-1

• 空間復(fù)雜度：O(1)

• 時間復(fù)雜度=O(n^2)

• 穩(wěn)定性：不穩(wěn)定

• 適用性：既可以用于順序表，也可用于鏈表

堆排序

堆的定義：

• 若n個關(guān)鍵字序列L[1…n] 滿足下面某一條性質(zhì)，則稱為堆（Heap）：

  • 若滿足：L(i)≥L(2i)且L(i)≥L(2i+1) （1 ≤ i ≤n/2 ）則為大根堆（大頂堆）

    • 即完全二叉樹中，任意根≥左、右

  • 若滿足：L(i)≤L(2i)且L(i)≤L(2i+1) （1 ≤ i ≤n/2 ）則為小根堆（小頂堆）

    • 即完全二叉樹中，任意根≤左、右

建立大根堆：

• 把所有非終端結(jié)點都檢查一遍，是否滿足大根堆的要求，如果不滿足，則進(jìn)行調(diào)整

  • 在順序存儲的完全二叉樹中，非終端結(jié)點編號 i≤?n/2?

  • 檢查當(dāng)前結(jié)點是否滿足 根≥左、右，若不滿足，將當(dāng)前結(jié)點與更大的一個孩子互換

    • i的左孩子：2i

    • i的右孩子：2i+1

    • i的父結(jié)點：?i/2?

  • 若元素互換破壞了下一級的堆，則采用相同的方法繼續(xù)往下調(diào)整（小元素不斷“下墜”）

建立大根堆（代碼）：

基于大根堆進(jìn)行排序：

• 選擇排序：每一趟在待排序元素中選取關(guān)鍵字最大的元素加入有序子序列

• 堆排序每一趟完成以下工作：

  • 將堆頂元素（就是最大的元素）加入有序子序列（與待排序序列中的最后一個元素交換）

  • 并將待排序元素序列再次調(diào)整為大根堆（小元素不斷“下墜”）

• 注意：大根堆獲得的排序序列是遞增序列，小跟堆相反，獲得的是遞減序列

代碼實現(xiàn)（大根堆排序）：

堆排序的效率分析：

• 建堆的過程，關(guān)鍵字對比次數(shù)不超過4n，建堆時間復(fù)雜度=O(n)

• 堆排序的時間復(fù)雜度 =O(n) + O(nlog2n) = O(nlog2n)

• 堆排序的空間復(fù)雜度 =O(1)

• 穩(wěn)定性：不穩(wěn)定

堆的插入刪除

基本操作：

• i的左孩子：2i

• i的右孩子：2i+1

• i的父結(jié)點：?i/2?

在堆中插入新元素：

• 對于小根堆，新元素放到表尾，與父節(jié)點對比，若新元素比父節(jié)點更小，則將二者互換。

• 新元素就這樣一路“上升”，直到無法繼續(xù)上升為止

在堆中刪除元素：

• 被刪除的元素用堆底元素替代

• 然后讓該元素不斷“下墜”，直到無法下墜為止

關(guān)鍵字對比次數(shù)：

• 每次“上升”調(diào)整只需對比關(guān)鍵字1次

• 每次“下墜”調(diào)整可能需要對比關(guān)鍵字2次，也可能只需對比1次

歸并排序

算法思想：

• 把兩個或多個已經(jīng)有序的序列合并成一個

• 對于兩個有序序列，將i、j指針指向序列的表頭，選擇更小的一個放入k所指的位置

• k++，i/j指向更小元素的指針++

• 只剩一個子表未合并時，可以將該表的剩余元素全部加到總表

• m路歸并：每選出一個小的元素，需要對比關(guān)鍵字m-1次

• 核心操作：把數(shù)組內(nèi)的兩個有序序列歸并為一個

代碼實現(xiàn)：

• low是數(shù)組中第一個有序序列的開始

• mid是數(shù)組中第一個有序序列的結(jié)尾

• high是數(shù)組中第二個有序序列的結(jié)尾

• 輔助數(shù)組B臨時存放這兩段有序序列

算法效率分析：

• 2路歸并的“歸并樹”形態(tài)上就是一棵倒立的二叉樹

• 二叉樹的第h層最多有2 ^ (h-1)個結(jié)點，若樹高為h，則應(yīng)滿足n <= 2 ^ (h-1)，即h ? 1 = ?log2n?

• n個元素進(jìn)行2路歸并排序，歸并趟數(shù)=?log2n?

• 每趟歸并時間復(fù)雜度為O(n)，則算法時間復(fù)雜度O(nlog2n)

• 空間復(fù)雜度=O(n)，來自于輔助數(shù)組B

• 穩(wěn)定性：穩(wěn)定

基數(shù)排序

算法思想：

基數(shù)排序得到遞減序列的過程如下：

• 初始化： 設(shè)置 r 個空隊列，Qr-1, Qr-2,…, Q0

• 按照各個 關(guān)鍵字位 權(quán)重遞增的次序（個、十、百），對 d 個關(guān)鍵字位分別做“分配”和“收集”

• 分配：順序掃描各個元素，若當(dāng)前處理的關(guān)鍵字位=x，則將元素插入 Qx 隊尾

• 收集：把 Qr-1, Qr-2,…, Q0 各個隊列中的結(jié)點依次出隊并鏈接

基數(shù)排序得到遞增序列的過程如下：

• 初始化： 設(shè)置 r 個空隊列，Q0, Q1,…, Qr?1

• 按照各個 關(guān)鍵字位 權(quán)重遞增的次序（個、十、百），對 d 個關(guān)鍵字位分別做“分配”和“收集”

• 分配：順序掃描各個元素，若當(dāng)前處理的關(guān)鍵字位=x，則將元素插入 Qx 隊尾

• 收集：把 Q0, Q1,…, Qr?1 各個隊列中的結(jié)點依次出隊并鏈接

算法效率分析：

• 需要r個輔助隊列，空間復(fù)雜度 = O(r)

• 一趟分配O(n)，一趟收集O(r)，總共 d 趟分配、收集，總的時間復(fù)雜度=O(d(n+r)）

• 穩(wěn)定性：穩(wěn)定

基數(shù)排序的應(yīng)用：

• 例如：

  • 某學(xué)校有10000名學(xué)生，將學(xué)生信息按照年齡遞減排序

  • 給十億人的身份證號排序

• 基數(shù)排序擅長解決的問題：

  • 數(shù)據(jù)元素的關(guān)鍵字可以方便地拆分為 d 組，且 d 較小

  • 每組關(guān)鍵字的取值范圍不大，即 r 較小

  • 數(shù)據(jù)元素個數(shù) n 較大

外部排序

外存、內(nèi)存的數(shù)據(jù)交換：

• 外存：

  • 操作系統(tǒng)以“塊”為單位對磁盤存儲空間進(jìn)行管理

  • 如：每塊大小 1KB各個磁盤塊內(nèi)存放著各種各樣的數(shù)據(jù)

• 內(nèi)存：

  • 磁盤的讀/寫以“塊”為單位

  • 數(shù)據(jù)讀入內(nèi)存后才能被修改

  • 修改完了還要寫回磁盤

外部排序原理：

• 數(shù)據(jù)元素太多，無法一次全部讀入內(nèi)存進(jìn)行排序

• 使用“歸并排序”的方法，最少只需在內(nèi)存或只能怪分配3塊大小的緩沖區(qū)即可對任意一個大文件進(jìn)行排序

• ”歸并排序“要求各個子序列有序，每次讀入兩個塊的內(nèi)容，進(jìn)行內(nèi)部排序后寫回磁盤

構(gòu)造初始“歸并段”：

若有N個記錄，內(nèi)存工作區(qū)可以容納L個記錄，則初始?xì)w并段數(shù)量=r=N/L

第一趟歸并：

第二趟歸并：

第三趟歸并：

時間開銷分析：

外部排序時間開銷=讀寫外存的時間+內(nèi)部排序所需時間+內(nèi)部歸并所需時間

優(yōu)化思路：

• 多路歸并

  • 采用多路歸并可以減少歸并趟數(shù)，從而減少磁盤I/O(讀寫)次數(shù)

  • 對 r 個初始?xì)w并段，做k路歸并，則歸并樹可用 k 叉樹表示，若樹高為h，則歸并趟數(shù) = h-1 = ?logkr?

  • 推導(dǎo)：k叉樹第h層最多有k^(h?1) 個結(jié)點，則r ≤ kh?1， (h-1)最小 = ?logkr?

  • k越大，r越小，歸并趟數(shù)越少，讀寫磁盤次數(shù)越少

  • 多路歸并帶來的負(fù)面影響：

    • k路歸并時，需要開辟k個輸入緩沖區(qū)，內(nèi)存開銷增加

    • 每挑選一個關(guān)鍵字需要對比關(guān)鍵字（k-1）次，內(nèi)部歸并所需時間增加（可使用敗者樹優(yōu)化）

• 減少初始?xì)w并段數(shù)量

  • 生成初始?xì)w并段的“內(nèi)存工作區(qū)”越大，初始?xì)w并段越長

敗者樹

定義：

• 可視為一棵完全二叉樹（多了一個頭頭）

• k個葉結(jié)點分別是當(dāng)前參加比較的元素，非葉子結(jié)點用來記憶左右子樹中的“失敗者”，而讓勝者往上繼續(xù)進(jìn)行比較，一直到根結(jié)點。

• 即失敗者留在這一回合，勝利者進(jìn)入下一回合比拼

敗者樹在多路平衡歸并中的應(yīng)用：

敗者樹的存儲結(jié)構(gòu)：

置換-選擇排序

• 使用置換-選擇排序，可以讓每個初始?xì)w并段的長度超過內(nèi)存工作區(qū)大小的限制

• 設(shè)初始待排文件為FI，初始?xì)w并段輸出文件為FO，內(nèi)存工作區(qū)為WA，F(xiàn)O和WA的初始狀態(tài)為空，WA可容納w個記錄。

• 置換-選擇算法的步驟如下：

  • 從FI輸入w個記錄到工作區(qū)WA。

  • 從WA中選出其中關(guān)鍵字取最小值的記錄，記為MINIMAX記錄。

  • 將MINIMAX記錄輸出到FO中去。

  • 若FI不空，則從FI輸入下一個記錄到WA中。

  • 從WA中所有關(guān)鍵字比MINIMAX記錄的關(guān)鍵字大的記錄中選出最小關(guān)鍵字記錄，作為新的MINIMAX記錄。

  • 重復(fù)3）～5），直至在WA中選不出新的MINIMAX記錄為止，由此得到一個初始?xì)w并段，輸出一個歸并段的結(jié)束標(biāo)志到FO中去。

  • 重復(fù)2）～6），直至WA為空。由此得到全部初始?xì)w并段。

最佳歸并樹

引子：

• 歸并過程中磁盤I/O次數(shù)=歸并樹的WPL*2

• 因此要讓磁盤I/O次數(shù)最小，就要使歸并樹的WPL最小即構(gòu)建一個哈夫曼樹

m叉最佳歸并樹的構(gòu)造：

• 注意：對于k叉歸并，若初始?xì)w并段的數(shù)量無法構(gòu)成嚴(yán)格的k叉歸并樹

• 則需要補充幾個長度為0的“虛段”，再進(jìn)行k叉哈夫曼樹的構(gòu)造

增加虛段的數(shù)量：

• 若（初始?xì)w并段數(shù)量 -1）% （k-1）= 0，說明剛好可以構(gòu)成嚴(yán)格k叉樹，此時不需要添加虛段

• 若（初始?xì)w并段數(shù)量 -1）% （k-1）= u ≠ 0，則需要補充 (k-1) - u 個虛段文章來源地址http://www.zghlxwxcb.cn/news/detail-404702.html

到了這里，關(guān)于一篇學(xué)完：王道考研408數(shù)據(jù)結(jié)構(gòu)（全）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！