# 20191107 南山高中資訊班課程 政治大學 碩一 王柏仁 --- # 今日重點 1. 動態規劃 - Top Down A.K.A 樹狀圖法則複習 - Bottom Up A.K.A 表格法介紹 - 題目練習及討論 2. 樹的基本介紹( Content Credit : [交大資訊之芽](https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week02/) ) - 定義 - 樹種及名詞介紹 - 各種樹種的基本運作 - 題目練習及討論 --- # 動態規劃 - 範例：（背包客問題） 現在有三個物體 **==\{ A, B, C \}==**，**==價值分別為 \{ $60, $100, $120 \}，重量分別為 \{ 10g, 20g, 30g \}==**。現在有一個 **==限重 50g 的袋子==**。請問在條件之下，袋子中 **==最大價值為多少==**？ ---- # 動態規劃 Top Down A.K.A 樹狀圖法則複習 - 整體來看 ```graphviz digraph hierarchy { nodesep=1.0 node [fontname=Courier,shape=box] edge [color=Blue, style=dashed] 三個東西和50g的空間【0】->兩個東西和50g的空間【0】[label="沒有拿走 A"] 三個東西和50g的空間【0】->兩個東西和40g的空間【60】[label="拿走 A"] 兩個東西和50g的空間【0】->一個東西和30g的空間【100】[label="拿走 B"] 兩個東西和50g的空間【0】->一個東西和50g的空間【0】[label="沒有拿走 B"] 兩個東西和40g的空間【60】->一個東西和20g的空間【160】[label="拿走 B"] 兩個東西和40g的空間【60】->一個東西和40g的空間【60】[label="沒有拿走 B"] 一個東西和30g的空間【100】->沒有東西和30g的空間【100】[label="沒有拿走 C"] 一個東西和30g的空間【100】->沒有東西跟空間【220】[label="拿走 C"] 一個東西和40g的空間【60】->沒有東西和40g的空間【60】[label="沒有拿走 C"] 一個東西和40g的空間【60】->沒有東西和10g的空間【180】[label="拿走 C"] 一個東西和50g的空間【0】->沒有東西和20g的空間【120】[label="拿走 C"] 一個東西和50g的空間【0】->沒有東西和50g的空間【0】[label="沒有拿走 C"] 一個東西和20g的空間【160】->沒有東西且空間不夠【不成立】[label="拿走 C"] 一個東西和20g的空間【160】->沒有東西和20g的空間【160】[label="沒有拿走 C"] } ``` ---- # 動態規劃 Top Down A.K.A 樹狀圖法則複習 - 第一步 ```graphviz digraph hierarchy { nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 三個東西和50g的空間【0】->兩個東西和50g的空間【0】[label="沒有拿走 A"] 三個東西和50g的空間【0】->兩個東西和40g的空間【60】[label="拿走 A"] } ``` ---- # 動態規劃 Top Down A.K.A 樹狀圖法則複習 - 第二步 ```graphviz digraph hierarchy { nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 兩個東西和50g的空間【0】->一個東西和30g的空間【100】[label="拿走 B"] 兩個東西和50g的空間【0】->一個東西和50g的空間【0】[label="沒有拿走 B"] 兩個東西和40g的空間【60】->一個東西和20g的空間【160】[label="拿走 B"] 兩個東西和40g的空間【60】->一個東西和40g的空間【60】[label="沒有拿走 B"] } ``` ---- # 動態規劃 Top Down A.K.A 樹狀圖法則複習 - 第三步 ```graphviz digraph hierarchy { nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 一個東西和30g的空間【100】->沒有東西和30g的空間【100】[label="沒有拿走 C"] 一個東西和30g的空間【100】->沒有東西跟空間【220】[label="拿走 C"] 一個東西和40g的空間【60】->沒有東西和40g的空間【60】[label="沒有拿走 C"] 一個東西和40g的空間【60】->沒有東西和10g的空間【180】[label="拿走 C"] } ``` ```graphviz digraph hierarchy { nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 一個東西和50g的空間【0】->沒有東西和20g的空間【120】[label="拿走 C"] 一個東西和50g的空間【0】->沒有東西和50g的空間【0】[label="沒有拿走 C"] 一個東西和20g的空間【160】->沒有東西且空間不夠【不成立】[label="拿走 C"] 一個東西和20g的空間【160】->沒有東西和20g的空間【160】[label="沒有拿走 C"] } ``` ---- # 動態規劃 Bottom Up A.K.A 表格法介紹 - 整體來看 | 物體/重量/價值 |0|10|20|30|40|50| |:-----------------------------:|:--------------:|:------------:|:-------------:|:--------:|:---------:|:---------:| | A / 10g / $60 |0|60|60|60|60|60| | B / 20g / $100 |0|60|100|160|160|160| | C / 30g / $120 |0|60|100|160|180|220| ---- # 動態規劃 Bottom Up A.K.A 表格法介紹 - 第一步（Bottom Up 第一列） | 物體/重量/價值 |0|10|20|30|40|50| |:-----------------------------:|:--------------:|:------------:|:-------------:|:--------:|:---------:|:---------:| | A / 10g / $60 |0|60|60|60|60|60| **==我們只有一個 A 物體，因此不論袋子是否裝滿，都是 Value 60==** ---- # 動態規劃 Bottom Up A.K.A 表格法介紹 - 第二步（Bottom Up 第二列） | 物體/重量/價值 |0|10|20|30|40|50| |:-----------------------------:|:--------------:|:------------:|:-------------:|:--------:|:---------:|:---------:| | A / 10g / $60 |0|60|60|60|60|60| | ==B / 20g / $100==|==0==|==60==|==100==|==160==|==160==|==160==| 基本概念： **==T[i][j]= max(T[i – 1][j], V[i]+T[i – 1][j – W[i]])==** ---- # 動態規劃 Bottom Up A.K.A 表格法介紹 - 第三步（Bottom Up 第三列） | 物體/重量/價值 |0|10|20|30|40|50| |:-----------------------------:|:--------------:|:------------:|:-------------:|:--------:|:---------:|:---------:| | B / 20g / $100 |0|60|100|160|160|160| | ==C / 30g / $120== |==0==|==60==|==100==|==160==|==180==|==220==| 基本概念： **==T[i][j]= max(T[i – 1][j], V[i]+T[i – 1][j – W[i]])==** ---- # 動態規劃 題目練習及討論 - [東東爬階梯](https://zerojudge.tw/ShowProblem?problemid=d212) - [DELIVERY DEBACLE](https://zerojudge.tw/ShowProblem?problemid=d054) - [擺花](https://zerojudge.tw/ShowProblem?problemid=a697) - [傳球遊戲](https://zerojudge.tw/ShowProblem?problemid=d105) ---- # 動態規劃 - 相關範例（外國資訊練習教學網站）：[連結](https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/) - 如何建表格：[連結](https://www.youtube.com/watch?v=8LusJS5-AGo) --- # 樹的基本介紹 定義 **==沒有環的連通圖==**  ---- # 樹的基本介紹 樹種及名詞介紹  ---- # 樹的基本介紹 樹種及名詞介紹 - 節點(node) - 邊(edge) - 根節點(root) - 葉節點(leaf) - 層(level) - 深度(depth) ---- # 樹的基本介紹 樹種及名詞介紹 - 父節點(parent) - 子結點(child) - 祖先(ancestor) - 子代(descendant) - 子樹(subtree) ---- # 樹的基本介紹 樹種及名詞介紹 - **==二元樹==** - **==Binary Search Tree==** - **==Heap Tree==** - **==平衡樹==** - AVL Tree - 紅黑樹 - [其他樹種及應用（未來有機會會補充）](https://docs.google.com/document/d/1wZ8qZI8KG0FWkLTlGmy4vB7tgKD_IG1fOsc-GV302Ug/edit#heading=h.11lxn6bs6vmp) ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹 - 每個節點最多只有兩個子節點 - 第 k 層最多有 2**k 個節點 - 一棵深度為k的二元樹最多有 2**(k+1)-1 個節點 - 遍歷：前序、中序、後序  ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹  - 遍歷：前序 ```graphviz digraph hierarchy { rankdir = LR nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 訪問根節點 -> 訪問左子樹 -> 訪問右子樹 } ``` 上圖的走訪順序為：ABDECFG ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹  - 遍歷：中序 ```graphviz digraph hierarchy { rankdir = LR nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 訪問左子樹 -> 訪問根節點 -> 訪問右子樹 } ``` 上圖的走訪順序為：DBEAFCG ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹  - 遍歷：後序 ```graphviz digraph hierarchy { rankdir = LR nodesep=1.0 node [fontname=Courier,shape=box,fontsize=20] edge [color=Blue, style=dashed] 訪問左子樹 -> 訪問右子樹 -> 訪問根節點 } ``` 上圖的走訪順序為：DEBFGCA ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹 - 又分為 Full（Perfect） Binary Tree 和 Complete binary tree |樹種|Full Binary|Complete binary| |:-------:|:-----:|:------:| |圖示||| ---- # 樹的基本介紹 各種樹種的基本運作 - 二元樹 - 針對 Complete binary tree 介紹 - 除了最後一層，每一層都是填滿的 - 最後一層的元素盡量往左靠 - 編號為 k 的兩個孩子編號分別為 2k 和 2k+1 - 編號為 k 的父親編號為 [k/2] - 一個有 n 個元素的 complete binary tree 的深度約為 log(n) ---- # 樹的基本介紹 各種樹種的基本運作 - Binary Search Tree 之重點 - 任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值，反之亦然。 - 任意節點的左、右子樹也是二元搜尋樹 - 編號為 k 的父親編號為 [k/2] - 沒有鍵值相等的節點 ---- # 樹的基本介紹 各種樹種的基本運作 - Binary Search Tree 之資料管理 [[其他清楚教學](http://alrightchiu.github.io/SecondRound/binary-search-tree-sortpai-xu-deleteshan-chu-zi-liao.html)] {%pdf https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week02/tree_inclass.pdf %} ---- # 樹的基本介紹 各種樹種的基本運作 - Heap Tree - 一棵complete binary tree，又分為 Max Heap 和 Min Heap - **==父節點的權重不小於子節點的權重==**  ---- # 樹的基本介紹 各種樹種的基本運作 - Heap Tree - 資料運作 [[其他清楚教學](http://alrightchiu.github.io/SecondRound/comparison-sort-heap-sortdui-ji-pai-xu-fa.html)] {%pdf https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week04/heap.pdf %} ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 - 又稱為自平衡二元搜尋樹 (Self-Balancing Binary Search Tree)，目的是為了避免極端測資 - 以下僅先介紹 **==AVL 樹==**，之後慢慢帶入[紅黑樹](https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91)、[伸展樹](https://zh.wikipedia.org/wiki/%E4%BC%B8%E5%B1%95%E6%A0%91)...等樹種 （有興趣可先閱讀，之後可一起討論！） ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 之 **==AVL 樹==** 介紹：(Content Credit : [Link](https://www.notes-hz.com/blog?id=128)) - BST 的改良版 - 在節點中加入平衡因子，通常是節點的兩棵子樹高度差。 **==當平衡因子為 -1、0、1 時 ， 樹是「平衡」的==** - 當這棵樹因為插入或刪除操作失衡時，AVL 樹利用「**==樹旋轉==**」的操作來回復平衡狀態。 ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 之 **==AVL 樹==** 介紹： - 平衡因子（BF）計算 - 左子樹的高度 - 右子樹的高度 - 當大於2時，則需要進行旋轉，**==共有四種旋轉方式：LL、RR、LR、RL==**  ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 之 **==AVL 樹==** 介紹： - 旋轉條件： _**==若有一加入的新節點為N，若一距離N最近且平衡因子為+-2的父節點P存在，則四種調整方式的適用時機如下==**_ ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 之 **==AVL 樹==** 介紹： - 旋轉條件：（ 依序為 **==LL / RR / LR / RL==** ） - 當加入的節點N在節點P的左邊的左邊 - 當加入的節點N在節點P的右邊的右邊 - 當加入的節點N在節點P的左邊的右邊 - 當加入的節點N在節點P的右邊的左邊 ---- # 樹的基本介紹 各種樹種的基本運作 - 平衡樹 之 **==AVL 樹==** 介紹：(Content Credit : [Link](https://www.notes-hz.com/blog?id=128)) - 旋轉條件：（ 依序為 **==LL / RR / LR / RL==** ） <iframe src="https://onedrive.live.com/embed?cid=F704F1841E606902&resid=F704F1841E606902%2117564&authkey=APKKe-t1bJqptJM&em=2" width="750" height="300" frameborder="0" scrolling="no"></iframe> ---- # 樹的基本介紹 題目練習及討論（課堂討論；回家練習） * [北一女：Heap 學習單](http://web.fg.tp.edu.tw/~tfgcsblog/blog/wp-content/uploads/2016/07/05_Heap%E5%AD%B8%E7%BF%92%E5%96%AE.pdf) * Zerojudge： * [通關密語](https://zerojudge.tw/ShowProblem?problemid=d432) * [合併果子](https://zerojudge.tw/ShowProblem?problemid=b151) * [黑暗部落](https://zerojudge.tw/ShowProblem?problemid=d808) * [垃圾信件](https://zerojudge.tw/ShowProblem?problemid=d449) * [Binary Search Tree (BST)](https://zerojudge.tw/ShowProblem?problemid=d526) --- END ---