Please enable JavaScript.
Coggle requires JavaScript to display documents.
(Binary Tree (Binary Tree的表示方法 (空間需求比較 - 隨node數 (Array : 指數成長, Linked List…
Binary Tree
Binary Tree的表示方法
Array
arr[0]不存資料。若n為BT的節點，則陣列大小必須為
min : n+1 (full BT)
MAX : 2^n (斜曲)
Linked List
空間需求
node數*每一個node所需要的空間
空間需求比較 - 隨node數
Array :
指數
成長
Linked List :
線性
成長
Binary Tree的性質
樹高h的樹
min子點數 : h
MAX子點數 : 2^h-1
若有n個點
樹高MAX : n
樹高min : log2(n+1)
Binary Tree的 Traversal
BT的operations大多都是透過traversal來實現
Traversal Method
Non-level order
Preorder : DLR
Inorder : LDR
Postoder : LRD
Level order : 由上而下，由左而右
Binary Tree的應用
Priority queue (可用tree實作)
opreartions
新增 : 將元素依照相關優先權插入到queue當中
刪除 : 將
最高
優先權的元素刪除，並回傳其值
可用來實作Priority Queues的資料結構
Unordered linked list
Unordered array
Sorted linked list
Sorted array
Heap
說明 : 一種建立於tree的資料結構
性質 : 子點的值必大、小、等於父點的值
不同的資料結構，不同的operation時間複雜度
Unordered linked list
插入 : Θ(1)
刪除 : Θ(n)
Unordered array
插入 : Θ(1)
刪除 : Θ(n)
Sorted array
插入 : O(n)
刪除 : Θ(1)
Sorted list
插入 : O(n)
刪除 : Θ(1)
Max Heap (complete binary tree)
插入 : Ο(log2n)
刪除 : Ο(log2n)
應用
Sorting
方法 : 把元素放進priorirt queue中依序pop，再依序放入陣列
時間複雜度: 排n個元素 -> O(nlogn)
說明
(1)放入一個元素到priority queue當中，重複n次 -> O(log n)*n = O ( n log n )
(2)把元素從priority queue中依序pop，存入陣列中，重複n次 -> O(log n)*n = O ( n log n )
Total : O(n log n) + O(n log n) => O(n log n)
比較 : 插入排序法O(n^2)
Priority queue (可用tree實作)
Priority queue (可用tree實作)
opreartions
新增 : 將元素依照相關優先權插入到queue當中
刪除 : 將
最高
優先權的元素刪除，並回傳其值
可用來實作Priority Queues的資料結構
Unordered linked list
Unordered array
Sorted linked list
Sorted array
Heap
說明 : 一種建立於tree的資料結構
性質 : 子點的值必大、小、等於父點的值
時間複雜度
說明 : 不同的資料結構，不同的operation時間複雜度
Unordered linked list
插入 : Θ(1)
刪除 : Θ(n)
Unordered array
插入 : Θ(1)
刪除 : Θ(n)
Sorted array
插入 : O(n)
刪除 : Θ(1)
Sorted list
插入 : O(n)
刪除 : Θ(1)
Max Heap (complete binary tree)
插入 : Ο(log2n)
刪除 : Ο(log2n)
應用
Sorting
方法 : 把元素放進priorirt queue中依序pop，再依序放入陣列
時間複雜度: 排n個元素 -> O(nlogn)
說明
(1)放入一個元素到priority queue當中，重複n次 -> O(log n)*n = O ( n log n )
(2)把元素從priority queue中依序pop，存入陣列中，重複n次 -> O(log n)*n = O ( n log n )
Total : O(n log n) + O(n log n) => O(n log n)
比較 : 插入排序法O(n^2)
重點考題
中序式轉後序式
postfix的Stack畫法
表達式的binary tree form
Huffman要會畫
三種表達式
Postfix
operator在operand的
前面
中序轉前序
(1)先對infix加上完整的括號配對，base on 優先權、結合性
(2)operator取代最近的左括號
(3)刪除右括號，其餘由左而右依序寫出
Prefix
operator在operand的
後面
中序轉後序
(1)先對infix加上完整的括號配對，base on 優先權、結合性
(2)operator取代最近的右括號
(3)刪除左括號，其餘由左而右依序寫出
Infix
人類熟悉，但對電腦來說不好處理
Heap
opeartions
插入
方法
(1)新建一個node，把要插入的data丟進去
(2)向上挑戰，若成功，就交換
時間複雜度
O( log n )
說明 : 最高交換次數為樹高⎾log2(n+1)⏋ => O( log n )
刪除
方法
(1)把root清空
(2)把least node移到root，並逐漸向下調整
時間複雜度
O( log n )
說明 : 一種建立於tree的資料結構
性質 : 子點的值必大、小、等於父點的值
為何要有Tree?
改良線性陣列，使程式編寫更容易。
通常使用
Linked List
實作
Linear List 與Tree的比較
Linear lists : 適合
連續排列
的data
Trees : 適合
階層式
的data
Binary Search Tree 與 Heap的比較
Heap
插入 : O(log2n) -> 棒
搜尋 : O( n ) -> 不適合用來做search
BST
搜尋 : O(h) -> 樹高
Binary Search Tree
opeartions
刪除
Leaf : 直接刪除
Degree-1 : 上下連結砍掉，直接接起來
Degree-2
(1)令要刪除的node位置(X)、左子樹的最大值或右子樹的最小值的位置(y)。將y中的值放到X中
(2)依照y的degree下去進行y的刪除
應用
Huffman Code
N-ary Tree
令一個節點集合T
1.為空
2.含有N個不同的N-ary trees