資料結構(計財系)

樹狀結構 簡介 樹的走訪(traverse) 左子右兄弟樹 二元搜尋樹 勝者樹與敗者樹(winner tree, loser tree) 互斥集合(Disjoint set) 不用指標表示樹

Winner Tree 當要合併k個排序好的序列(變成一個序列)時： 每次都找出串列頂端值最小的串列 把頂端取出來 如何把頂端最小的串列找出來? 15 16 … 20 38 30 25 28 50 11 95 99 18 10 9 6 8 90 17

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 … … … … … … … … … … … …

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 … … … … … … … … … … … … … … … …

Winner Tree 分析：(k個序列，共n個數字) 樹的深度： 第一次建樹： 當輸出某個節點，重新建樹： 合併k個串列： lg (k+1) 第一次建樹： O(k) 當輸出某個節點，重新建樹： O(lg k) 合併k個串列： O(n lg k)

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 … … … … … … … … … … … … … … … …

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 … … … … … … … … … … … … … … … …

Disjoint Set 在程式中如何表示互斥集合？ 先看集合應該有哪些運算： Union: 把兩個集合聯集 Find: 尋找某個項目在哪個集合中

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

Disjoint Set 用樹來表示集合： 每一個node有一個指標指向自己的root，以root代表 自己所在的集合 Find: 往parent找，找到是NULL為止 Union: 把其中一個人的parent指向另一集合的成員 Ex: Union(9,2) 6 8 7 4 1 9 2 3 5

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 ) ; }

Disjoint Set 退化樹： 以上union方法，可能會造成以下結果： 執行find時可能會變成O(n) 執行find時可能會變成O(n) 解決方式：Weighted union 1 2 3 …

Disjoint Set Weighted union ： Union的時候，把level比較小的人的root接在level比 較大的人的root 4 1 9 2

Disjoint Set Weighted union ： Union的時候，把level比較小的人的root接在level比 較大的人的root 如此一來可以保證， 假設有m個node時 樹的深度不會超過 (lg m) +1 8 3 7 4 1 9 2 6

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。其餘則不變

Disjoint Set 假設執行10次find(5)，每一次都會爬樹三層 4 1 9 2 8 3 7 6 5

Disjoint Set 假設執行10次find(5)，每一次都會爬樹三層 瓦解規則： Find找到後，把路徑上的點 都直接連接到root 8 3 7 4 1 9 2 6 5

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]; }

Disjoint Set Ackermann function Values of A(m, n)

Disjoint Set 用Weighted union與collapsing find進行連續 n次集合操作，其費時不會超過O(n×α(n)) 其中α(n)是Ackermann function A(n,n) 的反函 數 但是因為A(4,4)的值接近  ，因此α(n)可以 視為常數 證明略，更多相關可參考 http://en.wikipedia.org/wiki/Ackermann_f unction

不用指標表示樹 如果可以用陣列的index找到每個node，那其實 不一定要用指標來表示tree 前提：已經知道最多會有幾個node root 1 data 1 2 2 data 3 3 4 data data 4 5 6 5 data 6 data

不用指標表示樹 如果可以用陣列的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

不用指標表示樹 Disjoint set的程式碼