如何按DRY原則實現二叉樹？
01-11
眾所周知，二叉樹是一種非常靈活的數據結構。
可以有紅黑樹，也可以有AVL樹
可以mutable，也可以immutable
mutable可以有parent指針，也可以有sibling指針
不但如此，還記錄額外的信息，加速字元串為Key時的查詢
或者AVL樹記錄節點的size，可以當動態數組用
我相信，為了不同的用途，每個人都實現過無數遍二叉樹
現在問題來了，我們能不能按DRY原則來實現二叉樹，可以很方便的把不同的功能按需組合起來，而不用每次重複實現？
求教，真誠的。
我們這些全都表示成一個元素序列，用二叉樹每個節點維護一個 monoid，叫做這段元素的
度量(measure)，要可以合併的那種。然後我們支持兩個操作：1. 把兩段拼起來
2. 按照度量二分把序列劈成兩半這樣就能實現常見的二叉樹功能了。可以參見 finger tree。（補充：
常數時空間的 iterator 可以
1.理論上，immutable 用前位置兩邊的序列分開，存成 finger tree，支持往兩邊的常數複雜度挪動。2. mutable 的話我說的那些和 parent sibling 指針不矛盾……不過好像確實不能用 monoid 實現 parent/sibling）還有些不太常見的，比如替罪羊樹套可持久化線段樹什麼的容我再想想卧槽原來提問者是b大，怕了怕了
想到了一個相關的talk
順便說問題評論區小劇場好有意思
我是來看評論區小劇場的
不懂。
有點想問個平行的問題：如何以 DRY 原則實現各種字元串？
沒有，野路子沒學過數據結構
推薦閱讀：