數(shù)據(jù)結(jié)構(gòu)及其變化

集合

散列表

定義：

散列表：通過將元素映射到該表中的某一位置，來提高訪問速度 
裝填因子：元素的個數(shù)/表的長度 
碰撞： 多個關(guān)鍵字映射到同一位置的現(xiàn)象 
碰撞檢測方案：直接尋址法和鏈接法 
簡單一致散列：每個元素散列時是獨立的，與其他元素無關(guān) 
一致散列：假設(shè)每個關(guān)鍵字的探察序列`<0,1,2,…,m-1>的m!中排列的每一種可能性是相同的 
關(guān)鍵字集合靜態(tài)：關(guān)鍵字集合存入表中后不再變化

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

即映射函數(shù) 。 
好的映射函數(shù)應(yīng)該滿足簡單一致散列 
通常利用關(guān)鍵字分布的限制性信息來設(shè)計，稱為啟發(fā)式

乘法散列

h_k = ka

除法散列

h_k = k mod a

全域散列及設(shè)計

作用在大小為m的表上的一組映射函數(shù)H，其能夠保證任意兩個元素，最多只有|H|/m個映射函數(shù)會發(fā)生碰撞。 
這個設(shè)計的平均性能比較好

選則一個大質(zhì)數(shù)p p> max(e) 
h_a,b(k)=((ak+b)mod p)mod m 
H_p,m={h_a,b:a∈Z_p^* ,b∈Z_p} 
H_p,m中共有p(p-1)個散列函數(shù)

設(shè)計證明：

即證明選擇不同的值發(fā)生碰撞的概率不大于1/m 
1 對于任意兩個元素k,l(k!=l) r=(ak+b)mod p s=(al+b)mod p 可證明r!=s 
2 可用r s 來表示a,b a=((r-s)((k-l)^-1 mod p)) mod p, b=(r-ak)mod p 重要的是可以證明<r,s>對和<a,b>對一一對應(yīng)。 
3 可證明 給定r,p的選擇數(shù)目為p-1個， 碰撞概率 r== s mod m 的數(shù)目最多為 (p-1)/m,所以碰撞概率最多為1/m

完全散列

定義：在靜態(tài)集合上最壞查找是O(1)的散列技術(shù)

1 最外圍函數(shù)為h(k)=((ak+b)mod p)mod m (是全域散列) 
2 散列表S的大小為m_j 相關(guān)的散列函數(shù)為h_j(k)=((a_jk+b_j)mod p)mod m_j 
3 m_j為落在該pos下的元素個數(shù)的平方

E(x)=C_n² * 1n2 = n2n2*1n2 < 1/2

開放地址法

所有的元素都放在表中。依據(jù)探查序列算法解決發(fā)生碰撞時下一個探查的位置 
該結(jié)構(gòu)在刪除元素時，不能將對應(yīng)的位置設(shè)置為空，而是設(shè)置一個deleted的標記 
線性探查 h(k,i)=(h(k)+ci)mod m 
二次探查 h(k,i)=(h(k)+c₁i+c₂i²)mod m 
雙重散列 h(k,i)=(h(k)+h₂(k)i)mod m

線

棧

后進先出的數(shù)據(jù)結(jié)構(gòu)

隊列

先進先出的數(shù)據(jù)結(jié)構(gòu)

樹

二叉樹

完全二叉樹:只有最下面的兩層結(jié)點度能夠小于2，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置的二叉樹 
滿二叉樹:除最后一層無任何子節(jié)點外，每一層上的所有結(jié)點都有兩個子結(jié)點二叉樹 
平衡二叉樹:其左右高度相差不超過1，并且都是平衡二叉樹， 
各基本操作的運行時間都是O(h) h為樹的高度 
avl樹=二叉搜索樹+平衡

紅黑書

根節(jié)點和葉子節(jié)點是黑色的，兩者之間黑色節(jié)點的個數(shù)是相同的。另外一種樹是紅樹，其子節(jié)點都是黑樹 此為紅黑樹 
最壞情況下操作時間為O(lgn) 
每個節(jié)點 (color,key,left,right和p)

左旋

長子的次子是自己的長子 
自己是長子的次子

右旋

次子的長子是自己的次子 
自己是次子的長子

增

根據(jù)二叉樹找到掛靠的父節(jié)點，直接插入，顏色為紅 
增調(diào)：（紅黑顛倒簡稱倒） 
伯紅 => 伯父爺?shù)?我=我爺 命名為(上竄) 
伯黑 => （我是長子 => 我=父 左旋）父爺?shù)?爺右旋

刪

確定實際要刪的節(jié)點y（當前節(jié)點(雙子不全)或者其繼任）所以y一定不是雙子 
確定y的替代節(jié)點x（唯一的孩子或空 ） 
x向上取代y 
若y黑，則刪調(diào) 
刪調(diào)：比較麻煩，后續(xù)再提煉

B樹

定義 B樹是平衡(t+)叉樹 t>=2 是最小度數(shù)

曾

B-TREE-SPLIT-CHILD ：當前節(jié)點中間關(guān)鍵字放到上面，左右分拆為兩個 
B-TREE-INSERT-CHILD： 
1 當跟節(jié)點為2t-1時，拆 
2 插入元素到指定node位置，如果node滿了，拆；（如果父節(jié)點滿了，拆）

刪

1 刪掉指定元素k 如果該元素位于內(nèi)節(jié)點中。如果其有合適的前繼或后繼e，則刪掉e;否則刪掉k,合并左右子節(jié)點， 
2 若合并 則進行合并后調(diào)整: 檢查該節(jié)點元素個數(shù)，如果不滿足，則從左右兄弟拉元素或者合并

二叉堆

父元素大于（或小于）子元素的滿二叉樹

二項堆

可合并堆

支持create、insert、min、pop、union五種操作（建增查刪合）的數(shù)據(jù)結(jié)構(gòu)

二項樹

一種遞歸定義的有序樹。二項樹B₀只包含一個節(jié)點。二項樹B_k 由兩棵B_k-1連接而成，其中一顆樹是另一棵樹的左孩子。 
最小堆有序:結(jié)點的關(guān)鍵字大于或等于其父節(jié)點的關(guān)鍵字。

二項堆

最壞情況下時間復(fù)雜度為lgn 
是具有最小堆有序性質(zhì)的二項樹的一個集合，其中不存在根度數(shù)重復(fù)的元素 
容易證明m個元素 二項樹的個數(shù)為<=lg₂m+1

斐波那契堆

除刪除外其余操作時間為O(1) 
由一組最小堆有序樹構(gòu)成，但不一定是二項樹 
樹根之間是無序的，樹根之間和各個樹內(nèi)部都是雙鏈。

圖

先序、中序、后序

最小生成樹

無向加權(quán)連通圖<G,E> ,選擇一組E₁ ,E₁ ∈E,能連接所有頂點，求min(E₁)

kruskal算法（OElgE）

優(yōu)先收集全圖最小邊（除非該邊的兩個頂點都在已知的頂點中）

Prim算法（OElgV）

收集已知頂點外圍的最小邊

單源最短路徑

最短路徑估計：對每個頂點v∈V,都設(shè)置一個屬性d[v],用來描述從源點到v的最短路徑的上界。 
松弛技術(shù)： 
1 初始化每個頂點v與原點u間的最短路徑估計為無窮 
2 針對

bellman-ford算法（OEV）

用每個頂點松弛每條邊 ,可以處理邊為負數(shù)的情況

dijkstra算法（Ov²）

1 頂點集合S，將S邊上最短路徑的頂點u加入S 
2 使用u松弛u周圍的邊 
不可以處理邊為負數(shù)的情況

多源最短路徑

定義：計算每對頂點間的最短路徑 
閉包：任何頂點之間都存在路徑的有向圖

floyd-warshall算法(OV₃)

用任意頂點k松弛任意兩個頂點<u,v>間的邊

johnson算法

依次執(zhí)行Dijkstra算法

最大流

流守恒：進入某頂點的速度等于離開該頂點的速度 
問題描述：在不違背容量限制的條件下，把物質(zhì)從源點傳輸?shù)絽R點的最大速率是多少？ 
ford-fulkerson方法依賴三種重要思想:殘留網(wǎng)絡(luò)，增廣路徑、割。

殘留流量

C_f(u,v)=c(u,v)-f(u,v)

殘留網(wǎng)絡(luò)

給定一流網(wǎng)絡(luò)G=(V,E)和流f，由f壓得的G的殘留網(wǎng)絡(luò)是G_f=(V,E_f)

增廣路徑

增廣路徑為殘留網(wǎng)絡(luò)中的一條從源點到匯點的簡單路徑

流網(wǎng)絡(luò)的割

將網(wǎng)絡(luò)切成兩部分的一種割法 
最小割 就是最小容量的割 
最大流最小割 最小割就是最大流

基本的ford-fulkerson算法

1 全置0 
2 依次尋找一個增廣路徑p,計算其最小容量c 
3 依次對該路徑上的每段子路徑的流加上c，每段子路徑的容量減去c 
所以算法的關(guān)鍵是如何尋找到一個增廣路徑（尋增算法）

edmonds-karp算法

使用廣度優(yōu)先算法找增廣路徑

壓入與重標記算法

定義 依次檢查殘留網(wǎng)絡(luò)的每個頂點的相鄰頂點 
兩種基本操作：1 把流的余量從一個頂點壓向另一個頂點 2重標記 
壓入：把當前節(jié)點的余流沿著邊壓向鄰點 
重標記：當前邊為最低鄰點的高度+1