Chapter 5 樹狀結構.

Slides:



Advertisements
Similar presentations
1 第八章 深入探討樹狀結構. 2 目次 8.1 m-way 搜尋樹 8.2 B-tree 8.3 動動腦時間 8.4 練習題解答.
Advertisements

第7章 樹與二元樹 (Trees and Binary Trees)
資料結構 老師:李崇明 助教:楊斯竣.
Tree (2): heap, deap, 2-3 tree, 2-3-4tree
演算法 陣列 鏈結串列 堆疊與佇列 樹狀結構 搜尋
資料結構(計財系).
計算機概論 第五章 資料結構 陳維魁/陳邦治 旗標出版社.
Chapter 6 樹狀結構.
新世代計算機概論 第15章 資料結構.
樣本空間與事件 餘事件:不在A中的樣本所構成的事件,即A′.
计算机软件技术基础 数据结构与算法(4).
第三节 树与二叉树 树的基本概念: 前面我们讨论的线性表,栈、队列和数组等都是线性结构。而树是一种非线性数据结构,它的每一个结点,都可以有不止一个直接后继,除根外的所有结点,都有且只有一个直接前趋。这些数据结点按分支关系组织起,清晰地反映了数据元素之间的层次关系。
第5章 树( Tree )和二叉树 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林
Chap4 Tree.
Chap5 Graph.
資料結構 第3章 鏈結串列.
資料結構設計與C++程式應用 Fundamentals of Data Structures and Their Applications Using C++ 第3章 佇列 資料結構設計與C++程式應用.
第11章 資料結構 – 使用C語言的模組 11-1 資料結構的基礎 11-2 C語言的模組化程式設計 11-3 基本鏈結串列
第7章 樹與二元樹 (Trees and Binary Trees)
Course 0 課程介紹 Introduction
樹狀結構 Trees.
第七章 AVL搜尋樹 二元搜尋樹簡單易懂,不過有一個問題:它並非平衡樹。本章將介紹平衡的 AVL 搜尋樹,討論它的資料結構、函式,並設計程式使用它。
資料結構與C++程式設計進階 鏈結串列 講師:林業峻 CSIE, NTU 6/ 10, 2010.
資料結構 第6章 樹狀結構.
(Circular Linked Lists)
第 七 章 樹狀結構 課程名稱:資料結構 授課老師:________ 2019/1/1.
資料結構–樹(Tree) 綠園.
4.1 單向鏈結串列 4.2 堆疊的加入與刪除 4.3 佇列的加入與刪除 4.4 其他型式的佇列
鄧姚文 資料結構 第六章:樹(Tree) 鄧姚文
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
Chap3 Linked List 鏈結串列.
Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree.
第六章 樹狀結構 T r e e 版權屬作者所有,非經作者 同意不得用於教學以外用途.
Ch 3 Dynamic Programming (動態規劃).
2-3-4 Tree and how it relates to Red Black Tree
Chap4 Tree.
Tree & Binary Tree.
資料結構 7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構.
資料結構使用Java 樹(Tree).
Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
Definition of Trace Function
BC430 ABAP Dictionary Views、 Search Help 報告者:林聖期、程汎汝.
小學四年級數學科 8.最大公因數.
第7章 樹與二元樹(Trees and Binary Trees)
挑戰C++程式語言 ──第8章 進一步談字元與字串
圓的定義 在平面上,與一定點等距的所有點所形成的圖形稱為圓。定點稱為圓心,圓心至圓上任意一點的距離稱為半徑,「圓」指的是曲線部分的圖形,故圓心並不在圓上.
資料結構與C++程式設計進階 樹狀結構(Tree) 講師:林業峻 CSIE, NTU 11/ 12, 2009.
第 八 章 高等樹 課程名稱:資料結構 授課老師:________ 2019/4/28.
資料結構使用Java 第9章 樹(Tree).
Chapter 6 樹狀結構.
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
資料結構使用Java 第6章 鏈結串列(Linked List).
流程控制:Switch-Case 94學年度第一學期‧資訊教育 東海大學物理系.
第六章 二元搜尋樹 現在我們的注意焦點要轉到搜尋樹(search tree)了,要深度討論兩種標準的樹結構(tree structure),就是本章所要說明的二元搜尋樹(binary search tree)以及下一章所要討論的 AVL 平衡樹(AVL tree)。這兩種樹其資料都依序排列的,它們之間的差別只在於.
二項分配-Binomial 伯努利試驗(Bernoulli Trial) 每一次試驗皆僅有兩種可能結果,不是成功(S),就是失敗(F)。
動畫演示 Node規範了一些基本的方法,像是增加節點、刪除節點、讓節點做一些事、取得第n個節點等等
6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題
第7章 資料結構 7-1 陣列 7-2 鏈結串列 7-3 堆疊和佇列 7-4 樹狀結構.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
第一節 餐飲服務的定義及範圍 4-2 鋸條的種類、用途與規則 一. 鋸條規格 二. 鋸條的種類 三. 鋸條的用途.
堆積(Heap Tree) 授課老師:蕭志明.
第四組 停車場搜尋系統 第四組 溫允中 陳欣暉 蕭積遠 李雅俐.
10791: Minimum Sum LCM ★★★☆☆ 題組:Problem Set Archive with Online Judge
Trees 授課者:驕芸.
10303: How Many Trees? ★★☆☆☆ 題組:Contest Archive with Online Judge
第10章 二元搜尋樹 (Binary Search Tree)
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
第一章 直角坐標系 1-2 距離公式、分點坐標.
Presentation transcript:

