2006/11/30

正宗紅黑樹模擬

有需要者可透過這個 Java applet 和紅黑樹多親近親近 XD。

--
努力與紅黑樹建立良好關係中 XD。


插入、刪除節點的規則初步背起來了,洗澡後準備仔細看看紅黑性質維護的狀況。目前結論:大概沒有人想實作紅黑樹兩次。

--
所以請愛用 std::map XD。


這個 applet 也相當棒,而且做得很漂亮,可以開啟思考模式、調整動畫速度,跟著動畫一起想。

--
紅黑樹還是用模擬的學習效果最棒 XD。


差不多了,以後應該隨時能即時推出各種規則才對(雖然可能卡一陣子 XD)。個人認為如果先從 recoloring 的狀況開始,不能 recoloring 時再想辦法轉,邏輯上比較順。課本上以及實際操作還得考慮雙旋轉和單旋轉,不過不難處理。可以考慮做個紅黑樹投影片 XD。

--
所以做投影片其實是整理所學的好手段 XD。

--
原訂於此時段解決的高等微積分就不了了之 XD。

Blogger yen311/30/2006 4:15 pm 說:

這對於正在學二元樹的我是一個好啟發XD

 
Anonymous ㄚ順(spallen@mail.apol.com.tw)1/04/2008 5:33 am 說:

看了你POST的文,跟用了一下 Applet 模擬,算是對紅黑樹有非常粗淺的認識ㄚ。

但我在看一些有關紅黑樹的題目時還是有很多不明白的地方,想要請教你一下!

1.為何黑節點只有一個child時,該child一定是紅色?

2.為何每個紅色節點的兩個 child 都要是黑色?

在網路上查了一些資料,對紅黑樹提到的都很少,只有在你的blog有比較多的介紹,所以想要問你看看嚕。

謝謝!~~~

 
Blogger Josh Ko1/04/2008 9:13 am 說:

Hi,

關於你問的兩個問題:

1. 為何黑節點只有一個 child 時,該 child 一定是紅色?

理論上看紅黑樹的時候,我們會把 NULL 點也畫出來,並視之為黑色。例如最末端的葉點(leaf node)會被視為又有兩個 black children。

紅黑樹必須滿足所謂的「黑色性質」,即從 root 走到任一個 NULL 點路徑上的黑色節點數必須相等,以及 root 必須是黑色。另外當然也有「紅色性質」,要求任兩個紅色節點不得相鄰。黑色性質和紅色性質都滿足的話,就保證紅黑樹大致上是平衡的,即高度為 O(lg n)。

所以當黑節點 B 只有一個 child C 時,另一邊有一個 NULL 節點 D,依照剛剛的約定,我們視之為黑色。黑色性質告訴我們,「從 root 走到 D」和「從 root 走到任一個其他 NULL 點」兩條路徑上的黑點數目必須相同。因為從 root 到 B 的路徑是唯一的,我們就能推得「以 C 為 root 的子樹內除了 NULL 以外不能有黑色節點」,否則從 root 經過那個黑色節點走到下面的 NULL,中途遇到的黑色節點數會和走到 D 不一樣,違背黑色性質。

由此我們不僅知道 C 一定是紅色,還知道 C 下面都沒有點,因為紅點下面不能再放紅點(紅色性質),剛剛又已經證明下面不能放黑點。整棵紅黑樹的點非紅即黑,所以 C 點下面不能放別的點,一定是兩個 NULL。

2. 為何每個紅色節點的兩個 child 都要是黑色?

這直接從紅色性質的定義就能得到。

---

推薦你看我們老師今年上課用的投影片:

http://www.csie.ntu.edu.tw/~hil/algo2007fall/2007fall-algo04.ppt

這一份是「資料結構」概念的介紹,最後一部份就是討論紅黑樹。
另外關於紅黑樹的插入和刪除,我用自己的邏輯整理過一遍:

http://joshkos.blogspot.com/2007/11/blog-post_25.html

不一定很好懂就是了,我主要是寫給我自己備忘的 :P。

-- JK

 

<< 回到主頁