正宗紅黑樹模擬
有需要者可透過這個 Java applet 和紅黑樹多親近親近 XD。
--
努力與紅黑樹建立良好關係中 XD。
插入、刪除節點的規則初步背起來了，洗澡後準備仔細看看紅黑性質維護的狀況。目前結論：大概沒有人想實作紅黑樹兩次。
--
所以請愛用 std::map XD。
這個 applet 也相當棒，而且做得很漂亮，可以開啟思考模式、調整動畫速度，跟著動畫一起想。
--
紅黑樹還是用模擬的學習效果最棒 XD。
差不多了，以後應該隨時能即時推出各種規則才對（雖然可能卡一陣子 XD）。個人認為如果先從 recoloring 的狀況開始，不能 recoloring 時再想辦法轉，邏輯上比較順。課本上以及實際操作還得考慮雙旋轉和單旋轉，不過不難處理。可以考慮做個紅黑樹投影片 XD。
--
所以做投影片其實是整理所學的好手段 XD。
--
原訂於此時段解決的高等微積分就不了了之 XD。
這對於正在學二元樹的我是一個好啟發XD
看了你POST的文，跟用了一下 Applet 模擬，算是對紅黑樹有非常粗淺的認識ㄚ。
但我在看一些有關紅黑樹的題目時還是有很多不明白的地方，想要請教你一下！
1.為何黑節點只有一個child時，該child一定是紅色？
2.為何每個紅色節點的兩個 child 都要是黑色？
在網路上查了一些資料，對紅黑樹提到的都很少，只有在你的blog有比較多的介紹，所以想要問你看看嚕。
謝謝！~~~
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
<< 回到主頁