關於Clojure中二叉搜索樹的問題（不可變結構）

我在編寫從樹中刪除一個節點的代碼時遇到了問題。關於Clojure中二叉搜索樹的問題（不可變結構）

給出一個BST和一個鍵值，找到樹中的鍵並刪除它。

所以這裏是我的想法，首先，如果BST是零，則返回零，如果BST只有一個節點的根，則返回零。

然後如果BST中的密鑰與給定密鑰匹配，請檢查此節點具有的葉數。如果該節點根本沒有子節點，則從第一個前驅（根）到該節點的最後一個前驅重新創建一個bst，並共享所有不是前驅的其餘數據。

如果節點有一個孩子，則視爲沒有孩子的孩子，但只是將孩子添加到最後的前任。

爲節點有兩個孩子，我必須找到沒有任何孩子來代替他們的位置，一些節點。

編寫代碼時出現了困難的部分，我現在真的不知道如何重新創建和共享樹的數據。

所以有人可以提供一些提示或線索？

來源

2013-11-25 Landey

你有沒有考慮過拉鍊？ –

@lgrapenthin，你的意思是使用拉鍊來存儲信息？ – Landey

我真的不知道如何在共享數據時重新創建樹。 @lgrapenthin – Landey

它看起來像我，你幾乎有它，但只需要一點幫助的細節。所以我們可以說你有一些節點結構和以下功能操作就可以了：

(left-subtree [node]) - 返回node左子樹，或nil如果node沒有左子樹
(right-subtree [node]) - 返回node右子樹，或者nil，如果node沒有右子樹。
(value [node]) - 返回與node
(leaf? [node])相關聯的值 - 返回true如果node是葉，否則false。

現在讓我們寫一個without-root功能，需要一個（子）樹，並返回一個包含原樹一切，除了它的根節點的新樹：

(defn without-root [node] 
    (cond (leaf? node) nil ; resulting tree is the empty tree, return nil 
     (and (left-subtree node) ; two children, "difficult" case 
      (right-subtree node)) (handle-difficult-case node) 
     ;; cases for single child 
     (left-subtree node) (left-subtree node) 
     (right-subtree node) (right-subtree node)))

正如你在問題中的狀態，「難」情況是當node有兩個孩子。所以我決定把它分成一個單獨的函數來促進討論。

那麼讓我們來談談handle-difficult-case。由於有兩個孩子，我們需要將它們組合成一棵樹。如果您閱讀維基百科關於BST Deletion的說法，您基本上想要選擇有序的前任者或後繼者（即左子樹的最右側節點或右子樹的最左側節點），並使其成爲新的根。你選擇哪一個並不重要 - 任何一個都可以。爲了這個討論，我們將選擇左子樹的最右邊的節點。

現在我們可以編寫一個新函數without-rightmost-node，它接受一棵樹並返回一棵沒有最右邊節點的新樹。但是，我們也需要存儲在該節點中的值。所以我們要麼需要獨立地調用一些find-rightmost-node函數來獲取它的值（這將是低效的），或者返回值和新樹（這會混淆函數的用途）。

而是讓我們編寫一個函數，接受一棵樹並返回一個等價於原始樹的新樹，除了它的根是原始樹的最右邊的節點。爲了好玩，我們調用這個函數percolate-rightmost-node，因爲我們將會看到，最右邊的節點將遞歸地「冒泡」到（子）樹的頂部。

(defn percolate-rightmost-node [node] 
    (if-let [right-side (right-subtree node)] 
    ;; then (recurse down the right side) 
    (let [percolated (percolate-rightmost-node right-side)] 
     ;; Construct a new tree from the result. 
     (with-left-subtree percolated 
         (with-right-subtree node (left-subtree percolated)))) 
    ;; else (we are at the rightmost node -- return it!) 
    node))

我覺得像if-let表達的「那麼」面還不是很清楚，所以讓我解釋一點。基本上，我們取percolated子樹，得到它的左子樹（這是percolated的唯一子），並將其替換爲node的右子樹。然後，我們取這個結果，並替代percolated的左子樹（有效地重新生根樹），產生最終結果。

percolate-rightmost-node的輸出將只有一個左子樹 - 它永遠不會有一個正確的子樹。所以在結果結束「冒泡」之後，我們只需要給它一個正確的子樹。因此，我們可以執行handle-difficult-case爲：

(defn handle-difficult-case [node] 
    (let [percolated (-> node   ; Find the rightmost node of the left 
         (left-subtree) ; subtree and "percolate" it to the top 
         (percolate-rightmost-node))] 
    ;; Now take the percolated tree. Its right subtree is empty, 
    ;; so substitute in the right subtree of node. 
    (with-right-subtree percolated 
         (right-subtree node))))

而且應該是這樣。當然，您需要將其適用於您的代碼（至少要嵌入handle-difficult-case或給它一個合適的名稱）。但希望能讓你開始。

注意事項：我沒有試圖測試此答案中給出的代碼。歡迎更正！

來源

2013-11-26 19:07:09

這將是一個很長的答案，所以請讓我提前指點你對一本書，並沒有直接回答道歉。我強烈建議您查看Purely Functional Data Structures，這是（作爲合法的）來自作者的PDF格式。無論如何，這是一本很好的書，在print/ebook。

超級簡短的答案是使用Clojure的內置sorted-map，如果你想在實踐中這樣做（儘管編寫你自己的意志當然會得到nerd-street-cred），因爲已排序的地圖在罩下使用二進制紅黑樹

來源

2013-11-25 22:56:31

關於Clojure中二叉搜索樹的問題（不可變結構）

回答

相關問題