資料結構 紅黑樹 - 考試

By Megan
at 2015-04-12T19:42
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的解答
以上個人的想法如有錯請其他大大指教
--
: 各位好,由於上完王老師函授的資結,對於上課所提及到的紅黑樹著墨甚少,
: 所以心中還是有不少疑問,首先附上範例圖:
: 一顆紅黑樹如下
: 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
at 2015-04-14T18:56

By Edwina
at 2015-04-17T16:02
at 2015-04-17T16:02

By Zora
at 2015-04-18T13:40
at 2015-04-18T13:40

By Agatha
at 2015-04-19T11:23
at 2015-04-19T11:23

By Candice
at 2015-04-21T11:39
at 2015-04-21T11:39

By Quanna
at 2015-04-22T19:43
at 2015-04-22T19:43

By Margaret
at 2015-04-27T02:50
at 2015-04-27T02:50

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

By Caroline
at 2015-05-03T08:19
at 2015-05-03T08:19

By Rae
at 2015-05-05T05:21
at 2015-05-05T05:21

By Ivy
at 2015-05-10T00:44
at 2015-05-10T00:44

By Yedda
at 2015-05-11T05:16
at 2015-05-11T05:16

By Hedwig
at 2015-05-15T15:02
at 2015-05-15T15:02

By Mary
at 2015-05-19T19:50
at 2015-05-19T19:50

By Bethany
at 2015-05-23T22:29
at 2015-05-23T22:29

By Noah
at 2015-05-26T10:50
at 2015-05-26T10:50

By Robert
at 2015-05-28T18:26
at 2015-05-28T18:26

By Tracy
at 2015-05-29T21:22
at 2015-05-29T21:22

By Kyle
at 2015-05-31T08:26
at 2015-05-31T08:26

By George
at 2015-06-02T21:35
at 2015-06-02T21:35
沒錯,你的2node是指節點內的2個值吧

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

By Thomas
at 2015-06-09T12:50
at 2015-06-09T12:50

By Donna
at 2015-06-13T04:34
at 2015-06-13T04:34

By Margaret
at 2015-06-13T09:07
at 2015-06-13T09:07

By Audriana
at 2015-06-18T08:52
at 2015-06-18T08:52

By Agatha
at 2015-06-22T23:26
at 2015-06-22T23:26

By Liam
at 2015-06-24T13:21
at 2015-06-24T13:21

By Blanche
at 2015-06-26T03:54
at 2015-06-26T03:54
樹葉

By Oliver
at 2015-06-30T20:46
at 2015-06-30T20:46

By Mason
at 2015-07-03T18:35
at 2015-07-03T18:35

By Cara
at 2015-07-04T15:02
at 2015-07-04T15:02

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

By Genevieve
at 2015-07-07T03:17
at 2015-07-07T03:17
圖中的第三點剛好就是此種情況

By Ingrid
at 2015-07-11T11:40
at 2015-07-11T11:40

By Anonymous
at 2015-07-13T16:29
at 2015-07-13T16:29

By Faithe
at 2015-07-14T11:47
at 2015-07-14T11:47

By Anonymous
at 2015-07-14T23:43
at 2015-07-14T23:43

By Oscar
at 2015-07-18T03:20
at 2015-07-18T03:20

By Charlie
at 2015-07-18T04:39
at 2015-07-18T04:39

By Adele
at 2015-07-20T18:48
at 2015-07-20T18:48

By Tracy
at 2015-07-24T11:07
at 2015-07-24T11:07

By David
at 2015-07-28T08:13
at 2015-07-28T08:13

By Lucy
at 2015-08-01T05:35
at 2015-08-01T05:35

By Agnes
at 2015-08-06T05:03
at 2015-08-06T05:03

By Hedy
at 2015-08-09T01:13
at 2015-08-09T01:13

By Hedwig
at 2015-08-13T15:34
at 2015-08-13T15:34

By Mary
at 2015-08-16T05:30
at 2015-08-16T05:30

By Quintina
at 2015-08-17T05:30
at 2015-08-17T05:30

By Hedda
at 2015-08-21T15:10
at 2015-08-21T15:10

By Mia
at 2015-08-21T21:32
at 2015-08-21T21:32

By Lydia
at 2015-08-26T01:28
at 2015-08-26T01:28
Related Posts
購買基本電學題庫&選購國考計算機

By Hardy
at 2015-04-12T19:17
at 2015-04-12T19:17
請問易台大正課會有解題模板嗎?

By Mason
at 2015-04-12T17:58
at 2015-04-12T17:58
資料結構 紅黑樹

By Candice
at 2015-04-12T17:50
at 2015-04-12T17:50
101年地特工數選擇第9題求解

By Hamiltion
at 2015-04-12T17:28
at 2015-04-12T17:28
高考資訊技師 今年5科異動

By Susan
at 2015-04-12T17:13
at 2015-04-12T17:13