ocaml的 - 建立二叉樹

我讀教程OCaml的賈森·希基，這裏是在短構建樹的建議方式：ocaml的 - 建立二叉樹

type 'a elem = Empty | Node of 'a * 'a elem * 'a elem;; 

let rec insert x = function 
    | Empty -> Node (x, Empty, Empty) 
    | Node (y, left, right) as node -> 
     if x < y then 
      Node (y, insert x left, right) 
     else if x > y then 
      Node (y, left, insert x right) 
     else 
      node;;

難道我理解正確的話，這種做法使的副本插入新元素的樹的一部分，並將舊樹的一部分附加到此新副本中？

如果是這樣，我的評估是，每個插入僅創建O(height(tree))節點？

這樣做（對我來說有點不尋常）是否依賴於這樣的事實：如果逐個插入多個值，那麼所有較舊的節點組副本將被GC有效刪除？

來源

2014-01-12 Rodion Gorkovenko

我是否正確理解這種方法會生成插入新元素的樹的一部分的副本，並將舊樹的一部分附加到此新副本中？

如果是這樣，我的評估是，每個插入僅創建O（高度（樹））節點？

是的。如果你正確地平衡了樹（例如紅黑樹），那麼這意味着插入是O（log（n））。

這樣做（對我來說有點不尋常）是否依賴這樣的事實：如果逐個插入多個值，那麼所有較舊的節點組副本將被GC有效刪除？

是的。函數式編程語言通常會產生大量短命的垃圾，例如元組，閉包和小數據類型值。但是實現被優化以使其非常便宜（例如，通過輕量級堆表示，指針凹凸分配和世代收集）。

還要注意，這種方法有一個基本優勢：功能數據結構自動爲持久，即舊版本保持有效，並且可以同時使用多個版本的數據結構。對於命令式數據結構，當需要「恢復」舊版本時，有兩種選擇：（1）事先複製整個結構，或者（2）維護更改日誌並向後運行。這兩個選項通常比使用功能結構更昂貴，其中持久性是免費的。

請參閱Chris Okasaki關於Purely Functional Data Structures的優秀書籍，詳細討論各種功能數據結構的複雜性，攤銷成本和各種其他方面。（他的thesis涵蓋了大部分相同的內容，並免費提供。）

來源

2014-01-12 09:11:14

ocaml的 - 建立二叉樹

回答

相關問題