Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree.

Slides:



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

會計學 Chapter 1 基本概念 1-2 基本概念 第一節 單式簿記 第二節 會計學的定義與功用 第三節 會計學術與會計人員 第四節 企業組織 第五節 會計學基本第五節 會計學基本慣例 第六節 會計方程式 第七節 財務報表.
Chapter 5 教育發展與職業選擇. 1. 認識高職學生的生涯進路。 2. 了解個人特質與職業屬性之 間的關係。 3. 認識打工安全與勞動權益。
导 游 基 础 知 识.
传道书 12种虚空 9处不可知 23样价值观 7个小结论 人生是虚空的虚空! (没有神的人生)
報告書名:父母會傷人 班級:二技幼四甲 姓名:吳婉如 學號:1A2I0034 指導老師:高家斌
小 王 子 組別:第五組 班級:財金二甲 組員:A 林安潔 A 陳思羽 A 許雅涵
11-1 保險業之定義 11-2 保險業之設立 11-3 保險業之組織 11-4 保險業之營業範圍
3/5/2017 十二经脉 八、足少阴肾经.
34 府学胡同的文天祥祠,相传是南宋民族英雄文天祥当年遭囚禁和就义的地方,1376年明洪武九年建祠 。
9-1 火災保險 9-2 海上保險 9-3 陸空保險 9-4 責任保險 9-5 保證保險 9-6 其他財產保險
媽,我們真的不一樣 青少年期與中年期 老師: 趙品淳老師 組員: 胡珮玟4A1I0006 馬菀謙4A1I0040
資料結構 老師:李崇明 助教:楊斯竣.
Tree (2): heap, deap, 2-3 tree, 2-3-4tree
Chapter 6 樹狀結構.
新世代計算機概論 第15章 資料結構.
外国小说话题突破系列之七 情感.
一般纳税人增值税 纳税申报表填写指引 白银高新区国税局 纳税服务科 2016年5月.
槍砲病菌與鋼鐵 第三組.
第7课 古罗马的政制与法律.
第二单元 商鞅变法 第1课 改革变法风潮与秦国历史机遇(背景) 第2课 “为秦开帝业”──商鞅变法(内容)
Chapter 5 樹狀結構.
高考文言文的整体阅读.
班級:二幼三甲 姓名:郭小瑄 、 詹淑評 學號:1A2I0029 、1A2I0025
導覽解說與環境教育 CHAPTER 3 解說員.
財務報表的內容 四種報表格式 財務報表的補充說明 會計師簽證的重要性 合併報表 財務報表分析 Chapter 2 財務報表的內容.
老師 製作 法律與生活.
指導老師:陳韻如 姓名:吳宜珊 學號:4A0I0911 班級:幼保二乙
第十七章休閒農業之經營策略與成功之道 17 Chapter.
Chapter 2 勞工安全衛生法.
傳統童玩遊戲創新 組別:第八組 班級:幼保二甲 組員: 4A0I0005柯舒涵 4A0I0011謝孟真
風險分析與財務結構 瞭解風險的定義與種類 衡量企業風險與財務風險 影響企業風險的因素 影響財務風險的因素 以現金流量衡量企業長期的財務狀況
國際行銷管理 林 建 煌 著.
第一節 知覺 第二節 認知 第三節 學習 第四節 創造力
CHAPTER 2 綜合所得稅之架構.
Chap5 Graph.
第7章 樹與二元樹 (Trees and Binary Trees)
樹狀結構 Trees.
資料結構 第6章 樹狀結構.
(Circular Linked Lists)
資料結構–樹(Tree) 綠園.
4.1 單向鏈結串列 4.2 堆疊的加入與刪除 4.3 佇列的加入與刪除 4.4 其他型式的佇列
鄧姚文 資料結構 第六章:樹(Tree) 鄧姚文
Chapter 9 高度平衡二元搜尋樹 AVL Binary Search Tree
樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.
Chap3 Linked List 鏈結串列.
Ch 3 Dynamic Programming (動態規劃).
Chap4 Tree.
資料結構使用Java 樹(Tree).
Reference to FUNDAMENTALS OF DATA STRUCTURE IN C++
Definition of Trace Function
老師 製作 休閒農場.
心理學—日常生活中的應用 人際溝通.
圓的定義 在平面上,與一定點等距的所有點所形成的圖形稱為圓。定點稱為圓心,圓心至圓上任意一點的距離稱為半徑,「圓」指的是曲線部分的圖形,故圓心並不在圓上.
資料結構與C++程式設計進階 樹狀結構(Tree) 講師:林業峻 CSIE, NTU 11/ 12, 2009.
第 八 章 高等樹 課程名稱:資料結構 授課老師:________ 2019/4/28.
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
唐常杰 四川大学计算机学院 计算机科学技术系
動畫演示 Node規範了一些基本的方法,像是增加節點、刪除節點、讓節點做一些事、取得第n個節點等等
6.1 樹狀結構的一些專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹的追蹤 6.5 引線二元樹 6.6 其它議題
財務預測 財務預測的用途 法令相關規定 預測的基本認知 預測的方法 製作預測性報表 財務報表分析 Chapter 16 財務預測.
本教學投影片係屬教科書著作之延伸,亦受著作權法之保護。
Parasitics Extraction (PEX) 與 postsimulation(posim)
有理数的乘方(二).
堆積(Heap Tree) 授課老師:蕭志明.
自慢 社長的成長學習筆記 何飛鵬.
Trees 授課者:驕芸.
團體工作的倫理議題 CHAPTER 12. 團體工作的倫理議題 CHAPTER 12 團體工作的倫理議題 1.如果我有資格執行個別治療,那麼我也可以執行團體治療。 2.仔細而審慎地篩選團體成員,較符合專業倫理要求。 3.在團體治療開始前,讓成員能先有準備以便從團體中獲得最大利益,是非常重要的。
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
Chapter1 大師的視界,見證歷史的腳步
Presentation transcript:

Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree

