第六章 樹狀結構 T r e e 版權屬作者所有,非經作者 同意不得用於教學以外用途.

Slides:



Advertisements
Similar presentations
组长:倪运超 小组成员:徐悦、曹吕卿、孙浩、徐圣尧.  上海的历史 上海的历史  上海的历史 上海的历史  上海的文化 —— 建筑 上海的文化 —— 建筑  上海的文化 —— 美食 上海的文化 —— 美食  香港的历史 香港的历史  香港的历史 香港的历史  香港的文化 —— 建筑 香港的文化.
Advertisements

一、 突出解析几何复习中的重点问题的通法通解 解析几何中的重点问题 一、 突出解析几何复习中的重点问题的通法通解 直线与圆锥曲线的位置关系 重点一.
(5)能根据具体要求绘制简单的电路图(不超过两个用电器) b
600年前,鄭和率領世界上最強大的艦隊,浩浩蕩蕩的駛入印度洋,展開一場「文化帝國」的海上大秀。
第十三章 中国的传统科学技术 中国古代的科技曾经长期处于世界领先地位,对人类文明的进步作出过重要贡献,并形成了富有特色的科技文化。在今天,源自中国古代科技文化的中医学仍然在现实生活中发挥着积极的作用。
大南海文化園區 (國立歷史博物館 -初期計畫) 簡介
第7章 樹與二元樹 (Trees and Binary Trees)
Chapter 06 Tree and binary tree 第六章 树和二叉树
動畫與遊戲設計 Data structure and artificial intelligent
中國歷史人物—孫中山 姓名:黎昕晴 班別:五理.
第6章 二叉树和树 前面的章节主要讨论的是线性结构,二叉树和树属于非线性的结构。遍历非线性结构比线性结构要麻烦。
雄伟的金字塔.
——奧科特公開及內部培訓 系列課程(三)之十一
宁波万里国际学校 陈湘龙
第十一章 理气剂.
计算机软件技术基础 数据结构与算法(4).
第六章 树和二叉树.
第6章 树和二叉树 (Tree & Binary Tree)
第5章 树( Tree )和二叉树 5.1 树的基本概念 5.2 二叉树 5.3 遍历二叉树和线索二叉树 5.4 树和森林
CH6 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林
第8章 查找 在英汉字典中查找某个英文单词的中文解释;在新华字典中查找某个汉字的读音、含义;在对数表、平方根表中查找某个数的对数、平方根;邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息,就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释,就需要存储类似英汉字典这样的信息表,以及对该表进行的查找操作。本章将讨论的问题即是“信息的存储和查找”。
第八章 查找.
数据结构 第六章 树与二叉树 深圳大学计算机系 蔡茂国.
第五章 树 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
数据结构 第6章 树和二叉树 什么是树和二叉树?? 二叉树的遍历 数据结构.
第三节 固精缩尿止带药 1.特点:酸涩收敛,主归肾、膀胱经。 2.功效:固精、缩尿、止带。兼补肾。
足太阳膀胱经.
经 络 学.
第8章 查找 数据结构(C++描述).
开 学 第 一 课 六年级3班.
§4 Additional Binary Tree Operations
Chap4 Tree.
Tree(樹) 什麼是「樹」? 「樹」的範例 「樹」的定義 「樹」的表示法.
Chapter 5 Tree & Binary Tree
Chap5 Graph.
樹狀結構 陳怡芬 2018/11/16 北一女中資訊專題研究.
Chapter8 Binary and Other Trees
講師:郭育倫 第3章 基本資料結構 講師:郭育倫
哈夫曼编码.
第12章 樹狀搜尋結構 (Search Trees)
演算法與資料結構 製作單位: 高雄市立高雄中學.
第六章 树和二叉树.
本章重点难点 重点:顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。
第 七 章 樹狀結構 課程名稱:資料結構 授課老師:________ 2019/1/1.
教 师:曾晓东 电 话: E_mail: 计算机软件技术基础 教 师:曾晓东 电 话: E_mail:
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
樹狀結構 Tree Structure chapter 7 德明科技大學資訊科技系.
親愛的老師您好 感謝您選用本書作為授課教材,博碩文化準備本書精選簡報檔,特別摘錄重點提供給您授課專用。 說明: 博碩文化:
Data Structure.
计算机问题求解 – 论题2-14 -B树 2018年6月10日.
数据结构 第9章 查找 什么是查找?? 静态查找 动态查找 哈希表 数据结构.
第九章 查找 2019/2/16.
樹 2 Michael Tsai 2013/3/26.
感謝同學們在加分題建議. 我會好好研讀+反省~
B+ Tree.
Tree & Binary Tree.
書名 Java於資料結構與演算法之實習應用
二叉树的遍历.
第六章 树和二叉树 学习要点 理解树的定义和基本术语,重点了解二叉树的定义、性质、存储结构; 掌握二叉树遍历的递归算法及它的典型运算;
9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较
第7章 樹與二元樹(Trees and Binary Trees)
怎样使用电器正常工作 习题课.
資料結構使用Java 第9章 樹(Tree).
Chapter 6 樹狀結構.
9.1 何謂高度平衡二元搜尋樹 9.2 AVL-tree的加入 9.3 AVL-tree的刪除
106二專班第二次作業 2017/11/27.
计算机问题求解 – 论题 基本的数据结构 2018年05月09日.
Data Structure.
第10章 二元搜尋樹 (Binary Search Tree)
JAVA 程式設計與資料結構 第十七章 Tree.
Presentation transcript:

