數據結構及其變化

集合

散列表

定義：

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

散列函數的設計

即映射函數 。 
好的映射函數應該滿足簡單一致散列 
通常利用關鍵字分布的限制性信息來設計，稱為啟發式

乘法散列

h_k = ka

除法散列

h_k = k mod a

全域散列及設計

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

選則一個大質數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)個散列函數

設計證明：

即證明選擇不同的值發生碰撞的概率不大于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>對一一對應。 
3 可證明 給定r,p的選擇數目為p-1個， 碰撞概率 r== s mod m 的數目最多為 (p-1)/m,所以碰撞概率最多為1/m

完全散列

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

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

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

開放地址法

所有的元素都放在表中。依據探查序列算法解決發生碰撞時下一個探查的位置 
該結構在刪除元素時，不能將對應的位置設置為空，而是設置一個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

線

棧

后進先出的數據結構

隊列

先進先出的數據結構

樹

二叉樹

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

紅黑書

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

左旋

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

右旋

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

增

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

刪

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

B樹

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

曾

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

刪

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

二叉堆

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

二項堆

可合并堆

支持create、insert、min、pop、union五種操作（建增查刪合）的數據結構

二項樹

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

二項堆

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

斐波那契堆

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

圖

先序、中序、后序

最小生成樹

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

kruskal算法（OElgE）

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

Prim算法（OElgV）

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

單源最短路徑

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

bellman-ford算法（OEV）

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

dijkstra算法（Ov²）

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

多源最短路徑

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

floyd-warshall算法(OV₃)

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

johnson算法

依次執行Dijkstra算法

最大流

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

殘留流量

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

殘留網絡

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

增廣路徑

增廣路徑為殘留網絡中的一條從源點到匯點的簡單路徑

流網絡的割

將網絡切成兩部分的一種割法 
最小割 就是最小容量的割 
最大流最小割 最小割就是最大流

基本的ford-fulkerson算法

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

edmonds-karp算法

使用廣度優先算法找增廣路徑

壓入與重標記算法

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