B-tree B-tree的功能非常強大,有許多資料庫系統皆採用B-tree來儲存與刪除其資料。

11.1 m-way搜尋樹 何謂m-waw搜尋樹(m-way search tree)? 一棵m-way搜尋樹,所有節點的分支度(dgree)均小於或等於m。若T為空樹,則T亦稱為m-way搜尋樹,倘若T不是空樹,則必須具備下列的性質: 節點的型態是n, A0, (K1, A1), (K2, A2),...,(Kn, An) 其中Ai是子樹的指標 0 ≤ i ≤ n < m; n為節點上的鍵值數,Ki是鍵值1 ≤ i ≤ n 及 1 ≤ n < m 。

11.1 m-way搜尋樹 節點中的鍵值是由小至大排列的,因此 Ki < Ki+1,1 ≤ i< n。 子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki , 0 < i < n。 子樹An的所有鍵值均大於Kn,而且子樹A0的所有鍵值小於K1。 Ai指到的子樹,0 ≤ i ≤ n亦是m-way搜尋樹。

11.1 m-way搜尋樹 例如有一3-way的搜尋樹,其中有12個鍵值分別為12, 17, 23, 25, 28, 32, 38, 45, 48, 55, 60, 70。 表為圖11-1中每個節點之3-way的搜尋樹表示法。

11.1 m-way搜尋樹 由於3-way搜尋榼,每個節點的型態是n, A0, (K1, A1), (K2, A2),...,(Kn, An),因此a節點的格式為 2, b, (23, c), (48, d) 表示a節點有2個鍵值,在b節點中的所有鍵值均小於23,在c節點中的每個鍵值大小介於23與48之間,最後d節點的所有鍵值均大於48。

11.1 m-way搜尋樹 11.1.1 m-way搜尋樹的加入

11.1 m-way搜尋樹

11.1 m-way搜尋樹

11.1 m-way搜尋樹

11.1 m-way搜尋樹 11.1.2 m-way搜尋樹的刪除 而在刪除方法上則與二元搜尋樹極為相同,若刪除非樹葉節點上的鍵值,則以左子樹中最大的鍵值或右子樹中的最小鍵值取代之。

11.1 m-way搜尋樹 刪除3則直接刪除之:

11.1 m-way搜尋樹 刪除8: 刪除12:

11.1 m-way搜尋樹 刪除7: 刪除10:

11.2 B-tree 一棵order為m的B-tree是一m-way搜尋樹。若是空樹,也算B-tree,假若高度 > 1必須滿足以下的特性: 樹根至少有二個子節點(children),亦即節點內至少有一鍵值(key value)。 除了樹根外,所有節點至少有個子節點,至多有m個子節點。此表示至少應有 - 1個鍵值,至多有m-1個鍵值(表示大於m/2的最小正整數)。 所有的樹葉節點皆在同一階層。

11.2 B-tree

11.2 B-tree 在圖11-2中(a)不屬於B-tree of order 3,因為樹葉節點不在同一階層上,而(b)是屬於B-tree of order 3,因為所有的樹葉節點皆在同一階層。 B-tree of order 3表示除了樹葉節點外每一節點的分支度(degree)不是等於2就是等於3,因此B-tree of order 3就是著名的2-3 tree。假使m=4,則是2-3-4 tree。

11.2 B-tree 11.2.1 B-tree 的加入 假設加入P節點,若 該節點少於m-1個鍵值。 該節點的鍵值已等於m-1,則將此節點分為二,因為一棵order為m的B-tree,最多只能有m-1個鍵值。

11.2 B-tree 請看下例之說明(此處的B-tree為order 5)

11.2 B-tree 加入88於圖11-3

11.2 B-tree 承(1)加入98

11.2 B-tree 承(2)加入91

11.2 B-tree 承(3)加入93

11.2 B-tree 承(4)加入99

11.2 B-tree 11.2.2 B-tree的刪除 B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的,此處也分成兩部份: 刪除的節點是樹葉節點(leaf node), 刪除的節點為非樹葉節點(non-leaf node)。

11.2 B-tree 以B-tree of order 5如圖11-4來說明。

11.2 B-tree 若刪除的節點是樹葉節點 如將圖11-4刪除70

11.2 B-tree 如欲將圖11-4中的鍵值26刪除

11.2 B-tree 若欲刪除85

11.2 B-tree 有一棵B-tree of order 5如圖11-5所示

11.2 B-tree 先從圖11-5刪除59

11.2 B-tree 由於合併後c節點僅存放一個鍵值,不符合B-tree的定義

11.2 B-tree 若刪除的節點為非樹葉節點

11.2 B-tree 若刪除圖11-6的鍵值50,找到p'節點為g,從中取出最小值52,並代替50。

11.2 B-tree 若再刪除52

11.2 B-tree 承上圖,若繼續刪除55

11.2 B-tree 由於g節點其鍵值數少於 個鍵值,且其兄弟節點h也沒有大於 個鍵值,故將g、h、與c的鍵值65合併於g節點,結果如下圖:

11.2 B-tree 此時c節點的鍵值數也少於 ,且其兄弟節點的鍵值數不大於 ,故將b、c與a節點合併,結果如下: