Editing Persistent data structure (section)

===Trees===
Consider a [[binary search tree]],<ref name="auto"/> where every node in the tree has the [[Recursion|recursive]] [[Invariant (computer science)|invariant]] that all subnodes contained in the left subtree have a value that is less than or equal to the value stored in the node, and subnodes contained in the right subtree have a value that is greater than the value stored in the node.

For instance, the set of data
 xs = [a, b, c, d, f, g, h]
might be represented by the following binary search tree:

[[File:Purely_functional_tree_before.svg]]

A function which inserts data into the binary tree and maintains the invariant is:<syntaxhighlight lang="ocaml">
 fun insert (x, E) = T (E, x, E)
   | insert (x, s as T (a, y, b)) =
        if x < y then T (insert (x, a), y, b)
        else if x > y then T (a, y, insert (x, b))
        else s
</syntaxhighlight>After executing
 ys = insert ("e", xs)
The following configuration is produced:

[[File:Purely_functional_tree_after.svg]]

Notice two points: first, the original tree (<code>xs</code>) persists.  Second, many common nodes are shared between the old tree and the new tree. Such persistence and sharing is difficult to manage without some form of [[Garbage collection (computer science)|garbage collection]] (GC) to automatically free up nodes which have no live references, and this is why GC is a feature commonly found in [[Functional programming|functional programming languages]].

==== Code ====
GitHub repo containing implementations of persistent BSTs using Fat Nodes, Copy-on-Write, and Path Copying Techniques.

To use the persistent BST implementations, simply clone the repository and follow the instructions provided in the README file.<ref>{{github|DesaultierMAKK/PersistentBST}}</ref>