Clojure:如何生成 'trie' ？

Question

鉴于以下情况...

(def inTree
 '((1 2)
   (1 2 3)
   (1 2 4 5 9)
   (1 2 4 10 15)
   (1 2 4 20 25)))

你如何将它转换成这个特里树？

(def outTrie
 '(1
    (2 ()
       (3 ())
       (4 (5
            (9 ()))
          (10
            (15 ()))
          (20
            (25 ()))))))

Answer 1

这是一个清理后的解决方案。这修复了 Brian 的 add-to-trie 方法的错误，因为它当前依赖于您以长度递增的顺序插入 seq。它还允许通过前缀查询 trie，这是一种常见的用例。

请注意，此处的内存使用量较高，因为它将值存储在 trie 的叶节点中，以便您可以执行搜索。

(defn add-to-trie [trie x]
  (assoc-in trie x (merge (get-in trie x) {:val x :terminal true})))

(defn in-trie? [trie x]
  "Returns true if the value x exists in the specified trie."
  (:terminal (get-in trie x) false))

(defn prefix-matches [trie prefix]
  "Returns a list of matches with the prefix specified in the trie specified."
  (keep :val (tree-seq map? vals (get-in trie prefix))))

(defn build-trie [coll]
  "Builds a trie over the values in the specified seq coll."
  (reduce add-to-trie {} coll))