如果我理解正確，在Haskell中修改（插入或洗掉）二叉搜索樹需要復制整個樹，因此實際上使其成為O(n)。有沒有辦法在O(log n)中實作它，或者編譯器可能會將O(n)插入優化到O(log n) “在引擎蓋下”？
uj5u.com熱心網友回復：
如果我理解正確，在 Haskell 中修改（插入或洗掉）二叉搜索樹需要復制整個樹，因此實際上使其成為O(n)。
您不需要復制整個樹。實際上，讓我們使用一個簡單的不平衡二叉搜索樹，例如：
data Tree a = Node (Tree a) a (Tree a) | Empty deriving (Eq, Show)
然后我們可以插入一個值：
insertIn :: Ord a => a -> Tree a -> Tree a
insertIn x = go
where go Empty = Node Empty x Empty
go n@(Node l v r)
| x < v = Node (go l) v r
| x > v = Node l v (go r)
| otherwise = n在這里，我們在構造 a 的情況下重用 ，在構造 a 的情況下重用。對于我們訪問的每個節點，我們創建一個新節點，其中在新節點中使用兩個子樹之一。這意味著新樹將指向與原始樹相同的子樹物件。rNode (go l) v r lNode l v (go r)
在這個例子中，新節點的數量因此與O(d)成比例，而d是樹的深度。如果樹相當平衡，那么它將插入O(log n)。
當然，您可以通過在節點中存盤更多關于平衡的資訊來改進演算法并定義 AVL 樹或紅黑樹，在這種情況下，您可以保證O(log n)插入時間。
所有資料都是不可變的這一事實有助于重用樹的某些部分：我們知道這一點l并且r不能更改，因此兩棵樹將共享大量節點，從而減少所需的記憶體量，如果您想同時使用原來的和新的樹。
如果沒有必要參考舊樹，垃圾收集器最終將收集已被新樹替換的“舊”節點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/416354.html
標籤：