樹

樹 1 Michael Tsai 2013/3/19

2 樹 The family tree of Sigmund Christoph von Waldburg-Zeil-Trauchburg http://www.ahneninfo.com/de/ahnentafel.htm

3 在 CS 的世界裡, 通常我們都把樹畫顛倒 樹根在上面 一棵樹有什麼特性呢? 非線性 (nonlinear), 具階層式的 (hierarchical) 方式表示資料 葉子們在下面

4 樹的定義 Definition: A tree is a finite set of one or more nodes such that (1) There is a specially designated node called the root. (2) The remaining nodes are partitioned into n 0 disjoint sets T 1, T 2,, T n, where each of these sets is a tree. (3) T 1, T 2,, T n are called the subtrees of the root. 注意以上為遞迴定義 一個 node 沒有子樹的話, 是不是樹? 沒有 node 是不是樹? 右邊的是不是樹? 違反了什麼規則?

5 樹的字典 Root Node/Edge (branch) Degree (of a node): The number of subtrees of a node Leaf/Terminal node: its degree=0 Parent/Children Siblings they have the same parent. Ancestors/Descendants K A B C D E F G H I J L M

6 樹的字典 Level/depth (of a node): 從 root 走到那邊需要經過的 branch 數目. (root 在 level 0) Height (of a tree): tree 共有幾個 level. ( 注意 Karumanchi 裡面的定義略有不同 ) Size (of a tree): tree 裡面總共有幾個 node Weight (of a tree): tree 總共有幾個 leaf Degree (of a tree): tree 裡面 degree 最大的 node 的 degree K A B C D E F G H I J L Level 0 M Level 3 Level 1 Level 2

7 怎麼在記憶體裡面記一棵樹呢? Array 法 存什麼? 通常每個 node 會有一些資料. Array 法 依照 level 依序在 array 裡面儲存資料 在 array 裡面 : 怎麼找某個 node 的 parent? 怎麼找某個 node 的 children? A [0] [1]-[3] B C D [10]-[12] [7]-[9] [4]-[6] E F G H I J Max degree of the tree=3 0 1 2 3 4 5 6 7 8 9 10 11 12 A B C D E F G H I J

8 怎麼在記憶體裡面記一棵樹呢? Array 法 假設 degree=3 ( 每個 node 最多有三個 children) 怎麼找某個 node 的 parent? 觀察 : Index 為 i 的 node, 其 parent 之 index 為 (i 1)/d 怎麼找某個 node 的 children 觀察 : Index 為 i 的 node, 其 children 之 index 為 di + 1 ~ di + d [4]-[6] A [0] [1]-[3] B C D [7]-[9] [10]-[12] E F G H I J 想想看為什麼是這樣?

9 怎麼在記憶體裡面記一棵樹呢? Array 法 壞處是什麼? A 中間如果有許多沒有連接的地方, 許多 node 有少於 d 個 children 那 array 中間會有很多空白 B C D E G H I J 0 1 2 3 4 5 6 7 8 9 10 11 12 31 A B C D E G H I J K K Max degree of the tree=3 浪費很大!

10 怎麼在記憶體裡面記一棵樹呢? Linked Structure 法 假設 degree=3 struct TreeNode{ char data; struct TreeNode* child1; struct TreeNode* child2; struct TreeNode* child3; }; A A B C D 浪費很大! 變成浪費指標的部分 H I B \0 \0 \0 C \0 \0 \0 D \0 這樣問題解決了嗎? \0 代表 NULL. 在 C 裡面, NULL 的值其實就是 0 H \0 \0 \0 I \0 \0 \0

11 怎麼在記憶體裡面記一棵樹呢? Linked Structure 法 Data child 1 child 2 child 3 child k A 1 2 d B C ㄅ 假設 degree of tree = d, 總共有 n 個 nodes 有多少個 child 欄位是 NULL? 總共有 nd 個欄位 但是整棵樹有幾個 branch? n 1 個 nd n 1 = n d 1 + 1 越小越好! 浪費很大! 變成浪費指標的部分

12 左小孩 - 右兄弟姊妹表示法 Left child-right sibling representation Data left child Right sibling 觀察 : 1. 每個 node 最多只有一個最左邊的 child ( 是廢話 ) 2. 每個 node 也最多只有一個最靠近他的右邊的 sibling ( 也是廢話 )

13 來畫一下怎麼用 LC-RS 表示這棵樹? A A B C D B C D E F G H I J E F G H I J K L M K L M