Chapter 5 樹狀結構

樹狀結構包含:樹根(root)、節點(node)、樹葉(leaf) 樹狀結構 - 定義 樹狀結構包含:樹根(root)、節點(node)、樹葉(leaf) A為樹根,分別與B、C、D相連接。從A到L稱為節點,共有11個節點。

每個節點都有父節點(樹根除外) 每個節點的下一個節點稱為子節點 同一個高度的節點稱為兄弟節點 尾端的樹葉稱為外部節點或終端節點 一棵樹除了樹葉外其餘為內部節點或非終端節點。 去除樹根,其餘稱為子樹,這些子樹構成一個”森林”,一個節點擁有的子樹數目稱為”分支度”。

樹狀結構-階度(高度) 像是人類的族譜,祖父母到孫子一共三代;在樹狀結構是以「階度、高度」來表示

樹狀結構 - 樹的串列表示法 樹狀結構的串列表示法: (A(B(E,F),C,D(G(K),H,I(L)))) 樹的記憶體表示法: data 樹狀結構 - 樹的串列表示法 樹狀結構的串列表示法: (A(B(E,F),C,D(G(K),H,I(L)))) 樹的記憶體表示法: data link dlink rlink

(A(B(E,F),C,D(G(K),H,I(L)))) 一般化串列節點結構表示法: (A(B(E,F),C,D(G(K),H,I(L)))) Tag Data Link

樹狀結構 - 二元樹(Binary Tree) 樹狀結構每個節點的分支度沒有固定,處理不便。 二元樹為一個樹根與兩個以下的分支所構成的樹狀結構,二元樹的節點結構為 二元樹的分支度為一左一右,左子樹與右子樹。順序上通常小的置於左子樹,大的置於右子樹,因此二元樹又稱為有序樹。 Llink Data Rlink

樹與二元樹: 樹的子樹之間沒有順序關係,二元樹有。 樹至少要有一個樹根,不可以為空集合,二元樹可以。 樹的分支度大於等於 0,而二元樹的分支度小於等於 2 及大於等於 0。

樹狀結構-二元樹的特性 高度為1,節點只有樹根A,節點數為1;高度為2,節點數為3(A,B,C);高度為3,節點數為7(A,B,C,D,E,F,G)。以此類推,高度為n,最大節點數為2n-1,數學式為:20+21+22+23+…+2n-1=(2n-1)/(2-1)=2n-1 第一高度有一個節點(A),第二高度有二個節點(B,C),第三高度有四個節點(D,E,F,G),則第m高度的節點數目最多有2m-1個。 樹葉總數等於分支度2的節點總數加一。

結論: 例題 page174 高度為n的二元樹,其最大的節點數為2n-1 高度為n的二元樹,第m高度的節點樹目最多有2m-1個(其中n≧m) 非空的二元樹,若樹葉總數為n0,且分支度2的節點總數為n2,則n0=n2+1 例題 page174

樹狀結構-歪斜樹(Skewed Tree) 當二元樹只有在左邊的節點上或是只有在右邊的節點上,稱為歪斜樹。只有左子樹,稱為左歪斜樹;只有右子樹,稱為右歪斜樹。

樹狀結構-完整二元樹(Complete Binary Tree) 若二元樹的高度為n,節點依出現順序排成二元樹,且節點總數≦2n-1,此種二元樹稱為完整二元樹。若節點總數為m,則此完整二元樹的高度為log2m +1。 上圖完整二元樹m=10個節點,log210 +1=4.32,取整數4 非完整二元樹?如:少F或G

