Structural Sharing in Clojure

Question

I'm unclear about structural sharing in Clojure. Below is a function xconj taken from the Joy of Clojure (Great book 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)}))

If one defines two trees t1 and t2 as shown below.

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

It is clear that the Left subtree is shared by t1 & t2

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

But if one were to create a new tree t3, by inserting a new value '1' in the left subtree of t1, like this:

(def t3 (xconj t1 1))

Will this result in a completely new tree with all values copied and no structural sharing, or will some structure still be shared? What if the left branch was bigger say 2->3->4->5->6->7(*root) and 1 was inserted in the left subtree, will then some sharing of structure persist?

Answer 1

The nodes on the path to the place where the new value is to be inserted will be replaced, but there are at least two things one ought to notice to get the whole story:

1. Replacing a non-nil node in the course of an xconj operation preserves one of its subtrees and its value; only one subtree is swapped out. (If you replace nodes along the path "left, left, left", then the node at position "left, left, right" is going to be shared.) Thus a lot of structure can potentially be shared even if all nodes along the path to one of the leaves are replaced.

2. The nodes being replaced are maps. If they were larger than just three keys, it would make sense to use assoc / assoc-in / update-in instead of building new maps:

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

   Than the new node map would be able to share structure with the old node map. (Once again, here it doesn't make sense because of how small the nodes are; but in different contexts this can make a huge difference.)