第六章 樹狀結構 T r e e 版權屬作者所有,非經作者 同意不得用於教學以外用途

本章內容 6-1 樹及定義 6-2 二元樹的基本性質 6-3 二元樹的儲存方式 6-4 二元樹的建立 6-5 二元樹的走訪 6-1 樹及定義 6-2 二元樹的基本性質 6-3 二元樹的儲存方式 6-4 二元樹的建立 6-5 二元樹的走訪 6-6 引線二元樹 6-7 二元搜尋樹 6-8 高度平衡二元樹 (AVL樹) 6-9 m 元搜尋樹及 B 樹 6-10 2-3 樹 6-11 2-3-4 樹與紅黑樹 6-12 Huffman 樹

6-1 樹及定義 董事長 總經理 主任秘書 業務經理 人事經理 總務經理 秘書甲 秘書乙 國內部副理 國外部副理 採購主任 庶務主任 第五章提到,樹在數學上的定義是:沒有環路的連通圖,我們稱這種樹為「一般樹」( general tree ) 或是「無根樹」( unrooted tree ) 在資料結構中所應用的樹,我們稱之為「有根樹」( rooted tree ),有一個特定的節點稱為「樹根」( root )。樹根通常畫在一棵樹的最上方。樹根又包含零個到多個「子樹」( subtree ),畫在樹根的下方。 例如圖6.1中,董事長即為樹根。此樹根包含兩個子樹,分別是以總經理為樹根的子樹,和以主任秘書為樹根的另一子樹。

1. 內部節點 ( internal node ,或非終端節點 , non-terminal node ) : 節點 A、B、C、G 階度 ( level) 1 A B C D 2 E F G 3 H I J 4 1. 內部節點 ( internal node ,或非終端節點 , non-terminal node ) : 節點 A、B、C、G 2. 外部節點 ( external node ,或終端節點 terminal node ,或樹葉 leaf node ) :節點 D、E、F、H、I、J 3. 節點 A 是節點 B、C、D 的父節點。節點 B、C、D 是節點 A 的子節點 4. 在第 2 階的節點有 B、C、D 5. 這棵樹的高度是 4 6. 所有的樹,節點數 ( V ) = 邊數 ( E ) + 1 除了樹根以外,其餘每個節點都有一個對應的邊從它的父節點指向它自己,因此節點數會比邊數多1,而多出來的節點就是樹根

6-2 二元樹的基本性質 … … … 1. 二元樹第 i 階上所有節點的數目最多為 2i-1 個 6-2 二元樹的基本性質 階度 ( i ) 2i-1 1 1 (21-1) 二元樹:每個內部節點最多有2個兒子 2 2 (22-1) 3 4 (23-1) … … … 4 8 (24-1) 1. 二元樹第 i 階上所有節點的數目最多為 2i-1 個 2. 高度為 k 的二元樹上所有節點的數目最多為 2k -1個 3. 完滿(full)二元樹:高度為 k 且總節點數為 2k -1的二元樹 高度為 4 的完滿二元樹 總節點數為 24 –1 = 15

