资料结构-使用C语言2B-tree课件.ppt

上传人(卖家):三亚风情 文档编号:3025763 上传时间:2022-06-23 格式:PPT 页数:38 大小:2.57MB
下载 相关 举报
资料结构-使用C语言2B-tree课件.ppt_第1页
第1页 / 共38页
资料结构-使用C语言2B-tree课件.ppt_第2页
第2页 / 共38页
资料结构-使用C语言2B-tree课件.ppt_第3页
第3页 / 共38页
资料结构-使用C语言2B-tree课件.ppt_第4页
第4页 / 共38页
资料结构-使用C语言2B-tree课件.ppt_第5页
第5页 / 共38页
点击查看更多>>
资源描述

1、資料結構資料結構 - 使用使用 C 語言語言 2B-tree的功能非常強大,有許多資料庫系統皆採用B-tree來儲存與刪除其資料。資料結構資料結構 - 使用使用 C 語言語言 3何謂m-waw搜尋樹(m-way search tree)?一棵m-way搜尋樹,所有節點的分支度(dgree)均小於或等於m。若T為空樹,則T亦稱為m-way搜尋樹,倘若T不是空樹,則必須具備下列的性質:n節點的型態是n, A0, (K1, A1), (K2, A2),.,(Kn, An) 其中Ai是子樹的指標 0 i n m; n為節點上的鍵值數,Ki是鍵值1 i n 及 1 n m 。資料結構資料結構 - 使用使

2、用 C 語言語言 4n節點中的鍵值是由小至大排列的,因此 Ki Ki+1,1 i n。n子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki , 0 i 1必須滿足以下的特性:n樹根至少有二個子節點(children),亦即節點內至少有一鍵值(key value)。n除了樹根外,所有節點至少有個子節點,至多有m個子節點。此表示至少應有 - 1個鍵值,至多有m-1個鍵值(表示大於m/2的最小正整數)。n所有的樹葉節點皆在同一階層。資料結構資料結構 - 使用使用 C 語言語言 16資料結構資料結構 - 使用使用 C 語言語言 17在圖11-2中(a)不屬於B-tree of order 3,因為樹葉節點

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。資料結構資料結構 - 使用使用 C 語言語言 1811.2.1 B-tree 的加入假設加入P節點,若n該節點少於m-1個鍵值。n該節點的鍵值已等於m-1,則將此節點分為二,因為一棵order為m的B-tree,最多只能有m-1個鍵值。資料結構資料結構 - 使用使用 C 語言語言 19請看下

4、例之說明(此處的B-tree為order 5)資料結構資料結構 - 使用使用 C 語言語言 20加入88於圖11-3資料結構資料結構 - 使用使用 C 語言語言 21承(1)加入98資料結構資料結構 - 使用使用 C 語言語言 22承(2)加入91資料結構資料結構 - 使用使用 C 語言語言 23承(3)加入93資料結構資料結構 - 使用使用 C 語言語言 24承(4)加入99資料結構資料結構 - 使用使用 C 語言語言 2511.2.2 B-tree的刪除B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的,此處也分成兩部份:n刪除的節點是樹葉節點(leaf n

5、ode),n刪除的節點為非樹葉節點(non-leaf node)。資料結構資料結構 - 使用使用 C 語言語言 26以B-tree of order 5如圖11-4來說明。資料結構資料結構 - 使用使用 C 語言語言 27如將圖11-4刪除70資料結構資料結構 - 使用使用 C 語言語言 28n如欲將圖11-4中的鍵值26刪除資料結構資料結構 - 使用使用 C 語言語言 29n若欲刪除85資料結構資料結構 - 使用使用 C 語言語言 30n有一棵B-tree of order 5如圖11-5所示資料結構資料結構 - 使用使用 C 語言語言 31先從圖11-5刪除59資料結構資料結構 - 使用使

6、用 C 語言語言 32由於合併後c節點僅存放一個鍵值,不符合B-tree的定義資料結構資料結構 - 使用使用 C 語言語言 33資料結構資料結構 - 使用使用 C 語言語言 34若刪除圖11-6的鍵值50,找到p節點為g,從中取出最小值52,並代替50。資料結構資料結構 - 使用使用 C 語言語言 35若再刪除52資料結構資料結構 - 使用使用 C 語言語言 36承上圖,若繼續刪除55資料結構資料結構 - 使用使用 C 語言語言 37由於g節點其鍵值數少於 個鍵值,且其兄弟節點h也沒有大於 個鍵值,故將g、h、與c的鍵值65合併於g節點,結果如下圖:資料結構資料結構 - 使用使用 C 語言語言 38此時c節點的鍵值數也少於 ,且其兄弟節點的鍵值數不大於 ,故將b、c與a節點合併,結果如下:

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 办公、行业 > 各类PPT课件(模板)
版权提示 | 免责声明

1,本文(资料结构-使用C语言2B-tree课件.ppt)为本站会员(三亚风情)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!


侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|