樹狀結構-完滿二元樹(Full Binary Tree) 若二元樹的高度為n,節點依出現順序排成二元樹,而且節點總數等於 2n-1,此種二元樹稱為完滿二元樹。若二元樹為完滿二元樹,節點總數為m,則此完滿二元樹的高度為log2(m+1)。 節點總數滿足log2(m+1)等於整數為完滿二元樹,否則為非完滿二元樹。該整數即為二元樹高度。 例題 page177

樹狀結構-二元樹的儲存表示法 二元樹儲存方式可用陣列和鏈結串列來表示。 循序陣列表示法: 將二元樹視為一個完滿二元樹,依節點的階度依序存放入記憶體內。 節點 1 2 3 4 5 6 7 8 9 10 11 鍵值 A B C D E F G H I J K Level 1 Level 2 Level 3 Level 4

二元樹的儲存表示法 二元樹若為完整或完滿二元樹,則使用陣列表示法將有效節省空間;否則將浪費記憶體空間。 圖5-12 E D F 節點 1 2 3 4 5 6 7 8 9 10 11 鍵值 A B C D E F Level 1 Level 2 Level 3 Level 4

二元搜尋樹(binary search tree)為二元樹,具下列性質: 左子樹節點的值小於(≦)根節點的值 右子樹節點的值大於(≧)根節點的值 左、右子樹仍為二元搜尋樹 例題 ko5_1

樹狀結構-二元樹的儲存表示法 鏈結串列表示法: 陣列表示法較鏈結串列表示法浪費記憶體空間。 例題 ko5_2,例題page 184, 185 F C B E D A B C D E F

樹狀結構-二元樹的追蹤 二元樹的追蹤就是拜訪二元樹的每一個節點。 假設L、D、R分別代表節點的左子樹、資料、右子樹,依據二元樹由左而右追蹤的特性,會有三種情況:LDR(中序追蹤 inorder traversal)、LRD(後序追蹤 postorder traversal)、DLR(前序追蹤 preorder traversal)。 Llink Data Rlink

樹狀結構-二元樹的追蹤 中序追蹤(LDR) 指拜訪二元樹節點的順序為左子樹→樹根節點→右子樹(樹根在拜訪二元樹節點的過程置於中間)。 中序追蹤是由左子樹→樹根→右子樹 D→B→E→A→F→C 例題 ko5_3 (中序追蹤)

樹狀結構-二元樹的追蹤 後序追蹤(LRD) 指拜訪二元樹的順序為左子樹→右子樹→樹根節點(樹根在拜訪二元樹節點的過程置於最後)。 後序追蹤是由左子樹→右子樹→樹根 D→E→B→F→C→A 例題 ko5_4 (後序追蹤)

樹狀結構-二元樹的追蹤 前序追蹤(DLR) 指拜訪二元樹節點的順序為樹根節點→左子樹→右子樹(樹根在拜訪二元樹節點的過程置於最前面) 前序追蹤是由樹根→左子樹→右子樹 A→B→D→E→C→F 例題 ko5_5 (前序追蹤),PAGE193~196

樹狀結構-引線二元樹 Fig5-23(Page 196) 充分使用沒有被使用的鏈結欄,避免浪費,使其指向其他的節點。 指標的接法規則: 1.將所有的空鏈結改成指標引線。 2.若引線是從該節點的左子樹指向另一個節點時,此引線應指向中序追蹤的前一個節點。D----A 3.若引線是從該節點的右子樹指向另一個節點時,此引線應指向中序追蹤的後一個節點。F---C 中序追蹤 B—A—D—F—C—E See page 197~8 for example LBit LChild Data RChild RBit See Page 197、198

樹狀結構-樹的二元樹表示法 一般樹轉換成二元樹的方法: 1.將一般樹所有節點的鏈結刪除,但鏈結至最左子樹的鏈結除外。 2.將所有兄弟接點的鏈結在一起。 See fig 5-28 (page199) fig5-29(a)、(b)、(c) 森林轉換成二元樹的方法: 1.將各樹的樹根從左至右連結起來。 2.再以一般樹轉換成二元樹的方法的方法,即可完成森林轉換成二元樹。 See fig 5-30 (page200) fig5-31(a)、(b)、(c)、(d) See例題page202、203

樹狀結構-二元樹的計數 二元樹的計數在於討論n個節點可以排成幾種不同的二元樹: 1.n=1,有一種不同的排列。 n=p,有 種不同的排列。 例題(page204)