4. 高度為 k 的二元樹上所有節點的數目最少為 k 個 5.若是所有內部節點都正好有兩個子節點,這種二元樹稱為正規二元樹 ( formal binary tree ) 外部節點數目 t 比內部節點數目 i 多一 t = i + 1 6.如果二元樹的排列情形如下:第 k 階滿了才能排到第 k+1 階,並且每一階的節點都是往左靠 ,這種二元樹稱為完整二元樹 ( complete binary tree ) 1 2 3 4 5 6 7 8 9 ※ 編號 i 的左兒子編號為 2i + 1,右兒子編號為 2i + 2 ※編號 i 的父節點編號為 (i-1)/2

7. 具有n個節點的完整二元樹,其高度為 lg n + 1。 假設完整二元樹的節點數目為 n,高度為 k。 根據二元樹性質(第2點及第3點),高度為 k 的完整二元樹,節點最多的狀況就是高度為 k 的完滿二元樹,總節點數是2k-1,節點最少的狀況就是高度為 k-1的完滿二元樹再加一個節點,節點數是2k-1-1 + 1 = 2k-1。 k-1 k 節點最少 節點最多 因此: 0 < 2k-1  n  2k-1 0 < 2k-1  n  2k-1 < 2k 0 < 2k-1  n < 2k 取對數 lg (2k-1)  lg n < lg(2k) k-1  lg n < k lg n = k-1 k = lg n + 1 因此:0 < 2k-1  n  2k-1 0 < 2k-1  n  2k-1 < 2k 0 < 2k-1  n < 2k 取對數 lg (2k-1)  lg n < lg(2k) k-1  lg n < k lg n = k-1 k = lg n + 1

6-3 二元樹的儲存方式 一維陣列表示法 1. 使用完整二元樹的編號方式。 2. 如果二元樹不很 「完整」,將會有很多儲存空間的浪費。 A 6-3 二元樹的儲存方式 一維陣列表示法 A 1. 使用完整二元樹的編號方式。 B 1 C 2 D 3 E 4 F 5 G 6 H 7 2. 如果二元樹不很 「完整」,將會有很多儲存空間的浪費。 [0] [1] [2] [3] [4] [5] [6] [7] Tree1[] A B C D E F G H A B 1 C 2 D 3 F 6 E 8 G 13 H 14 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] Tree2[] A B C D F E G H

