資料結構紅黑樹 - 考試

By Megan
at 2015-04-12T19:42

Table of Contents

※ 引述《lei70200 (客家一哥)》之銘言：
: 各位好，由於上完王老師函授的資結，對於上課所提及到的紅黑樹著墨甚少，
: 所以心中還是有不少疑問，首先附上範例圖：
: 一顆紅黑樹如下
: 15
: / \
: 6 17
: / \ / \
: 3 12 16 20
: / \ / \
: 10 13 18 23
: /
: 7
: 補上其最初2-3-4樹如下
: 15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7,10 13 16 18 23
: 其中節點7、12、20 為紅色節點，請一步步刪除圖中節點，
: 依序為10、18、3、16、13、12、17
: 最後的解答為
: 7
: / \
: 6 20
: / \
: 15 23

我以234樹來說
15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7,10 13 16 18 23

刪10

15
: / \
: 6,12 17,20
: / | \ / | \
: 3 7 13 16 18 23

刪18

15
: / \
: 6,12 17
: / | \ / |
: 3 7 13 16 20,23
刪3

15
: / \
: 12 17
: / \ / \
: 6,7 13 16 20,23
刪16
15
: / \
: 12 20
: / \ / \
: 6,7 13 17 23

刪13
15
: / \
: 7 20
: / \ / \
: 6 12 17 23

刪12

: 15 20
: / | \
: 6,7 17 23

刪17
7,20
: / | \
: 6 15 23

再來就以小的值做為父親節點轉紅黑樹

7
: / \
: 6 20
: / \
: 15 23

就得到大大你PO的解答
以上個人的想法如有錯請其他大大指教

--

Tags: 考試

All Comments

By Hamiltion
at 2015-04-14T18:56

不太會用顏色所以沒表現出7和20之間是紅色的

By Edwina
at 2015-04-17T16:02

謝謝!!! 這樣看起來清楚多了@@!!!

By Zora
at 2015-04-18T13:40

我234樹刪16那邊和你不太一樣耶.我root會變(12,15,20)

By Agatha
at 2015-04-19T11:23

刪16後原本16的右兄弟還有2個值也就要把17向下移，20向上

By Candice
at 2015-04-21T11:39

移，還達不到要降階的條件

By Quanna
at 2015-04-22T19:43

可我看書上步驟~除root外，遇到2node要先轉成3或4node

By Margaret
at 2015-04-27T02:50

沒錯阿你要先把20移上去和17成為17,20這樣就是書上說的再

By Barb Cronin
at 2015-04-30T06:48

向17,20借17向下移

By Caroline
at 2015-05-03T08:19

疑？所以他不是指搜尋的路上有遇到2node要先處理？

By Rae
at 2015-05-05T05:21

而是找到要刪除的元素再判斷？

By Ivy
at 2015-05-10T00:44

搜尋的路上有遇到就要先處理沒錯

By Yedda
at 2015-05-11T05:16

兩位大大都沒錯，只是刪16跟刪13的圖錯了

By Hedwig
at 2015-05-15T15:02

k大的比較沒問題，那是王老師的版本...

By Mary
at 2015-05-19T19:50

B樹是要刪除的節點到樹根沒有辦法借(都只有1個KEY)才會向

By Bethany
at 2015-05-23T22:29

下降一階，這題還有一個節點有2個KEY怎麼會就降階

By Noah
at 2015-05-26T10:50

不知道是否為top-down 2-3-4樹和n-way樹差別嗎？

By Robert
at 2015-05-28T18:26

topdown作法可避免backward restructuring path

By Tracy
at 2015-05-29T21:22

k大你有看王老師的資料結構11-57(2014)delete有分三種情

By Kyle
at 2015-05-31T08:26

況，(1)sibling為2個node(分支為2)才和兄弟合併，(2)(3)

By George
at 2015-06-02T21:35

都是兄弟有3或以上的node會先借1個來，所以我的刪16和13
沒錯，你的2node是指節點內的2個值吧

By Tristan Cohan
at 2015-06-04T21:34

是使用第(1)個情況沒錯呀~同你的圖要刪16的2-3-4樹

By Thomas
at 2015-06-09T12:50

17為2node他的兄弟12也為2node所以合併變成(12,15,17)

By Donna
at 2015-06-13T04:34

之後作刪除16動作，root就會變成(12,15,20)

By Margaret
at 2015-06-13T09:07

過程是這樣：http://i.imgur.com/VA60fs8.jpg

By Audriana
at 2015-06-18T08:52

不知道步驟是否有錯~ 但參考步驟紅黑樹轉回的2-3-4樹

By Agatha
at 2015-06-22T23:26

應該是會長這樣~ 有錯再請高手補充...

By Liam
at 2015-06-24T13:21

錯了，你刪16要先看他的兄弟，不是先看父節點(17)

By Blanche
at 2015-06-26T03:54

(1)的情況是p為樹葉，這題帶(1)的話p指的是17那個它不是
樹葉

By Oliver
at 2015-06-30T20:46

這邊的(1)是你回文的情況(1)=書上的(3)-①

By Mason
at 2015-07-03T18:35

然後是依序往下處理q=17 p=parent=15所以使用3-1的case

By Cara
at 2015-07-04T15:02

downward pass，p與q是會移動的，當遇到2node先處理

By Barb Cronin
at 2015-07-05T11:07

因為書上有些模糊，我有特地google找一些教材參考

By Genevieve
at 2015-07-07T03:17

這張圖說明的滿清楚的：http://i.imgur.com/AYsjXfP
圖中的第三點剛好就是此種情況

By Ingrid
at 2015-07-11T11:40

又不是要刪17你q指向17對嗎？第1個條件p有2個node則p為

By Anonymous
at 2015-07-13T16:29

q先指17確認不是2node才往下啊

By Faithe
at 2015-07-14T11:47

root你覺得用你做的方式這個條件合嗎？

By Anonymous
at 2015-07-14T23:43

他不是root

By Oscar
at 2015-07-18T03:20

一開始q為15為2node->root情況排除往下17為2node處理

By Charlie
at 2015-07-18T04:39

看那張投影片，我的理解是這樣啦~

By Adele
at 2015-07-20T18:48

這個是剛好3層，如果是4層你不就要從第2層開始向下合併？

By Tracy
at 2015-07-24T11:07

投影片2的意思就表示遇到2node要先處理，而不是直接就

By David
at 2015-07-28T08:13

是指到欲刪除的元素

By Lucy
at 2015-08-01T05:35

應該不會有你說的情況

By Agnes
at 2015-08-06T05:03

應該沒有第二層2node第三層也2node的case吧

By Hedy
at 2015-08-09T01:13

所以會到第三層，然後處理情況又和本題一樣了

By Hedwig
at 2015-08-13T15:34

k大講得很對呀~先遇到2node先處理，全部處理完後再刪除

By Mary
at 2015-08-16T05:30

之後就停止做動作

By Quintina
at 2015-08-17T05:30

這樣才符合Forward deletion,層層往下處理的意義

By Hedda
at 2015-08-21T15:10

我上面講得有點跳：我的意思是指第二層和第三層若同為

By Mia
at 2015-08-21T21:32

2node則因為第二層已和root合併，所以原來第三層會變成

By Lydia
at 2015-08-26T01:28

就會變成4個兄弟所以不會出現bug問題

資料結構紅黑樹 - 考試

All Comments

Related Posts

購買基本電學題庫&選購國考計算機

請問易台大正課會有解題模板嗎?