Red Black Tree In Functional Programming
12 May 2019本文介紹 FP 如何實作紅黑樹的新增和刪除,如果不清楚紅黑樹是什麼,或忘記如何 imperatively 操作紅黑樹,可以先到紅黑樹介紹獲得來龍去脈。
好的,知道那些奇怪的操作之後,可以忘掉了,因為 FP 用不到。
新增
到底要怎麼講解新增,我想了很久,但我看不出來有什麼文字比這張圖更能解釋程式在幹嘛的。(參考資料 2 有 haskell 程式。)
非常精妙的將全部 case 整理成四種情況,並且歸一到相同解!
刪除
真正的困難藏在這裡,往下讀之前可以試試看:你現在知道多一個紅的要怎麼平衡,思考一下少一個黑的如何平衡?
解法的核心在於引入兩個新顏色,深黑與負黑,分別代表 +2, -1。(你可能記得紅黑樹每條路徑的黑點數量要相同,換句話說這些顏色其實是計數器,黑跟紅代表 1 跟 0)接著運用 divide and conquer 分成三個步驟:
- remove:當你移除末端的黑點時就會用到深黑。
- bubble:將深黑狀態往上傳,因為在底部沒有子節點來平衡這個顏色。這個步驟很簡單,把子節點 -1、父節點 +1 即可。
- balance:在這個過程尋找消除的機會。
即使多兩個顏色,也只多出六種情況,最美妙的是,其中四種可以照抄新增的! 剩下的則負責將左圖變成右圖
其餘的就是一些有關刪除的 helper function,你的作業就寫完啦!(誰會把這個當作業啊,還有人性嗎?)
後記
會想做這個的初衷是為了製作測試腦袋是否清醒的石蕊試紙,突發奇想覺得如果能正確心算操作紅黑樹的話,那腦袋大概就是清醒的(想到這種點子的時候大概是不清醒的)。同時想順便練習 elm,於是 project 就這麼開始了。樹的呈現花了一點心思,因為我也沒用過 svg,要查一下;拉線方式也從一開始的固定角度變成直接算座標。重頭戲果然還是在演算法。我過於拘泥原本作法,想了很久還是想不出來,問神之後就找到那兩篇論文。
寫完之後才發現,根本沒用嘛,操作麻煩只存在於 imperative 啊,變成這樣就算喝醉也能心算新增和刪除了吧。