Re: [理工] [資結]95中山資工
原題目 20
/ \
8,15 25,30
/ | \ / | \
5 12 16 21 27 36
題目問刪20完會做幾次disk access
刪20 因為在non-leaf 所以可以以左子樹的最大值或右子樹的最小值取代root
以右子樹最小來取代root為例
先算讀的部分
刪完20之後要找右子樹最小 也就是21
所以要找21 要先讀20 and 25,30 and 21 這三個node 讀了3次
刪掉root之後以21來取代的b tree如下
21
/ \
8,15 25 , 30
/ | \ / | \
5 12 16 O 27 36
O是沒有key的node
因為underflow
把O和27當作一個node讀一次 發現沒辦法rotation所以要做combine 所以這裡又讀了一次
把25下拉跟27合併成一個node
combine 的結果
21
/ \
8,15 30
/ | \ / \
5 12 16 25,27 36
而21and 30 and 25,27 為新的三個點 所以寫了3次
因此disk access 讀4次 寫3次 共7次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 36.225.130.115
※ 編輯: white8824 來自: 36.225.130.115 (11/06 02:49)
推
11/06 10:45, , 1F
11/06 10:45, 1F
→
11/06 10:47, , 2F
11/06 10:47, 2F
→
11/06 10:48, , 3F
11/06 10:48, 3F
→
11/16 00:00, , 4F
11/16 00:00, 4F
→
11/16 00:01, , 5F
11/16 00:01, 5F
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：
理工
1
1