鏈結表示法—動態配置節點 typedef struct tagTnode { struct tagTnode *left_c; // 指向左兒子 char data; //資料 struct tagTnode *right_c; //指向右兒子 }TNode; A B C D E F G H

6-4 二元樹的建立 建立二元樹的步驟 讀入資料,如果是 0 則表示停止 6-4 二元樹的建立 建立二元樹的步驟 讀入資料,如果是 0 則表示停止 否則以此資料建立一個節點,並且以同樣原則建立此節點的左子樹,直到不能繼續為止。 接著建立此節點的右子樹,直到不能繼續為止。

輸入資料為:ABDH000E00CF00G00,則建立此二元樹的步驟如下: 2.讀入資料 B,建立節點,並為節點 A 的左子節點,接著建立此節點 B 的左子樹 A B 3.讀入資料 D,建立節點,並為節點 B 的左子節點,接著建立此節點 D 的左子樹 A B D 4.讀入資料 H,建立節點,並為節點 D 的左子節點,接著建立此節點 H 的左子樹 A B D H

ABDH000E00CF00G00 A B D H 5. 讀入0,表示 H 無左子節點。節點H的左子樹已無法再長,接著建立節點H的右子樹 6. 讀入0,表示 H 無右子節點。節點D的左子樹已無法再長,接著建立節點D的右子樹 7. 讀入0,表示 D 無右子節點。此時節點 B 的左子樹已無法繼續再長 8. 讀入資料 E,以此資料建立節點,並為節點 B 的右子節點 A B D H E

ABDH000E00CF00G00 A B D H E 9. 讀入0,表示 E 無左子節點 10. 讀入0,表示 E 無右子節點。節點A的左子樹已無法再長 11. 讀入資料 C,以此資料建立節點,並為節點 A 的右子節點 A B D H E C

ABDH000E00CF00G00 12. 讀入資料 F,以此資料建立節點,並為節點 C 的左子節點 A B D H E C F 15. 讀入資料 G,以此資料建立節點,並為節點 C 的右子節點 A B D H E C F G 16. 讀入0,表示 G 無左子節點 17. 讀入0,表示 G 無右子節點。節點 A 的右子樹已無法再長。由於節點 A 是樹根,因此整棵樹也無法繼續再長,建立過程結束

6-5 二元樹的走訪 系統性走訪:「前序走訪」、「中序走訪」、和「後序走訪」 前序走訪 ( preorder traverse ): 6-5 二元樹的走訪 系統性走訪:「前序走訪」、「中序走訪」、和「後序走訪」   前序走訪 ( preorder traverse ): l    先拜訪目前的節點 l    再以前序順序拜訪左子樹 l    再以前序順序拜訪右子樹 A B C 前序走訪順序 A B C A B C E D G F J H A B C E D 前序走訪順序 A B D E C A的左子樹 A的右子樹 前序走訪順序 A B D J E C F H G

中序走訪 ( inorder traverse ) l    先以中序順序拜訪左子樹 l    再拜訪目前的節點 l    再以中序順序拜訪右子樹 A B C 中序走訪順序 B A C A B C E D A B C E D G F J H 中序走訪順序 D B E A C A的左子樹 A的右子樹 中序走訪順序 J D B E A H F C G

後序走訪 ( postorder traverse ): l    先以後序順序拜訪左子樹 l    再以後序順序拜訪右子樹 l    再拜訪目前的節點 A B C 後序走訪順序 B C A A B C E D A B C E D G F J H 後序走訪順序 D E B C A A的左子樹 A的右子樹 後序走訪順序 J D E B H F G C A

前序走訪的順序為:ABDEFCHGI 中序走訪的順序為:DBFEAHCGI 後序走訪的順序為:DFEBHIGCA 例 6.1 A B C E

前序走訪函式 中序走訪函式 後序走訪函式 1. void preorder(NODE *p) 2. { if (p != NULL) 3. { visit(p); //拜訪目前的節點 4. preorder(p->left_c); //遞迴拜訪左子樹 5. preorder(p->right_c); //遞迴拜訪右子樹 6. } 7. } 中序走訪函式 1. void inorder(NODE *p) 2. { if (p != NULL) 3. { inorder(p->left_c); //遞迴拜訪左子樹 4. visit(p); //拜訪目前的節點 5. inorder(p->right_c); //遞迴拜訪右子樹 6. } 7. } 後序走訪函式 1. void postorder(NODE *p) 2. { if (p != NULL) 3. { postorder(p->left_c); //遞迴拜訪左子樹 4. postorder(p->right_c); //遞迴拜訪右子樹 5. visit(p); //拜訪目前的節點 6. } 7. }

6-6 引線二元樹 ※ n 個節點的二元樹,有 2n – ( n-1 ) = n + 1 個指標是接地的 6-6 引線二元樹 ※ n 個節點的二元樹,有 2n – ( n-1 ) = n + 1 個指標是接地的 ※ 將原本接地的指標作為引線,將左引線指向此節點的中序立即前行者 ,將右引線指向此節點的中序立即後繼者,稱為引線二元樹 A B C D E F G J H I K 如何找節點的中序立即後繼者 :  1. 如果是右引線,照右引線所指即為後繼者。例如節點K,節點K有右引線,因此照著它的右引線指向節點D,節點D即為節點K的後繼者。  2. 如果是右指標,則先往右,再一路沿著左指標往左,一直到沒有左指標,而是左引線的節點為止。例如節點A,節點A有右指標,則往右到節點C,再一路沿著左指標到達節點H,節點H沒有左指標,而是左引線,因此節點H即為節點A的後繼者。

首節點 對整棵樹作中序走訪的過程: A B C D 1 1 E 1 F 1 1 G 1 J 1 H 1 1 I 1 1 K 1 A B C D 1 1 E 1 F 1 1 G 1 J 1 H 1 1 I 1 1 K 1 對整棵樹作中序走訪的過程: 1. 首節點的後繼者,先往右 ( 回到自己 ),再一路往左,可找到節點 J 2. 節點 J 的後繼者,先往右(K),再一路往左 ( 沒有 ),因此節點 J 的後繼者是節點 K 3. 節點 K 的後繼者,往右是引線,因此節點 K 的後繼者是節點 D 4. ~ 11. 以此類推,順序為:B E A H F C G I 12. 節點 I 的後繼者,往右是引線,因此節點 I 的後繼者是首節點,走訪結束

6-7 二元搜尋樹 二元搜尋樹的定義: 對二元搜尋樹中每一個內部節點而言,它的左子樹所有節點的資料值,都小於它的資料值,它的右子樹所有節點的資料值,都大於它的資料值 51 39 70 20 45 63 80 10 42 49 75 ※ 這是一棵二元搜尋樹,因為每個內部節點都符合定義 ※ 對二元搜尋樹作中序走訪,可以得到由小到大排列的順序 ※ 將資料整理成二元搜尋樹,將可以有效率地找到所要的資料

二元搜尋樹的建立 每讀入一個資料就依循下列原則,將新節點插入擴充中的二元搜尋樹: 1. 如果是空樹,則新節點為樹根 2. 否則將新節點的資料與樹根相比,小於樹根則往左子樹,大於樹根則往右子樹 3. 重複與此子樹的樹根比較,直到指標接地為止 4. 將新節點加在最後停留之處 我們以下列的資料,示範建立二元搜尋樹的程序: 51、70、39、45 51 70 70加入,70 > 51 ( 樹根 ),往右子樹 51 加入51為樹根 51 39 70 39加入,39 < 51 (樹根 ),往左子樹 51 39 70 45 45加入,45 < 51 (樹根 ),往左子樹。45 > 39,往右子樹。

二元搜尋樹的節點搜尋 若搜尋的鍵值為 49 搜尋的過程和插入節點十分類似,依循下列原則: 1. 將搜尋的鍵值 (key) 與樹根相比,若相等則搜尋成功 2. 否則,小於樹根則往左子樹,大於樹根則往右子樹 3. 重複與此子樹的樹根比較,若相等則搜尋成功 4. 若直到指標接地為止都不相等,則搜尋失敗 若搜尋的鍵值為 49 1. 首先鍵值49和樹根資料51相比。49比51小,因此往左子樹,因為根據定義,如果資料49在二元搜尋樹中,只可能在資料51的左子樹中出現 51 2. 鍵值49和資料39相比,49比39大,往右子樹。 39 70 20 45 3. 鍵值49和資料45相比,49比45大,往右子樹 63 80 10 42 4. 鍵值49和資料49相比,相等,搜尋成功 49 75

二元搜尋樹的節點刪除 依照要刪除節點所在的位置,分為三種狀況來討論: 狀況1. 要刪除的節點是樹葉:只要直接刪去即可,這是最單純的狀況。 51 51 r r 39 39 p 20 45 45 49 49 狀況2. 要刪除的節點只有一棵子樹(左或右皆同):只要將其父節點的指標越過欲刪除節點,改指向此節點的子節點即可。 51 51 r r 39 39 p 20 45 30 45 30 49 25 31 49 25 31

(1) 找到此節點的「中序立即前行者」,並且以此前行者節點的資料,代替要刪除節點的資料。 狀況 3. 要刪除的節點有二棵子樹,作法是: (1) 找到此節點的「中序立即前行者」,並且以此前行者節點的資料,代替要刪除節點的資料。 (2) 由於此前行者最多只可能有一棵子樹(否則它就不可能被找上),因此再按照前述狀況1或狀況2,直接刪除此前行者即可完成刪除動作。 29 q p s r 35 13 38 6 19 4 10 12 11 (a) 欲刪除 13 29 q p s r 35 12 38 6 19 4 10 11 (b) 由12代替其位 29 p s r 35 12 38 6 19 4 10 11 (c)刪除原來的 12

6-8 高度平衡二元樹 (AVL樹) 在AVL樹上,所有內部節點的左子樹高度和右子樹高度,相差小於或等於1。 2 B 1 -1 -1 ( a )AVL樹 ( b )非AVL樹 假設新加入節點為N,而由於新節點的加入,造成原本平衡係數BF為 1的節點其BF變為 2,違反了AVL性質。這時,就必須根據新節點插入的位置,分成四種狀況來旋轉調整,使其恢復AVL性質。 LL型:新節點N插入到節點A的左兒子的左子樹。 RR型:新節點N插入到節點A的右兒子的右子樹。 LR型:新節點N插入到節點A的左兒子的右子樹。 RL型:新節點N插入到節點A的右兒子的左子樹。

LL型 插入 20 LL旋轉 A B 1 2 60 A 60 A 41 B 41 70 1 41 B B 70 29 60 A 29 52 29 52 20 52 70 20 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡的子樹 LL旋轉 A B 插入 N 1 A 2 A B B 1 B A AR AR BL BL BR h-1 BL BR BR AR h h-1 h-1 h N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

RR型 RR旋轉 A B 插入 85 -1 60 A -2 60 A 81 B 41 81 B 41 -1 81 B 60 A 93 1 81 B 41 81 B 41 -1 81 B 60 A 93 1 72 93 72 93 1 41 72 85 85 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡的子樹 RR旋轉 A B -1 A 插入 N -2 A B B -1 B A AL AL BR h-1 BL BR BL BR AL BL h h-1 h-1 h N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

LR型 插入 58 LR旋轉 A C 1 70 A 2 70 A 62 C B B 41 75 -1 41 75 -1 41 B -1 70 62 C B B 41 75 -1 41 75 -1 41 B -1 70 A 1 32 62 C 80 32 62 C 80 32 45 68 75 20 45 68 20 45 68 20 58 80 N 58 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡 插入 N LR旋轉 A C 1 A 2 A C B -1 A B AR -1 B AR BL CL CR AR C h C 1 BL BL CL CR CL CR h h-1 N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

RL型 插入 70 RL旋轉 A C -1 42 A -2 42 A 62 C 41 75 41 1 75 B 1 42 A 75 B B 62 C 41 75 41 1 75 B 1 42 A 75 B B 32 62 C 80 32 -1 62 C 80 41 45 68 80 45 68 92 45 68 92 32 70 N 92 70 N (a)平衡的子樹 (b)失去平衡 (c)重新平衡 插入 N RL旋轉 A C -1 A -2 A C B B 1 -1 A B AL BR AL BR C C 1 AL CL CR BR h h CL CR CL CR h-1 N N (a)平衡的子樹 (b)失去平衡 (c)重新平衡

6-9 m元搜尋樹及 B 樹 m 階 B 樹符合下列條件: 1. 每個節點至多有 m 個子樹 2. 樹根至少有 2 個子樹,除非它也是樹葉 4. 所有的樹葉都在同一階,亦即從樹根到任一個樹葉所經過的路徑長度均相同 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 f 24 27 g 33 40 h 49 i 63 69 j 77 k

加入鍵值21 加入鍵值74 B樹鍵值插入的原則,是必須確保插入後仍符合B樹的特性: 經過類似搜尋的過程,找到第一個可插入點(一定是樹葉)。 如果此樹葉的資料欄位有空位,將新鍵值插入適當順序的資料欄位。 如果樹葉的資料欄位已經額滿沒有空位,則樹葉進行節點分裂 (split),並且分配資料鍵值到兩個樹葉,同時將中間的鍵值(第 m / 2 個)往上插入父節點。 父節點的插入過程如同步驟2和步驟3,如果此節點還需要分裂,則一直重複。因此每次插入最多可能使B樹的高度h增加1。 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 77 k 加入鍵值74 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 74 77 k

加入鍵值43 L0 K1 L1 K2 L2 30 60 a 16 22 b 47 c 71 d 4 12 e 18 21 f 24 27 g 33 40 h 49 i 63 69 j 74 77 k L0 K1 L1 K2 L2 30 60 a 16 22 b 40 47 c 71 d 4 12 e 18 21 f 24 27 g 33 h 43 h’ 49 i 63 69 j 74 77 k

加入鍵值37 L0 K1 L1 K2 L2 30 60 a 16 22 b 40 47 c 71 d 4 12 e 18 21 f 24 27 g 33 37 h 43 h’ 49 i 63 69 j 74 77 k 加入鍵值39 L0 K1 L1 K2 L2 40 x 30 a 60 a’ b c c’ d 16 22 37 47 71 4 12 18 21 24 27 33 39 43 49 63 69 74 77 69

6-10 2-3 樹 2 – 3樹的節點鍵值插入,原則如下(與B樹同): 1. 新鍵值的第一個可插入點一定是樹葉。 6-10 2-3 樹 2 – 3 樹其實就是「3階的B樹」( B tree of order 3 )。因此在2 – 3樹上的每個節點最多有2個鍵值、3個指標。 具有1個鍵值(2個指標)的節點稱為 “2-node” (2-節點) 具有2個鍵值(3個指標)的節點稱為 ”3-node” (3-節點)。 2 – 3樹的節點結構可以宣告為: 1. typedef struct tagTwo3Node 2. { int KeyLeft, KeyRight ; 3. struct tagTwo3Node *LinkLeft, *LinkMiddle, *LinkRight; 4. } Two3Node; 2 – 3樹的節點結構可以圖示為: LinkLeft KeyLeft LinkMiddle KeyRight LinkRight 2 – 3樹的節點鍵值插入,原則如下(與B樹同): 1. 新鍵值的第一個可插入點一定是樹葉。 2. 如果樹葉的資料欄位有空位,將鍵值插入適當的資料欄位即告完成。 3. 如果樹葉的資料欄位已經額滿沒有空位,則樹葉進行節點分裂 (split) 。 4. 每次插入最多可能使2 – 3樹的高度h增加1。

(1)加入2, 7 (2)加入1 2 c 節點a分裂,鍵值2上提 2 2 7 a 1 a 7 b (3)加入8 (4)加入4 2 7 c 2 c 節點b分裂,鍵值7上提 1 4 8 1 a 7 8 b a b d (5)加入5, 9, 0 2 7 c 1 4 5 8 9 a b d (6)加入3 4 g 節點b分裂,鍵值4上提 節點c分裂,鍵值4上提 2 c 7 f 1 3 5 8 9 a b e d

6-11 2-3-4 樹與紅黑樹 2 – 3 – 4樹其實就是「4階的B樹」( B-tree of order 4 )。 6-11 2-3-4 樹與紅黑樹 2 – 3 – 4樹其實就是「4階的B樹」( B-tree of order 4 )。 在2 – 3 – 4樹上的每個節點最多有3個鍵值、4個指標。 具有1個鍵值(2個指標)的節點稱為 “2-node” (2-節點) 具有2個鍵值(3個指標)的節點稱為 “3-node” (3-節點) 具有3個鍵值(4個指標)的節點稱為 “4-node” (4-節點)。 2 – 3 – 4樹的節點結構可宣告如下: 1. typedef struct tagTwo34Node 2. { int Key[3]; 3. struct tagTwo34Node *Link[4]; 4. } Two34Node; 2 – 3 – 4樹的節點結構圖示如下: Link[0] Key[0] Link[1] Key[1] Link[2] Key[2] Link[3]

每個節點有2個指標,並且每個指標有2種形式:「紅指標」及「黑指標」。在畫出紅-黑樹時,通常以實線表示黑指標,以虛線表示紅指標。 「紅-黑樹」是2 – 3 – 4樹的二元樹表示法。 每個節點有2個指標,並且每個指標有2種形式:「紅指標」及「黑指標」。在畫出紅-黑樹時,通常以實線表示黑指標,以虛線表示紅指標。 2-3-4樹轉成紅黑樹 (1)一個2 – node 轉成1個紅-黑樹節點,2個指標的Color均為Black。 24 a b (2)一個3 – node轉成2個紅-黑樹節點,這2個紅-黑樹節點以1個Red指標連接。 24 27 a b c 或 (3)一個4 – node 轉成3個紅-黑樹節點,中間節點以兩個Red指標連接另2個節點 24 45 27 a b c d

此樹的內部路徑長 I = 0 (A)+ 1 (B) + 1 (C) + 2 (D) = 4 6-12 Huffman 樹 內部路徑長 ( internal path length ) :由樹根到每個內部節點的路徑長度之總和 外部路徑長 (external path length ) :由樹根到每個外部節點的路徑長度之總和 A B C D E 1 2 3 F 路徑長 G 9 8 7 此樹的內部路徑長 I = 0 (A)+ 1 (B) + 1 (C) + 2 (D) = 4 外部路徑長 E = 2 (E) + 2 (F) + 3 (G) = 7 加權外部路徑長 :由樹根到每個外部節點的路徑長乘上該節點的加權之總和 此圖的加權外部路徑長 = 2 * 8 (E) + 2 * 7 (F) + 3 * 9 (G) = 57 對具有相同外部節點同時加權也相同的不同二元樹,其加權外部路徑長也不同。其中加權外部路徑長最小的二元樹稱為Huffman樹,或稱最佳二元樹。

Huffman演算法 :由已知的外部節點建構 Huffman 樹(加權外部路徑長最小的樹 )的過程 開始 演算法:Huffman法建立編碼樹 (編碼字母表與頻率) 將樹葉(字母)按照加權(頻率)由小到大排成一個串列 當串列中多於一個元素,重複迴圈 從串列取出加權最小的兩個子樹生成一個新子樹,其加權為兩個子樹之加權和 將新子樹樹根插入串列適當位置,使串列仍然維持由小到大 迴圈結束 演算法結束 將樹葉按照加權由小到大排成一個串列 是 串列只有一個元素? 否 取串列左邊兩個加權最小的樹葉生成一個新節點,其加權為兩個樹葉之加權和 將新節點插入串列適當位置,使串列仍然維持由小到大 結束

假設有ABCDEF六個樹葉,其加權分別為15, 8, 30, 27, 5, 15 1. 將樹葉按照加權,由小到大排序好,成為一有序串列。   E / 5, B / 8, A / 15, F / 15, D / 27, C / 30 2. 取串列最左邊兩個加權最小的樹葉,作為一新節點N的兩個子節點,新節點N的加權為兩個樹葉的加權之和 N E B 8 13 5 3.  將節點N放入有序串列的適當位置,使串列保持次序。   N / 13, A / 15, F / 15, D / 27, C / 30 4. 取最左邊兩個節點 N 和 A,合成新節點 P P N A 15 28 13 E B 8 5

5. 將節點 P 放入有序串列的適當位置,使串列保持次序。 F / 15, D / 27, P / 28, C / 30 6. 取最左邊兩個節點 F 和 D,合成新節點 R P N A 15 28 13 E B 8 5 R F D 27 42 7.  將節點 R 放入有序串列的適當位置,使串列保持次序。   P / 28, C / 30, R / 42 8. 取最左邊兩個節點 P 和 C,合成新節點 S R F D 27 42 15 P N A 28 13 E B 8 5 S C 30 58

9. 將節點 S 放入有序串列的適當位置,使串列保持次序。 R / 42, S / 58 10. 取最左邊兩個節點 R 和 S,合成新節點 T,只剩一個節點,停止 A 15 E B 8 5 F D 27 C 30

Huffman樹經常用在處理資料的壓縮編碼。假設共有6個字母需要編碼,分別是A/15, B/8, C/30, D/27, E/5, F/15,合起來剛好100 %。我們依照前述 Huffman 演算法建構 Huffman樹: 1 1 1 F 15 D 27 30 C 1 A 15 1 E 5 B 8 A的編碼 = 右左右 = 101 B的編碼 = 右左左右 = 1001 C的編碼 = 右右 = 11 D的編碼 = 左右 = 01 E的編碼 = 右左左左 = 1000 F的編碼 = 左左 = 00

編碼一篇1000個字母的文章。根據字母出現的頻率,它們的出現次數分別是:  A 出現的次數 = 1000 * 15 % = 150 B 出現的次數 = 1000 * 8 % = 80 C 出現的次數 = 1000 * 30 % = 300 D 出現的次數 = 1000 * 27 % = 270 E 出現的次數 = 1000 * 5 % = 50 F 出現的次數 = 1000 * 15 % = 150  因此總共需要的bit數 150 * 3 + 80 * 4 + 300 * 2 +270 * 2 + 50 * 4 + 150 * 2 = 2410 未經編碼,每個字母用3個位元表示,( 8 種組合 ),共需3000個位元 2410 壓縮率= ( 1 - ) * 100 %  20 % 3000