Massive Algorithms: Immutable Binary Tree

Immutability in C# Part Six: A Simple Binary Tree
here's no obvious "insert" operation in a binary tree, so we'll just leave it up to the implementer.

public sealed class BinaryTree<V> : IBinaryTree<V>
{
    private sealed class EmptyBinaryTree : IBinaryTree<V>
    {
        public bool IsEmpty { get { return true; } }
        public IBinaryTree<V> Left { get { throw new Exception("Empty tree"); } }
        public IBinaryTree<V> Right { get { throw new Exception("Empty tree"); } }
        public V Value { get { throw new Exception("Empty tree"); } }
    }
    private static readonly EmptyBinaryTree empty = new EmptyBinaryTree();
    public static IBinaryTree<V> Empty { get { return empty; } }

    private readonly V value;
    private readonly IBinaryTree<V> left;
    private readonly IBinaryTree<V> right;

    public bool IsEmpty { get { return false; } }
    public V Value { get { return value; } }
    public IBinaryTree<V> Left { get { return left; } }
    public IBinaryTree<V> Right { get { return right; } }
    public BinaryTree(V value, IBinaryTree<V> left, IBinaryTree<V> right)
    {
        this.value = value;
        this.left = left ?? Empty;
        this.right = right ?? Empty;
    }
}

Note that another nice feature of immutable data structures is that it is impossible to accidentally (or deliberately!) create a tree which contains a cycle. In a mutable tree you could do something stupid like making the root a child of one of the leaves (or, for that matter, a child of itself!) Then you have to either live with the possibility that a user will create a cyclic "tree" and hope for the best (or, in other words, crash and/or hang) or you have to build yourself a cycle detector. Cycle detectors have potentially serious performance implications. It may be best to simply prevent the situation from arising in the first place.

A feature conspicuous by its absence from the above implementation is enumeration. Unlike a stack or a queue, there's no obvious best order in which to enumerate the members a binary tree. First off, there's the question of whether to enumerate in depth-first or breadth-first order, and then the matter of whether the parent comes before, after or between the children.

public static IEnumerable<V> InOrder<V>(this IBinaryTree<V> tree)
{
    // BAD IMPLEMENTATION, DO NOT DO THIS
    if (tree.IsEmpty) yield break;
    foreach(V v in tree.Left.InOrder()) yield return v;
    yield return tree.Value;
    foreach(V v in tree.Right.InOrder()) yield return v;

}

one reader correctly identified the problem with my recursive implementation of in-order iteration. A tree of maximum height h ends up allocating O(h) iterator objects. The recursive calls get O(h) deep. If h is very large, this could blow the call stack. And if the tree has n nodes, each with an average height of O(h), then iterating each node will require O(h) recursive calls apiece. Therefore the total time cost in calls for iterating the entire tree is O(n h).

http://blogs.msdn.com/b/ericlippert/archive/2007/12/19/immutability-in-c-part-seven-more-on-binary-trees.aspx

One of the downsides of immutable tree implementations is that usually the tree must be built from the leaves up, which is not always convenient. We'll look at implementations which hide this fact from the user in future posts.

In a binary tree with n nodes, h is always between log n and n, so that means that this iterator has best case asymptotic performance of O(n log n) and worst case of O(n²) in time, and uses between O(log n) and O(n) in both call stack and heap space. That's pretty lousy.

A better implementation would be to write a tree traversal algorithm which does not use recursion. Use an explicit stack rather than the call stack:

public static IEnumerable<T> InOrder<T>(this IBinaryTree<T> tree)
{
    IStack<IBinaryTree<T>> stack = Stack<IBinaryTree<T>>.Empty;
    for (IBinaryTree<T> current = tree; !current.IsEmpty || !stack.IsEmpty; current = current.Right)
    {
        while (!current.IsEmpty)
        {
            stack = stack.Push(current);
            current = current.Left;
        }
        current = stack.Peek();
        stack = stack.Pop();
        yield return current.Value;
    }
}

TODO

http://mikefroh.blogspot.com/2011/03/immutable-binary-trees.html

the advantages you can get in a concurrent execution environment by using immutable data types (or persistent data structures).

In total, four new nodes were allocated: one for each level in the tree. For a balanced tree, this generalizes to O(log n) node allocations, or the same runtime efficiency of a mutable binary tree. The remainder of the tree continues to point to the old values. Assuming we aren't holding onto a reference to the old tree root, the original 8, 13, and 10 nodes would now be eligible for garbage collection. (Though if another thread were accessing the old version of the tree, it would not be affected by this change, avoiding a potential race condition.)

http://mikefroh.blogspot.com/2011/03/immutable-binary-trees-part-2.html

immutable-binary-search-trees
http://community.schemewiki.org/?immutable-binary-search-trees
TODO:
Immutable Hash Trie Maps in Java
http://mikefroh.blogspot.com/2012/06/immutable-hash-trie-maps-in-java.html

http://mcherm.com/permalinks/1/immutable-trees-and-threading-evil-part-1