关于Clojure中二进制搜索树的问题(不可变结构)

Question

我在编写用于从树中删除节点的代码时遇到了问题.

给定BST和键值,找到树中的键并删除它.

所以这是我的想法,首先,如果BST为零则返回nil,如果BST只有一个节点根,则返回nil.

然后,如果BST中的密钥与给定密钥匹配,请检查该节点具有的叶数.如果节点根本没有子节点,则从第一个前任(根)重新创建一个bst到该节点的最后一个前导,并共享不是前一个节点的所有其余数据.

如果节点有一个子节点,则将其视为没有子节点的节点,但只需将子节点添加到最后一个节点.

因为节点有两个孩子,我必须找到一些没有任何子节点的节点来替换它们的位置.

在编写代码时出现了困难的部分,我现在不知道如何重新创建和共享树的数据.

有人可以提供一些提示或线索吗？

Answer 1

在我看来，你几乎已经拥有它，但只需要一些细节方面的帮助。假设您有一些节点结构和以下可以对其进行操作的函数：

• (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。由于有两个孩子，我们需要以某种方式将它们组合成一棵树。如果您阅读了 Wikipedia 关于BST 删除 的内容，您基本上想要采用有序的前驱或后继（即左子树的最右节点，或右子树的最左节点）并将其设为新的根。选择哪一个并不重要——任何一个都可以。为了便于讨论，我们将选择左子树的最右边的节点。

现在我们可以编写一个新函数 ，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或给它一个合适的名称）。但希望这能让你开始。

买者自负： 我没有尝试测试这个答案中给出的代码。欢迎指正！