14 左小孩 - 右兄弟姊妹樹 可以變成 degree-two tree 也就是說, 是一種把普通的樹轉成 degree-two 樹的方法 Root 沒有右邊的 child ( 也就是說原本的 LC-RS 樹裡面 root 不會有兄弟姊妹 - 廢話 ) A B C D E F G H I J K L M

15 Binary Tree Definition: A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree. 注意 : 可以是沒有 node 比較 : 一般 tree 不可以沒有 node 注意 : children 在左邊或右邊是不一樣的 ( 有順序 ) 比較 : 一般 tree 的 children 順序沒有差

16 一些證明 1. 在 level i 的 node 數目最多為 2 i, i 0 (root 在 level 0) 證明 : 用歸納法 i=0 時, 為 root 那一層, 所以只有一個 node, 也就是最多有 2 0 = 1 個 node. ( 成立 ) 假設 i=k-1 的時候成立 level k-1 最多有 2 k 1 個 node 那麼 i=k 的時候, 最多有幾個 node? 因為是 binary tree, 所以每個 node 最多有兩個 children 因此最多有 2 k 1+1 = 2 k node ( 得證 )

17 兩些證明 ( 誤 ) 2. 一棵 height 為 k 的 binary tree, 最多有 2 k 1 個 node, k 1. 證明 : 利用 1 的結果 則總共 node 數目最多為 k 1 0 2 i = 2k 1 = 2 1 2k 1. 喔耶.

18 三些證明 ( 誤 ) 3. 對於任何不是空的 binary tree, 假設 n 0 為 leaf node 數目, n 2 為 degree 2 的 node 數目, 則 n 0 = n 2 + 1. 證明 : 假設 n 為所有 node 數目, n 1 為 degree 1 的 node 數目, 則 n = n 0 + n 1 + n 2. (1) 假設 B 為 branch 的數目, 則 B = n 1 + 2n 2. (2) 而且 n = B + 1 (3). ( 只有 root 沒有往上連到 parent 的 branch, 其他的 node 正好每個人一個 ) (2) 代入 (3) 得 n = n 1 + 2n 2 + 1 (4) (4) 減 (1) 得 n 0 = n 2 + 1. 喔耶.

19 Full binary tree Definition: a full binary tree of depth k is a binary tree of depth k having 2 k 1 nodes, k 1. 也就是說 depth k 的樹裡面最多 node 數目的 ( 滿了 ) 除了 leaf 每個 node 都有兩個 children 1 2 3 4 5 6 7 depth=3 的 full binary tree

20 Complete binary tree Definition: A binary tree with n nodes and depth k is complete iff its nodes correspond to the nodes numbered from 1 to n in the full binary tree of depth k. 也就是說, 所有在 level k-1 和 k-2( 最底和倒數第二層 ) 的 leaf 都沒有 缺號. 1 1 1 1 1 2 3 2 3 2 2 2 3 4 5 4 5 6 4 5 5 6 Yes Yes Yes No No

21 Complete binary tree 的高度 如果一個 complete binary tree 有 n 個 node, 那麼樹的高度為? Hint: 高度為 k 的 full binary tree 有 2 k 1 個 node Hint: 在最底層總共有多少個 node? 答 : 最少有幾個 node? 2 k 1 2 k 1 + 1 = 2 k 1 所以 node 個數可能為 2 k 1 ~2 k 1 log 2 (n + 1) 在各種情況都可以得到 k

22 Binary Tree Traversal 有一棵 binary tree 後, 我們要怎麼把樹的每一個 node 都走一遍呢? 1 2 3 4 5 6 7 到某一個 node 的時候, 有三件事情可以做 : 1. 走左邊的 child 那邊的 node 們 ( 用 L 表示 Left branch) 2. 走右邊的 child 那邊的 node 們 ( 用 R 表示 Right branch) 3. 處理自己這個 node 的資料 ( 用 V 表示 Visit)

23 Binary Tree Traversal 如果 L 一定要在 R 之前, 那麼有三種 VLR: preorder LVR: inorder LRV: postorder A B E C G 請同學說明 preorder, inorder, postorder traversal 分別順序是如何

Binary tree with arithmetic expression 每個 arithmetic expression 都可以建立一個 expression tree 24 Preorder prefix Inorder infix Postorder postfix 請同學試試看 ( 亂寫一個 expression 看看 ) 2 3 * - 5 Reading Assignment: Karumanchi 6.9 How to build a expression tree?

25 Binary Tree Traversal 可以用 recursive 寫法來做 traversal ( 會很簡潔 ): void inorder(treepointer ptr) { inorder(ptr->leftchild); visit(ptr); inorder(ptr->rightchild); }

