Download presentation
Presentation is loading. Please wait.
1
資料結構(計財系)
2
樹狀結構 簡介 樹的走訪(traverse) 左子右兄弟樹 二元搜尋樹 勝者樹與敗者樹(winner tree, loser tree)
互斥集合(Disjoint set) 不用指標表示樹
3
Winner Tree 當要合併k個排序好的序列(變成一個序列)時： 每次都找出串列頂端值最小的串列 把頂端取出來
如何把頂端最小的串列找出來? 15 16 … 20 38 30 25 28 50 11 95 99 18 10 9 6 8 90 17
4
Winner Tree 6 6 6 8 9 6 8 17 10 9 20 6 8 9 90 17 15 20 20 15 15 11 95 18 16 38 30 25 50 16 99 20 … … … 28 … … … … … … … … … … … …
5
Winner Tree 6 6 8 8 6 8 9 9 6 8 17 15 10 9 20 6 15 8 9 90 17 15 20 20 25 15 11 95 18 16 38 30 28 50 16 99 20 … … … … … … … … … … … … … … … …
6
Winner Tree 分析：(k個序列，共n個數字) 樹的深度： 第一次建樹： 當輸出某個節點，重新建樹： 合併k個串列：
lg (k+1) 第一次建樹： O(k) 當輸出某個節點，重新建樹： O(lg k) 合併k個串列： O(n lg k)
7
Loser Tree Winner tree 中，為了重建樹需要多看許多人，而且樹的節點很多數字都重複 6 8 6 8 9 9 6 8 17
15 10 9 20 6 15 8 9 90 17 15 20 20 25 15 11 95 18 16 38 30 28 50 16 99 20 … … … … … … … … … … … … … … … …
8
Loser Tree 如果改成存輸的人的鍵值呢? 不用多往旁邊看一次 6 8 8 9 9 17 15 10 20 9 90 20 10 9
25 15 11 95 18 16 38 30 28 50 16 99 20 … … … … … … … … … … … … … … … …
9
Disjoint Set 在程式中如何表示互斥集合？ 先看集合應該有哪些運算： Union: 把兩個集合聯集
Find: 尋找某個項目在哪個集合中
10
Disjoint Set 如果單純把每一個項目加上一個欄位… Find: O(1) Union: O(n)，太慢 1 Set=1 2
3 Set=2 3 Set=1 4 Set=1 4 Set=2 5 Set=1 6 Set=1 7 Set=1 8 Set=1 8 Set=2 9 Set=2 9 Set=1 10 Set=2 10 Set=1 11 Set=1 12 Set=1 13 Set=1 14 Set=1 14 Set=2 15 Set=1 15 Set=2 16 Set=1 16 Set=2
11
Disjoint Set 用樹來表示集合： 每一個node有一個指標指向自己的root，以root代表 自己所在的集合
Find: 往parent找，找到是NULL為止 Union: 把其中一個人的parent指向另一集合的成員 Ex: Union(9,2) 6 8 7 4 1 9 2 3 5
12
Disjoint Set struct NODE * find ( int key ) { struct NODE * tmp ;
for ( tmp = id_array[key] ; tmp->parent != NULL ; tmp = tmp->parent ) ; return tmp ; } void set_union ( int key1 , int key2 ) { id_array[key2]->parent = find ( key1 ) ; }
13
Disjoint Set 退化樹： 以上union方法，可能會造成以下結果： 執行find時可能會變成O(n)
執行find時可能會變成O(n) 解決方式：Weighted union 1 2 3 …
14
Disjoint Set Weighted union ：
Union的時候，把level比較小的人的root接在level比 較大的人的root 4 1 9 2
15
Disjoint Set Weighted union ：
Union的時候，把level比較小的人的root接在level比 較大的人的root 如此一來可以保證， 假設有m個node時 樹的深度不會超過 (lg m) +1 8 3 7 4 1 9 2 6
16
Disjoint Set 只有兩顆樹深度相同時，union後的新樹 depth會+1。其餘則不變
void set_union ( int key1 , int key2 ) { struct NODE * n1 ; struct NODE * n2 ; n1 = find ( key1 ) ; n2 = find ( key2 ) ; if ( depth[n1->key] > depth[n2->key] ) { n2->parent = n1 ; } else { n1->parent = n2 ; if ( depth[n1->key] == depth[n2->key] ) depth[n2->key] ++ ; } 只有兩顆樹深度相同時，union後的新樹 depth會+1。其餘則不變
17
Disjoint Set 假設執行10次find(5)，每一次都會爬樹三層 4 1 9 2 8 3 7 6 5
18
Disjoint Set 假設執行10次find(5)，每一次都會爬樹三層 瓦解規則： Find找到後，把路徑上的點 都直接連接到root
8 3 7 4 1 9 2 6 5
19
Disjoint Set struct Node* collapsing_find ( int key ) {
if(id_array[key]->parent !=NULL) { id_array[key]->parent = collapsing_find ( id_array[key]->parent->key ) ; return id_array[key]->parent; } else { return id_array[key]; }
20
Disjoint Set Ackermann function Values of A(m, n)
21
Disjoint Set 用Weighted union與collapsing find進行連續 n次集合操作，其費時不會超過O(n×α(n)) 其中α(n)是Ackermann function A(n,n) 的反函 數 但是因為A(4,4)的值接近 ，因此α(n)可以 視為常數 證明略，更多相關可參考 unction
22
不用指標表示樹 如果可以用陣列的index找到每個node，那其實 不一定要用指標來表示tree 前提：已經知道最多會有幾個node
root 1 data 1 2 2 data 3 3 4 data data 4 5 6 5 data 6 data
23
不用指標表示樹 如果可以用陣列的index找到每個node，那其實 不一定要用指標來表示tree 前提：已經知道最多會有幾個node
root 1 data 2 3 4 1 2 2 data 3 3 4 data data 4 5 6 5 6 5 data 6 data
24
不用指標表示樹 Disjoint set的程式碼
Similar presentations
