在OCaml中構建二進制搜索樹的正確方法

好的，我在OCaml中編寫了一個binary search tree。在OCaml中構建二進制搜索樹的正確方法

type 'a bstree = 
    |Node of 'a * 'a bstree * 'a bstree 
    |Leaf 


let rec insert x = function 
    |Leaf -> Node (x, Leaf, Leaf) 
    |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

上面的代碼被說成是良好的The right way to use a data structure in OCaml

但是，我發現了一個問題。這insert一氣呵成建設從列表中BST時，如

let rec set_of_list = function 
    [] > empty 
    | x :: l > insert x (set_of_list l);;

因此，如果我們從列表中不斷構建BST，沒問題，我們可以得到它具有所有節點的一個完整的BST只會工作列表。

但是，如果我以前已經建立了一個BST，現在我要插入一個節點，然後將得到的BST不會有完整的節點從以前的樹，對嗎？

那麼我應該如何在OCaml中編寫一個bst，以便我們用前一棵樹中的所有節點創建一個新的bst以保持前一棵樹不變？如果每次我需要從舊的bst複製所有節點，是否會影響性能？

編輯：

所以我們可以說最初，一個BST與一個節點t1 = (10, Leaf, Leaf)創建。

然後我做let t2 = insert 5 t1，那我就拿t2 = (10, (5, Leaf, Leaf), Leaf)吧？在t2裏面，我們給一個變量c1 to the child node (5, Leaf, Leaf)

然後我做let t5 = insert 12 t2，然後我得到t3 = (10, (5, Leaf, Leaf), (15, Leaf, Leaf))。讓我們給變量c2 to the child node (5, Leaf, Leaf)

所以我的問題是c1 == c2？ t2和t3中的兩個(5, Leaf, Leaf)完全一樣嗎？

來源

2013-01-22 Jackson Tale

不應該有在列表和代碼中的第二次調用其他地方，插入一個新值插入第二個項目的通話之間的差異。插入x old_tree應該返回新的樹。 – stonemetal

您是否嘗試過並且失敗了，或者您在猜測？ – molbdnilo

我不明白你問的是什麼問題。「那麼由此產生的bst將不會有前一棵樹的完整節點，我是對的」 - >我不明白你想在這句話中說些什麼，但是你必須知道新的BST將與它共享所有的節點除了那些在新節點路徑上的節點（新BST中的指針將具有與舊節點中的指針相同的值），所以沒有節點的副本。 – Thomash

看看被接受的問題的答案。具體來說這條線的位置：

讓tree_of_list L = List.fold_right中插入L葉

工作發生了什麼事的鏈條。以列表1,2,3。

首先我們沒有樹並插入1 Leaf的結果。

呼叫此T1

下一步是通過嵌件2 T1

呼叫這個T2

然後生成的樹通過嵌件產生的樹3 T2

這就是返回作爲Tree_of_list的結果。

如果我們在代碼調用插件4別的地方調用結果T3則T3出現在結果沒有差異，從插入返回比調用Tree_of_list與列表1,2,3,4。

來源

2013-01-22 15:23:36 stonemetal

這就是我要說的。樹的初始創建和「稍後」之間沒有區別。在所有情況下，您都要保留一棵老樹，同時重新使用它的一部分來製作一棵新樹。使用這樣的不可變數據會對性能產生影響，但關於FP的令人驚奇的一點是，成本通常不高，而且效益顯着。 –

請參閱編輯。 @JeffreyScofield也請看看。 –

我會盡量回答你的問題的共享部分。簡單的答案是肯定的，兩棵樹的兩部分將是相同的。不變數據運作得如此之好的原因是，對可能的共享沒有限制。這就是FP運作如此順利的原因。

這裏有一個會議，做你的描述：

# let t1 = Node (10, Leaf, Leaf);; 
val t1 : int bstree = Node (10, Leaf, Leaf) 
# let t2 = insert 5 t1;; 
val t2 : int bstree = Node (10, Node (5, Leaf, Leaf), Leaf) 
# let t3 = insert 12 t2;; 
val t3 : int bstree = Node (10, Node (5, Leaf, Leaf), Node (12, Leaf, Leaf)) 
# let Node (_, c1, _) = t2;; 
val c1 : int bstree = Node (5, Leaf, Leaf) 
# let Node (_, c2, _) = t3;; 
val c2 : int bstree = Node (5, Leaf, Leaf) 
# c1 == c2;; 
- : bool = true

長的答覆是，沒有保證這兩個部分將是相同的。如果編譯器和/或運行時可以看到複製子樹的原因，那麼也可以自由地這樣做。有些情況下（如在分佈式處理中），這將是更好的選擇。 FP的重要之處在於共享沒有限制，這意味着在這種情況下共享既不是必需的也不是禁止的。

來源

2013-01-22 16:16:15

我能理解是這樣的：在我的代碼插入過程中，不需要改變任何附屬部分會因爲它們不改變共享，不違反計劃生育的不變法則。但是，如果一個子部分將在這個樹被改變（例如，新節點將被插入到樹的分支），則該子部分被返回爲新的節點，如下所示：如果x

分享部分的優秀答案。但我可以標記@stonemetal答案？因爲他的回答回答了主要部分。但謝謝傑弗裏。 –

我想說這是考慮它的好方法。同時你應該認識到OCaml是直截了當的：代碼或多或少只是做你說的。沒有什麼特別的工作可以讓分享發生。每一次id的出現都指向相同的（相同的）事物，這就是所有的事情。 –

在OCaml中構建二進制搜索樹的正確方法

回答

相關問題