Trees

Consider a binary tree used for fast searching, where every node has the recursive invariant that subnodes on the left are less than the node, and subnodes on the right are greater than 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:

Figure: Original tree.

    

Figure: Modified tree.

The next diagram is persistent tree. Notice two points: Firstly the original tree ($xs$) persists. Secondly 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 $(GC)$ to automatically free up nodes which have no live references, and this is why $GC$ is a feature commonly found in functional programming languages.