作業三禮拜四 5pm due 更多的樹 Michael Tsai 2010/10/29 請各位多利用下周二三四的 office hour
今日菜單 樹裡面找東西 選擇樹 ( 勝者樹與敗者樹 ) 樹的相關動作 ( 複製樹 ) 有線頭的樹 森林 解邏輯運算式
Binary search tree 問題 : 找系上某個同學的作業成績 條件 : 知道學號 (key) 找到學號就可以對應到儲存資料的地方 (search) 常常有人進來 (add node) 常常有人出去 (delete node)
Binary search tree Definition: A binary search tree is a binary tree. It may be empty. If it is not empty then it satisfies the following properties: 1. The root has a key. 2. The keys (if any) in the left subtree are smaller than the key in the root 3. The keys (if any) in the right subtree are larger than the key in the root 4. The left and right subtrees are also binary search trees ( 隱藏 ) All keys are distinct.
Binary search tree 30 這些是不是 binary search tree? 找到以後要做什麼? 20 15 25 2 60 5 40 Yes 80 號 HW1 65 HW2 65 HW3 空 Extra -20000 70 12 10 22 65 80 No Yes
如何尋找? 20 假設要找 10 12 22 10 15 element *search(tpointer root, int key) { if (!root) return NULL; if (k==root->data.key) return &(root->data); if (k<root->data.key) return search(root->leftchild, k); return search(root->rightchild, k); } 25 簡單. 那 time complexity = O(??)
如何插入新的 node? 先找有沒有一樣的 ( 隱藏版 rule: binary search tree 裡面不可以有一樣的 key) 找不到的話, 插在最後 找不到 的位置 插入 : 11 11 20 12 22 10 15 25
如何刪掉一個 node? 首先要先找到那個 node 接著, 有各種不同情形 : 20 如果沒有手 (degree=0) 直接拿掉 10 15 12 22 25 11
如何刪掉一個 node? 如果只有一隻手 (degree=1) 則把那個唯一的 child 拿上來接到 parent 上 20 例如 : 拿掉 25 15 25 10 12 22 問題 : 要怎麼接? 怎麼記得 parent 是誰? 11
如何刪掉一個 node? 如果兩手都有東西呢? (degree=2) 20 例如刪掉 12 找左邊 child 底下最大的 ( 或者是右邊 child 底下最小的 ) 10 15 12 22 25 刪掉它並把它移到原本刪掉的位置 11 問題 : 那如果那個最大的底下還有 child 呢?
一些 binary search tree 的動作 threewayjoin(small, mid, big) mid (small 裡面都比 mid 小, big 裡面都比 mid 大 ) mid->left=small; mid->right=big; 結束! small big height=?
一些 binary search tree 的動作 twowayjoin(small, big) (small 裡面的都比 big 裡面的小 ) mid 找到 small 裡面最小的 (O(??)) delete 它 ( 用前面講的刪 node 方法 ) 當成 mid threewayjoin(small, mid, big) small big height=? time complexity=o(??)
一些 binary search tree 的動作 split(tree,k,small,mid,big) 要把一棵 binary search tree 以 k 為分界切成 small, mid, big small 都比 k 小, big 都比 k 大, mid 跟 k 一樣 例子 : k=14 課本 program 5.18 20 13 22 10 15 25 11 14 16
s b small c k=14 20 big 13 22 10 15 25 11 14 16 mid
binary search tree 的高度 高度跟 node 數目有何關係? 20 h=o(log n)?? 13 15 No. In the worst case, h=o(n) 10 之後 chapter 10 & 11 會講到 h=o(log n) 的 balanced search trees
選擇樹 問題 : 有 k 組排好的數列, 要合併成一組 ( 共 n 個數字 ) 先來一個爛方法 每回合都比較各數列的頭頭 ( 共 k(k-1) 次 ), 比較出最大的一個 然後放入最後的數列裡 8 7 6 5 4 3 2 1 0 8 3 7 5 2 1 4 6 0 這樣的話, time complexity=ο
選擇樹 使用樹來記錄一些資訊 : 精神 : 上一回合比較的結果並不是全然無用 ( 只有上一回合勝出的數字和別人的比較結果需要重做 ) 紀錄一些資訊使得下一回合不用全部重來 目標 time complexity = Ο log
勝者樹 Tree 裡面記得每次贏的數字 很像錦標賽 用黑板講解 有沒有什麼缺點? 每次都要和 sibling 比 Linked representation 的時候不好找 從上一回合贏的那個數列一直到 root 每個數字都要改掉 ( 曼一點點 )
敗者樹 Tree 裡面記得每次贏的數字 用黑板講解 這樣就不需要跟 sibling 比了 每回合跟 parent 比, 輸的留下, 贏的晉級 time complexity=o(??) < 動腦時間 > 如果 2, 怎麼處理?
講一些輕鬆一點的 如果要拷貝 binary tree 怎麼做? 使用 recursive, 會很簡單 tpointer copy(tpointer original) { tpointer temp; if (original) { MALLOC(temp, sizeof(*temp)); temp->leftchild=copy(original->leftchild); temp->rightchild=copy(original->rightchild); temp->data=original->data; return temp; } return NULL; }
講一些輕鬆一點的 如果要測試兩個 binary tree 有沒有一模一樣怎麼做? 一樣用 recursive int equal(tpointer first, tpointer second) { if (!first &&!second) return TRUE; return (first->data == second->data) && equal(first->leftchild, second->leftchild) && equal(first->rightchild, second->rightchild); }
線頭樹?? root left A right left B right left C right 浪費浪費 left D right left E right 浪費浪費 left F right 浪費 left G right 浪費浪費浪費
浪費掉的 link field 可以拿來存一些別的資訊 Threaded Binary Tree 1. 如果 leftchild 是 null, 那就改成指到 inorder traversal 的前一個 node ( 又稱為 inorder predecessor) ( 此為 thread) 2. 如果 rightchild 是 null, 那就改成指到 inorder traversal 的後一個 node ( 又稱為 inorder successor) ( 此為 thread) 3. node 的 structure 裡面放兩個額外的 boolean 欄位, 說明是 link 還是 thread 效果 : 之後做 inorder traversal 不需要 stack 了!
Threaded binary tree 長這樣 root f A f f B f t C t t D t f E f f F t t G t t H t
Threaded Binary Tree 怎麼找到 inorder successor? 如果 rightthread == true, 那麼就是 thread 指到的地方 如果 rightthread == false, 那就找 rightchild 的 leftchild 一直 root 走到底 f A f f B f t C t t D t f E f f F t t G t t H t
Threaded Binary Tree 接著, 要做 inorder traversal 就很簡單了 for(;;) { temp=insucc(temp); if (temp==tree) break; // 走回 root 了 printf( %3c, temp->data); } < 動腦時間 > 如果要用 threaded binary tree 做 postorder or preorder traversal 呢?
在 Threaded Binary 裡面加一個 node f A f f B f t C t t D t f E f f F t t G ft t H t t I t
f A f f B f t C t t D t t I f f E f f F t t G t t H t
森林 Definition: A forest is a set of 0 disjoint trees. 要怎麼把森林轉成一棵 binary tree 呢? 提示 : 左小孩右兄弟姊妹法 + root 右手沒有連東西
森林的 traversal forest preorder (1) If F is empty then return (2) Visit the root of the first tree of F. (3) Traverse the subtrees of the first tree in forest preorder ( 把第一個 tree 的 subtrees 當成 forest) (4) Traverse the remaining trees of F in forest preorder 對應到轉換後的 binary tree 的 preorder traversal forest inorder 對應到轉換後的 binary tree 的 inorder traversal forest postorder 沒有對應 forest level-order
計算邏輯運算式 變數可為 true or false 三種 operator:,, 可以使用括號 例如 如何計算當,,,, 時的結果? 進階題 : 如何找出所有組合使得結果為 true?
計算邏輯運算式 用什麼 traversal 方法?
33 周末愉快 作業一已經改好 改好的作業下周會發給同學們. 成績分布會公布 請比較低分的同學多加留意! 多利用 office hour ( 下周二三四 ) 洲際盃中華 12:5 日本 請同學準備好下周要發問的問題 我也會準備一些我覺得重要的課題來複習