Please enable JavaScript.
Coggle requires JavaScript to display documents.
CH5 (Binary Tree (Binary Tree的表示方法 (空間需求比較 - 隨node數 (Array : 指數成長, Linked…
CH5
Binary Tree
Binary Tree的性質
樹高h的樹
min子點數 : h
MAX子點數 : 2^h-1
若有n個點
樹高MAX : n
樹高min : log2(n+1)
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的 Traversal
BT的operations大多都是透過traversal來實現
Traversal Method
Non-level order
Preorder : DLR => 可得到prefix的數學表達式
Inorder : LDR => 可得到infix的數學表達式
Postoder : LRD => 可得到postfix的數學表達式
Level order : 由上而下,由左而右
Binary Tree的應用
Priority queue (可用tree實作)
opreartions
新增 : 將元素依照相關優先權插入到queue當中
刪除 : 將
最高(低)
優先權的元素刪除,並回傳其值
時間複雜度
Unordered linked list
插入 : Θ(1)
刪除 : Θ(n)
Unordered array
插入 : Θ(1)
刪除 : Θ(n)
Sorted array
插入 : O(n)
刪除 : Θ(1)
Sorted list
插入 : O(n)
刪除 : Θ(1)
Max Heap
插入 : Ο(log n)
刪除 : Ο(log n)
Priority Queue的排序方法
Heapsort : 用heap實作 priority queue
Selection sort : 用ordered array實作 priority queue
insertion sort : 用unordered array實作 priority queue
應用
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的資料結構,為complete binary tree
性質 : 子點的值必大(或小於)父點的值
Forest
定義
有 >=0 顆disjoint tree
Tree化BT
步驟
(1)建立sibling間的平行link
(2)刪除父與子之link,但保留leftmost-child-linked
(3)順時針轉45度(保留leftmost-child當左子點,次右兄弟作為右子點)
Forest化BT
步驟
(1)將森林中每顆樹都化成BT
(2)將各個BT的root視為sibling,平行串聯
(3)針對root,次右兄弟轉成右子點
為何要有Tree?
改良線性陣列,使程式編寫更容易。
通常使用
Linked List
實作
Linear List 與Tree的比較
Linear lists : 適合
連續排列
的data
Trees : 適合
階層式
的data
Binary Search Tree 與 Heap的比較
Heap
插入/刪除 : O(log 2 n) -> 棒
搜尋 : O( n ) -> 不適合用來做search
BST
搜尋 : O(h) -> 樹高
N-ary Tree (多元樹 - 分N岔的樹)
令一個節點集合T
1.為空
2.含有N個不同的N-ary trees
Binary Search Tree
opeartions
刪除
Leaf : 直接刪除
Degree-1 : 上下連結砍掉,直接接起來
Degree-2
(1)令要刪除的node位置(X)、左子樹的最大值或右子樹的最小值的位置(y)。將y中的值放到X中
(2)依照y的degree下去進行y的刪除
Tree應用
Huffman Code