Структурный обмен в Clojure

Question

Я не уверен насчет структурного обмена в Clojure.Ниже приведена функция xconj, взятая из Joy of Clojure (Великая книга BTW).

;;Building a naive binary search tree using recursion
(defn xconj [t v]
      (cond 
          (nil? t) {:val v :L nil :R nil}
          (< v (:val t)) {:val (:val t) :L (xconj (:L t) v) :R (:R t)}
          :else {:val (:val t) :L (:L t) :R (xconj (:R t) v)}))

Если определить два дерева t1 и t2, как показано ниже.

(def t1 (xconj (xconj (xconj nil 5) 3) 2))
(def t2 (xconj t1 7))

Понятночто Левое поддерево является общим для t1 & t2

user> (identical? (:L t1) (:L t2))
true

Но если создать новое дерево t3, добавив новое значение '1' в левое поддерево t1, например:

(def t3 (xconj t1 1))

Приведет ли это к созданию совершенно нового дерева со всеми скопированными значениями и без совместного использования структуры, или некоторая структура все еще будет использоваться совместно?Что если левая ветвь была больше, скажем, 2-> 3-> 4-> 5-> 6-> 7 (* root) и 1 была вставлена ​​в левое поддерево, сохранится ли некоторое разделение структуры?

Answer 1

Узлы на пути к месту, где должно быть вставлено новое значение, будут заменены, но есть как минимум две вещи, на которые следует обратить внимание, чтобы получить всю историю:

1. Замена не-1005 * узла в ходе операции xconj сохраняет одно из его поддеревьев и его значение; выгружается только одно поддерево. (Если вы замените узлы вдоль пути «влево, вправо, влево», то узел в позиции «влево, вправо, влево» будет использоваться совместно.) Таким образом, многие структуры потенциально могут совместно использоваться, даже если все узлы вдоль путь к одному из листьев заменен.

2. Заменяемые узлы являются картами. Если бы они были больше трех ключей, имело бы смысл использовать assoc / assoc-in / update-in вместо создания новых карт:

   ...
   (< v (:val t)) (update-in t [:L] xconj v)
   ...
   

   Чем новая карта узлов сможет разделить структуру со старой картой узлов. (Еще раз, здесь это не имеет смысла из-за того, как маленькие узлы; но в разных контекстах это может иметь огромное значение.)