樹狀結構-樹的種類 以下是樹的種類:二元搜尋樹、延伸二元樹、最小加權外路徑長度二元樹、解碼樹、最佳二元搜尋樹、平衡樹、累堆樹、決策樹、選擇樹、輸家樹、遊戲樹、B 樹 二元搜尋樹 二元搜尋樹必須合乎下列條件: 若存在左子樹時,其鍵值須小於樹根的鍵值。 若存在右子樹時,其鍵值須大於樹根的鍵值。 Fig5-33 (page 205) {28, 24, 46, 59, 26, 40, 19, 40*} STEPS see page 205 若一組鍵值中有兩個以上的鍵值相同,後面的鍵值比前面的鍵值大。

樹狀結構-樹的種類 二元搜尋樹插入元素 二元搜尋樹插入元素是在已存在的二元搜尋樹內,插入某一個元素,其插入的結果還是要符合二元搜尋樹的條件。如前例中加入鍵值30,see Fig 5-35 (page 207)。 刪除二元搜尋樹的元素 二元搜尋樹的元素刪除後,也不可以失去二元搜尋樹的特性。刪除方法如下: Ψ 如果是樹葉的鍵值直接刪除。 Ψ如果刪除非樹葉的鍵值,先從其右子樹找出大於且 最接近次鍵值來取代它,然後,刪除此鍵值。 Ψ如前例中刪除鍵值40、28,see Fig 5-36 (page 208)。

樹狀結構-樹的種類 延伸二元樹 指任何一個二元樹,若有n個節點,具有n-1個非空鏈結,n+1個空鏈結, 若在每一個空鏈結上加入一個特殊的節點,稱此節點為外節點,其餘節點為內節點。See Fig 5-37 (page 209) 如此利用內、外節點建立的二元樹,稱為延伸二元樹。用於搜尋時,搜尋到外節點,代表搜尋失敗。 節點長度為樹根至節點的分支數 Fig 5-37內節點長度I、外節點長度E I=0+1+1+2+2=6 E=3+3+3+3+2+2=16 E=I+2n n為延伸二元樹的節點數 歪斜二元樹I、E值最大,完整二元樹I、E值最小

樹的種類 最小加權外路徑長度二元樹 加權代表兩個節點間的距離或價錢。 外長度路徑是指由樹根到每個外節點的路徑長度之總和;內路徑長度是指由樹根到每個內節點的路徑長度之總和。 假設有n個節點,每個外節點(長度或距離為k)均設有一加權數q,則此二元樹的加權外路徑長度等於: see Fig5-38(page 210) Huffman碼see Fig5-3 (page 210) Huffman解碼樹:see page 211~213 & 例題@page 213 最佳二元搜尋樹:指所有二元搜尋樹中具備有最小加權外路徑長度的二元樹。

樹狀結構-樹的種類 平衡樹 AVL樹必須合乎下列的條件: AVL樹進行插入或刪除後,高度須平衡。如不平衡可用LL、RR、LR、RL型(see page 215~6)旋轉成平衡。 將串列鏈結二元樹8-2-3-7-4-1-6-5轉成平衡二元樹。 See Fig 5-43 (page 216~7)

平衡樹 n層平衡樹最少節點數: 平衡二元樹 例題 page 219~221 n層最少節點數= n-1層最少節點數+ n-2層最少節點數+1 1層 :1個(root) 2層 : 2個 3層 : 4個 4層 : 7個 平衡二元樹 n層最少節點數= n-1層最少節點數+ n-2層最少節點數+1 例題 page 219~221

樹狀結構-樹的種類 累堆樹 累堆樹又稱為最大累堆樹。 最小累堆樹 累堆樹是一個完整二元樹。 每個節點之鍵值必須大於其子節點之鍵值。 累堆樹的樹根之鍵值是最大的。 累堆樹又稱為最大累堆樹。 最小累堆樹 每個節點之鍵值必須小於其子節點之鍵值,而且樹根之鍵值是最小的,這種累堆樹稱為最小累堆樹。 串列鏈結二元樹45、83、7、61、12、99、44、77、14、29轉換成最大累堆樹:see page 221~2。 例題page 223~225。 相同串列鏈結二元樹轉換成最小累堆樹see page 225~6。例題page 227。

樹的種類 最小-最大累堆樹 若有一個完整二元樹,此二元樹交互階度分別為最小階度及最大階度,其中樹根為最小鍵值。 建立最小-最大累堆樹的原則是:各(子)樹 階度1的鍵值<階度3的鍵值<階度5的鍵值………. 階度2的鍵值>階度4的鍵值>階度6的鍵值………. See Fig5-57~8 (page 228) 例題 page 228~230

