Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++

Presentation on theme: "Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++"— Presentation transcript:

1 Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
左傾樹（Leftist Tree） Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++

2 擴充二元樹(extendedbinary tree)
在擴充二元樹中，方形節點稱為外部節點(external node)。原有的節點為內部節點(internal node)。

3

4 shortest(x) 令x為擴充二元樹的節點。令left_child(x)和right_child(x)分別表示內部節點x的左、右子節點。
shortest(x)= 0 if x is an external node 1+min{shortest(left_child(x)),shortest(right_child(x))}

5 左傾樹定義 左傾樹為二元樹，它如果不是空的，則對每一內部節點x，
shortest(left_child(x)) ≧ shortest(right_child(x))

6 公式 令x為有n個(內部)節點的左傾樹之根節點。n ≧ 2shortest(x) –1
Proof:根據shortest(x)的定義，在左傾樹第一個shortest(x)階層不會有外部節點。因此，左傾樹至少有 shortest(x) Σ 2i-1 = 2shortest(x) –1 i=1

7 最小左傾樹(min-leftist tree) (或最大左傾樹(max-leftist tree))

8 Combine的步驟 挑出a、b之root的最小值作為新樹之root(令a為最小)。
A之root為新樹之root，且a之左子樹保留，將a之右子樹與b合併 。 重複前兩個步驟，直到合併完成。 檢查有無滿足min leftist tree性質，若沒有，則要對調左右子樹來調整。

9 Ｃ typedef struct { int key; /*other field*/ }element;
typedef struct *leftist_tree; struct leftist{ leftist_tree left_child; element data; leftist_tree right_child; int shortest; };

10 Ｃ void min-combine(leftist_tree *a, leftist_tree *b){
/*combine the two min leftist trees *a and *b. The resulting min leftist tree is returned in *a, and *b is set to NULL*/ if(!a){ *a = *b; }else if(*b){ min-union(a,b); } *b = NULL;

11 void min-union(leftist_tree *a, leftist_tree *b){
/*recursively combine two nonempty min leftist trees*/ leftist_tree temp; /*set a to be the tree with smaller root*/ if((*a)->data.key > (*b)->data.key){ SWAP(*a,*b,temp);} /*create binary tree such that the smallest key in each subtree is the root*/ if(!(*a)->right_child){ (*a)->right_child = *b; }else{ min_union(&(*a)->right_child,b);} /*leftist tree property*/ if(!(*a)->left_child){ (*a)->left_child = (*a)->right_child; (*a)->right_child = NULL; }else if((*a)->left_child->shortest<(*a)->right_child-<shortest){ SWAP((*a)->left_child,(*a)->right_child,temp); (*a)->shortest = (!(*a)->right_child)?1:(*a)->right_child->shortest +1;}}

12 Java class Element{ int key; /*other field*/ } class LeftistTree{
LeftistTree leftChild; LeftistTree rightChild; int shortest;

13 Java void minCombine(LeftistTree a, leftistTree b){
/*combine the two min leftist trees a and b. The resulting min leftist tree is returned in a and b is set to null*/ if(a==null){a=b;} else if(b!=null){ minUnion(a,b) } b=null;

14 void minUnion(LeftistTree a, LeftistTree b){
/*recursively combine two nonempty min leftist trees*/ LeftistTree temp; /*set a to be the tree with smaller root*/ if(a.data.key > b.data.key){swap(a,b,temp);} /*create binary tree such that the smallest key in each subtree is the root*/ if(a.rightChild==null){a.rightChild=b;} else{minUnion(a.rightChild,b);} /*leftist tree property*/ if(a.leftChild==null){ a.leftChild= a.rightChild; a.rightChild=null; }else if(a.leftChild.shortest < a.rightChild.shortest){ swap(a.leftChild,a.rightChild,temp); } a.shortest = (a.rightChild == null)?1 : a.rightChild.shortest+1;

15 分析min-combine 因為min-union沿著兩個要結合的左傾樹的最右邊的路徑向下移動，且這些路徑的長度最多為每一樹中元素個數的對數函數，所以合併全部元素個數為n的兩個左傾樹所需時間為O(log n)。

16 min-union 交替進行下列步驟： (1)建立包含所有元素的二元樹，並確認每一個子樹的根節點的鍵值是該子樹中最小的。
(2)確認每一節點有一左子樹，其shortest值大於或等於其右子樹的shortest值。

17 範例：結合兩最小左傾樹

18

19

20 Exercise：合併下列兩個左傾樹 1 3 2 4 5 9 10 6 8 12 15 請寫出全部過程!!

21 解答 1 3 2 4 5 6 9 8 10 12 15

22 The End 謝謝大家!!