我正在設計一個Haskell中的自平衡樹。作爲一個練習，因爲你的後背很高興。什麼自平衡樹在函數式編程中最簡單？
以前在C和Python中，我傾向於Treaps和Splay Trees，因爲它們有簡單的平衡規則。我總是不喜歡R/B樹，因爲他們看起來比他們更值得工作。
現在，由於Haskell的功能性質，事情似乎發生了變化。我可以在10行代碼中編寫一個R/B插入函數。另一方面，Treaps需要包裝來存儲隨機數字生成器，Splay Trees是一種自上而下的痛苦。
所以我問你是否有其他類型的樹木的經驗？ 哪些更好地利用函數式語言的模式匹配和自頂向下性質？
好吧，我想沒有太多的參考或研究回答這個問題。相反，我花時間嘗試了不同的想法和樹木。我沒有發現比RB樹更好的東西，但也許這只是搜索偏好。
的RB樹可以是（插入）有四個簡單的規則平衡，如shown by Chris Okasaki：
balance T (T R (T R a x b) y c) z d = T R (T B a x b) y (T B c z d)
balance T (T R a x (T R b y c)) z d = T R (T B a x b) y (T B c z d)
balance T a x (T R b y (T R c z d)) = T R (T B a x b) y (T B c z d)
balance T a x (T R (T R b y c) z d) = T R (T B a x b) y (T B c z d)
balance T a x b = T B a x b
AVL樹可以以類似的模式匹配方式來平衡。但是規則不壓縮，以及：
balance T (T (T a x b dx) y c (-1)) z d (-2) = T (T a x b dx) y (T c z d 0) 0
balance T a x (T b y (T c z d dz) 1) 2 = T (T a x b 0) y (T c z d dz) 0
balance T (T a x (T b y c 1) 1) z d (-2) = T (T a x b -1) y (T c z d 0) 0
balance T (T a x (T b y c (-1)) 1) z d (-2) = T (T a x b 0) y (T c z d 1) 0
balance T (T a x (T b y c _) 1) z d (-2) = T (T a x b 0) y (T c z d 0) 0
balance T a x (T (T b y c 1) z d (-1)) 2 = T (T a x b -1) y (T c z d 0) 0
balance T a x (T (T b y c (-1)) z d (-1)) 2 = T (T a x b 0) y (T c z d 1) 0
balance T a x (T (T b y c _) z d (-1)) 2 = T (T a x b 0) y (T c z d 0) 0
balance t = t
至於通常被認爲是AVL樹縫遜色於RB樹，他們很可能不值得額外的麻煩。
AA樹木理論上可以平衡好的，很容易：
balance T n (T n a x b) y c = T n a x (T n b y c) -- skew
balance T n a x (T n b y (T n c z d)) = T (n+1) (T n a x b) y (T n c z d) --split
balance T n a x b = T n a x b
但遺憾的是哈斯克爾不喜歡n超載。 AA樹的不太標準的實現可能不是使用等級，而是更類似於R和B的東西，可能會運行良好。
Splay樹很困難，因爲您需要關注單個節點，而不是樹的靜態結構。它可以通過merging insert and splay完成。因爲您沒有全局隨機生成器，但需要在每個節點中保留實例，因此在功能環境中也會遇到困難。這可以通過leaving the task of generating priorities to the client來解決，但即使如此，您也無法使用模式匹配進行優先級比較。
正如你所說紅黑樹不難用。你有沒有給finger trees a look？您可能有興趣使用類似於zipper.的東西來擴充您的基礎數據結構。您可能會感興趣的另一棵樹是AA tree它是對紅黑樹的簡化。
手指樹看起來非常酷。我很高興你讓我發現這個數據結構。 然而，他們並不看起來特別簡單的實施。我見過的大多數實現都使用2-3樹，並將樹概括爲很多用例。 – 2010-11-13 19:42:59
你可能會對AA樹感興趣，它們只是簡化的紅黑樹。 – stonemetal 2010-11-16 18:28:47
謝謝你指着我AA樹，我愛他們！不幸的是，他們使用的排名不適合模式匹配:( – 2011-06-03 10:19:48
這是已經實施的。
在諸如Data.Map和Data.Set的平衡樹的Haskell中有很好的實現。他們不滿足您的需求嗎？不要重新實現，重用。
出於算法的目的，它經常發生，你需要一棵樹，在每個節點中存儲特定的信息，無論是統計樹中子樹的大小，還是區間樹中最右邊的點。 – 2011-06-11 11:50:53
OCaml標準庫爲其map仿函數使用AVL樹。如果包含remove操作，看起來好像比RB樹更容易實現。
不是直接的答案，而是閱讀「純功能數據結構」以獲得一些好的想法。 – 2010-11-12 15:25:15
我喜歡它。它沒有涉及到詳細的結構，但提供了一個很好的一般觀點。 – 2010-11-12 17:02:07
你需要一個搜索樹，或者一個序列的樹形表示（如fingertrees - 連接和分裂）？在後一種情況下，純功能2-3樹是微不足道的。 – jkff 2010-11-18 06:20:31