3

我目前正在尝试在 clojure 中实现一个不可变的 BST。这是我的 make-tree 函数：

(defn make-tree [v] {:v v :l nil :r nil})

和插入：

(defn insert [tree v]
  (if (nil? tree)
    (make-tree v)
    (case (compare v (tree :v))
      -1 (assoc tree :l (insert (:l tree) v))
      0 tree
      1 (assoc tree :r (insert (:r tree) v)))))

问题是，这个插入函数会溢出类似的东西

(reduce insert (make-tree 1) (range 10000))

我知道我可以平衡树，这样我几乎不需要超过 1000 的深度。我仍然很好奇是否有定义函数以使其不会溢出。

由于可变版本只是修改节点，因此不需要存储父节点，这看起来很方便。

现实生活中你会选择什么？可变还是不可变？

4

2 回答 2

4

添加到A. Webb 的答案：

虽然需要在 CPS 中编写纯功能实现，但您可以将树实现为功能包装器 + 可变节点，其中修改将按如下方式进行：

  1. Wrapper 创建一个新的空根并告诉当前根执行修改并将结果放入新根中。

  2. 如果新根确定要修改自己的值，则将其子项复制到新根，将新值放入新根并返回。

  3. 否则，它将其值和不需要修改的分支复制到新根，并在新根中安装一个新的（空白）节点来代替确实（或者更确切地说，可能）需要修改的分支。

  4. 当前根告诉需要修改的分支修改自己，同时将新的空白节点交给它。

  5. 分支在重复步骤 2-5 时充当根。

  6. 包装器使用新根创建一个新包装器。新包装器作为顶级操作的结果返回。

上面第 2-5 点描述了一个递归过程，但它实际上是尾递归的，因此可以重写为循环。

在这一切完成之后，旧的包装器当然很好，并且仍然拥有相同的树（因为所有的突变只涉及新节点）。

事实上，许多 Clo​​jure 数据结构一直使用包含的可变性（主要涉及数组）。（虽然不是树形图；使用可变性的实际模式也不同，但是使用包含的可变性在内部加快速度同时在外部保持功能接口的基本前提是相似的。）

我还将添加两个切线注释：

首先，您的实现假设compare将返回 -1、0、1 之一，实际上可以自由地为“小于”返回任何负数，为“大于”返回任何正数（在我的 REPL 中(compare "foo" "bar")计算为4任何 JVM REPL，尽管确切的值再次未指定）。

其次，如果您对在 Clojure 中实现的自平衡树的真实示例感兴趣，您可能需要查看sorted.clj，它是 ClojurePersistentTreeMap和PersistentTreeSetClojure 中的实现。它基于 ClojureScript 实现，而后者又是 Clojure 的 Java 实现的一个端口。在这一点上，我会说它纯粹是实验性的1，但它似乎确实有效（通过了 CLJS 测试套件，完成了我在 REPL 中所期望的）并且可能作为简单 PDS 实现可能的示例有用看起来像在 Clojure 中。

1基本上在编写完 ClojureScript 实现之后，我想看看生成相同数据结构的 Clojure 实现需要多少额外的工作。很明显会有一些额外的工作，因为要实现 Java 接口，需要调整一些数组处理代码等，但我希望它不会加起来太多。我很高兴地报告，这一基本期望得到了经验的证实。性能方面，它并没有完全达到 Java 实现的标准（我似乎记得在大多数基准测试中减速了 1.5 倍，尽管我必须重新检查）；我希望最终能改善这一点，尽管此时 core.rrb-vector是性能调整的更高优先级。

于 2013-05-18T12:54:01.403 回答
3

您的实现不是自平衡的，您的示例是按顺​​序插入元素的最坏情况。堆栈溢出是由于深度递归造成的。为避免这种情况，您需要以延续传递样式重写算法，以便可以使用尾递归或创建显式展开堆栈，而不是隐式使用调用堆栈。

在现实生活中，Clojure 已经有一个不可变的自平衡树sorted-set和sorted-map，我会在大多数情况下使用它。Java 具有可变TreeMap属性，如果需要，您可以通过 Clojure 的 Java 互操作相当轻松地使用它。

(into (sorted-set) (range 10000))

于 2013-05-17T16:50:03.110 回答