樹狀結構-樹的種類 雙累堆樹 雙累堆樹是一個完整二元樹。 雙累堆樹的樹根不包含任何元素。 雙累堆樹的左子樹為一個最小累堆樹。 雙累堆樹的右子樹為一個最大累堆樹。 左子樹節點鍵值必須小於或等於對應右子樹節點鍵值。 例題 page 231~3

樹狀結構-樹的種類 決策樹 決策樹是從八個錢幣找出偽幣的問題。 假設有八枚硬幣,其中有一枚與其他七枚重量不同,因為他是偽造的,現在利用一個等臂天平將偽幣找出,希望以最少比較次數,找出偽幣。將一連串比較的可能結果列出一樹狀結構,此樹狀結構稱為決策樹。 例題 ko5_6 (決策樹) 選擇樹 輸家樹 遊戲樹 通常用於#字遊戲、圍棋、象棋、黑白棋、NXN陣列的棋子等等。

樹狀結構-樹的種類 B樹 m-路搜尋樹 二元搜尋樹節點最多有2個子樹,而m-路搜尋樹節點最多有m個子樹,此兩種搜尋樹用於I/O資料存取的次數,有截然不同的結果 m-路搜尋樹用於I/O資料存取的次數比二元搜尋樹的次數減少許多。

B樹 m-路搜尋樹是指一棵樹的根節點最多有m個子樹,具有下列性質: 節點的結構為: n, A0,(K1, A1), (K2, A2),…,(Kn, An) 其中Ai,0≦i≦n是指向m-路搜尋樹子樹的指標,且Ki,1≦i≦n為m-路搜尋樹的鍵值。 節點的鍵值是由小而大排列的。 Ai所有的鍵值小於Ki+1 An所有的鍵值大於Kn。 所有的子樹Ai,0≦i≦n也是m-路搜尋樹。 See Fig 5-74(page 242) 3-路搜尋樹

B樹 B樹 B樹是指度數(order)為m的m-路搜尋樹。有如下特性: 根節點至少有兩個子樹節點 每一節點的分支度≦m 非終端節點(樹根除外)每一節點所含的節點數為n,則m/2≦n≦m 所有樹葉節點都在同一層 高度為h,order為m的B樹,最多有(mh-1)/(m-1)個節點數,最多有mh-1個鍵值數 2-3樹、 2-3-4樹 see Fig 5-75, Fig 5-76 (page243)

B樹 B樹鍵值的插入 通常一個鍵值插入到B樹,須找到該鍵值的適當位置,此適當位置不會因加入某一鍵值後,而形成該節點鍵值爆滿,即可將此鍵值插入到此節點內。 如果加入鍵值後而形成節點鍵值爆滿,須將此節點一分為二,同時將鍵值Km/2提升到其父節點上,若因鍵值Km/2提升到其父節點上,直到上述情況不再發生為止。 Fig 5-75 B樹中插入15成Fig 5-77 Fig 5-75 B樹中插入30成Fig 5-78修改後成Fig 5-79 例題see page245~7

B樹 B樹鍵值的刪除 在B樹中欲刪除某一鍵值p,先找出其位置,其次再判斷此鍵值所在位置的節點是否為終端節點。 鍵值所在位置的節點為終端節點 刪除後,節點內尚有其他鍵值see page 248 (a) (b) 鍵值所在位置的節點不為終端節點 刪除後,尋找其右節點的所有鍵值中最小者取代刪除鍵值。 刪除後,若鍵值數<(m/2)-1,必須回到先前步驟調整節點內的鍵值 例題see page248~251

樹狀結構-樹的種類 B樹的搜尋 若x為欲搜尋的鍵值,在B樹的節點找到一個i值,滿足Ki≦x<Ki+1,則: 如果x> Ki ,則繼續搜尋Ai指向的節點。 如果x= Ki ,表示找到搜尋值。 如果Ai=0,表示沒有找到搜尋值,搜尋失敗。

樹狀結構-集合的表示法 森林所代表的集合是互斥的 如上圖一共有九個元素存在四顆子樹內,而構成一座森林,子樹與子樹之間彼此沒有任何關係,換言之,九個元素形成四個互斥的集合S1.S2.S3.S4。每一個集合的內容:S1={A.B.C}、S2={D.E}、S3={F.G.H}、S4={I}

樹狀結構-樹的種類 S1∪S2∪S3∪S4={A.B.C.D.E.F.G.H.I} 以A為樹根的聯集表示法如下: