資料結構 紅黑樹 - 考試

By Candice
at 2015-04-12T17:50
at 2015-04-12T17:50
Table of Contents
各位好,由於上完王老師函授的資結,對於上課所提及到的紅黑樹著墨甚少,
所以心中還是有不少疑問,首先附上範例圖:
一顆紅黑樹如下
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
以下提出我的疑問:
(1)老師有說過可以利用2-3-4樹推出紅黑樹(但是只做了插入就下課了...)
那麼,刪除紅黑樹的步驟是先將2-3-4樹刪除完後再轉換成紅黑樹嗎?
(2)承(1)如果是,由於2-3-4樹的特性在刪除之前可能會有值的位置變動,
這樣的變動是不是會讓紅黑樹為不唯一?如果不是,那麼每個步驟該怎麼做?(
比如說旋轉的時機等等...)資質駑鈍,看不出來兩棵樹在刪除的時候
有甚麼關聯OTL
(3)我有另外去用紅黑樹的正式規則做一次,但是做出來的結果與解答相去甚遠,
再這樣的差異下,考試的時候應該要以哪個為主?(感覺很吃運氣....)
後面的紅黑樹整個就大爆炸阿...出了感覺就很不妙....
希望有精通此樹的大大們可以為小的開釋...
--
Tags:
考試
All Comments

By Oscar
at 2015-04-14T11:33
at 2015-04-14T11:33

By Margaret
at 2015-04-15T04:50
at 2015-04-15T04:50

By Sierra Rose
at 2015-04-20T03:30
at 2015-04-20T03:30

By Bethany
at 2015-04-21T11:53
at 2015-04-21T11:53

By Emily
at 2015-04-21T16:01
at 2015-04-21T16:01

By Emily
at 2015-04-25T21:57
at 2015-04-25T21:57

By Daniel
at 2015-04-28T00:11
at 2015-04-28T00:11
時的2-3-4樹是否一樣

By Anonymous
at 2015-04-29T03:22
at 2015-04-29T03:22

By Rae
at 2015-05-01T01:21
at 2015-05-01T01:21
亂

By David
at 2015-05-04T21:51
at 2015-05-04T21:51

By Carolina Franco
at 2015-05-09T05:37
at 2015-05-09T05:37
否則會有很多種

By Queena
at 2015-05-10T11:22
at 2015-05-10T11:22

By Kyle
at 2015-05-12T16:53
at 2015-05-12T16:53
Related Posts
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
知識達DVD函授學員團結自救方法

By Todd Johnson
at 2015-04-12T16:53
at 2015-04-12T16:53
機械原理小問題

By Necoo
at 2015-04-12T16:13
at 2015-04-12T16:13
中會 減損迴轉

By Elizabeth
at 2015-04-12T16:01
at 2015-04-12T16:01