Haskell中如何代價最小的操作（插入、刪除）一棵樹？

03-01

最近在用haskell寫一些數據結構，比如說avl tree，但是每次insert、remove，遞歸里都調用了構造函數，相當於完全重建了一棵樹，感覺上是很浪費的，在c裡面更改指針指向就可以了，haskell裡面有什麼技巧嗎？

修改一個不可變數據結構的代價的確是比較大的。以樹為例，和你想的不一樣的是，並不需要完全重建一棵樹，如圖所示：

對於一棵 $n$ 個節點的樹，新建的節點數為 $O(log n)$ 。想要達到 $O(1)$ 的複雜度就需要用可變數據結構了。

更多請參考：

函數式編程所倡導使用的「不可變數據結構」如何保證性能？

Pros. / Cons. of Immutability vs. Mutability

Zipper？

Learn You a Haskell for Great Good!