26 那如果不要用 recursive 寫法呢? 用 Stack for(;;) { for(;node;node=node->leftchild) push(node); A node=pop(); if (!node) break; printf( %s, node->data); B E } node=node->rightchild; C G

27 Level-order traversal A 如果改成用 queue 呢? add(ptr); for(;;) { ptr=delete(); if (ptr) { printf( %s, ptr->data); if (ptr->leftchild) add(ptr->leftchild); if (ptr->rightchild) add(ptr->rightchild); } else break; } C B G E

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. root.key <root.key >root.key

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

如何尋找? 假設要找 10 20 12 22 struct TreeNode* find(struct TreeNode* root, int data) { if (root==null) return NULL; if (data==root->data) return root; if (data<root->data) return find(root->left,data); return find(root->right, data); } 簡單. 那 time complexity = O(??) 答 : O(h), h: height of the tree. Worst case: O(n) Average case: O(log 2 n) 10 15 25 Binary Search Tree 的 Algorithm 常常是以上的型態 : (1) 如果 key 跟現在的 node 一樣, 那麼就做一些處理後 return 結果. (2) 如果 key 比較大或比較小, 分別 call 自己的分身去處理右邊或左邊的 subtree

32 其他使用方法 20 12 22 10 15 25 Q: 怎麼找到 Binary Search Tree 裡面最大 ( 小 ) 的元素? A: 一直往右 ( 左 ) 邊的 child 走去, 直到碰到 NULL 為止. (Karumanchi p.149) Q: 怎麼把 Binary Search Tree 裡面所有的元素依序列出? A: 做 Binary Search Tree 的 Inorder Traversal!

如何插入新的 node? 先找有沒有一樣的 ( 隱藏版 rule: binary search tree 裡面不可以有一樣的 key) 找不到的話, 插在最後 找不到 的位置 插入 : 11 11 20 12 22 10 15 25

struct BinarySearchTreeNode *Insert(struct BinarySearchTreeNode *root, int data) { if (root==null) { root=(struct BinarySearchTreeNode*)malloc(sizeof(struct BinarySearchTreeNode)); }else{ 回傳給上一層 } } if (root==null) { } return root; printf("error\n"); exit(-1); root->data=data; root->left=null; root->right=null; if (data<root->data) root->left=insert(root->left,data); else if (data>root->data) root->right=insert(root->right,data); 34 找到 NULL 表示已經到樹的 leaf 了, 而且沒有找到 插在這個位置 如果比較大或比較小, 交給自己的分身去處理

如何刪掉一個 node? 首先要先找到那個 node 接著, 有各種不同情形 : 20 如果沒有手 (degree=0) 直接拿掉 10 15 12 22 25 11

如何刪掉一個 node? 如果只有一隻手 (degree=1) 則把那個唯一的 child 拿上來接到 parent 上 20 例如 : 拿掉 25 12 22 10 15 25 問題 : 要怎麼接? 怎麼記得 parent 是誰? ( 回傳給 return 給上一層去設定, slide #37) (Karumanchi p.152) 11

如何刪掉一個 node? 如果兩手都有東西呢? (degree=2) 20 例如刪掉 12 找左邊 child 底下最大的 ( 或者是右邊 child 底下最小的 ) 10 15 12 22 25 刪掉它並把它移到原本刪掉的位置 11 問題 : 那如果那個最大的底下還有 child 呢? 答案 : 最多只會有一個 child, 所以很好處理

struct TreeNode *delete(struct TreeNode *root, int data) { 回傳給上一層, 如果把現在這個 node 殺掉的話, 則可以回傳給上一層的 pointer 接上 TreeNode * temp; if (root==null) { printf( error\n ); return NULL; } else if (data < root->data) root->left=delete(root->left, data); else if (data > root->data) root->right=delete(root->right, data); else { // data == root->data if (root->left && root->right) { //two children temp=findmax(root->left); root->data=temp->data; root->left=delete(root->left,root->data); }else{ // one child or no child } return root; } temp=root; if (root->left==null) root=root->right; if (root->right==null) free(temp); root=root->left; 38 如果比較大或比較小, 交給自己的分身去處理 如果一樣的話, 在這邊處理.

39 Today s Reading Assignments 本次的 reading assignment 重要性依序為 : 1. Karumanchi 6.1-6.7 2. Karumanchi 6.11 或 Cormen 12.1-12.3 3. Karumanchi Problem [6-7], [10-11],14,30,31 4. Karumanchi 6.9 5. Karumanchi Problem [49-52,59]