Immutability in C# Part Seven: More on Binary Trees

Immutability in C# Part Seven: More on Binary Trees

Rate This
  • Comments 21

Lots of good comments on my previous post. To briefly follow up:

  • 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.
  • One smartypants pointed out that sure, this tree can have cycles -- if you have another binary tree implementation that has cycles and then paste such a cyclic tree in. True; what I meant was that using only the stated implementation, it's impossible to create a tree with cycles. If you are hell bent on making a bad tree, you can surely do that. Again, in a future post we'll have a tree which is built up by calling tree "mutating" operations, and those really will be guaranteed acyclic even in a world where there are other bad implementations hanging around.

And finally, 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). 

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(n2) 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;
    }
}

This consumes O(n) time, O(h) heap space, and O(1) call stack space. It is also painful to read and analyze compared to the slow naive implementation.

I would very much like to add new syntax to a hypothetical future version of C# which would be a syntactic sugar for the code above. If, hypothetically, we were prioritizing features for unannounced future versions of C#, unfortunately that one would not be our highest priority, so I wouldn't expect it any time soon. My colleague Wes has written a great article that goes into more details about the problem above and ways we might solve it in the future, so check that out if you want the details.

I have the code for the next few blog posts written, but odds are good that I'm not going to have time to write the surrounding text until after the festive holiday season is over. I hope you have a wonderful time during the remainder of 2007 and we'll see you bright and early in 2008 for more fabulous adventures!

  • For some reason, there's been a lot of buzz lately around immutability in C#. If you're interested in

  • I didn't realize that b-tree was an acronym for another data structure. I meant to say binary tree there.

    As for building immutable trees with parent pointers, I was not suggesting that, but pointing out that Ifeanyi's binary tree class has parent pointers, whereas Eric's binary tree class does not. The point was that including a parent pointer misleadingly looks like it uses less memory to traverse, when it actually grows at a faster rate than the stack usage.

  • why?

           current = stack.Peek();

           stack = stack.Pop();

    why not?

           current = stack.Pop();

  • Because stack.Pop() returns the popped stack.  Remember, it's an immutable stack; popping it does not change the stack, popping it returns you an entirely different object which represents the state of the popped stack.

    More generally, immutable data structures enable the abstract data type implementer to have every method do exactly one thing, which is good design.  Popping and peeking are two entirely different things. One creates a new data structure, the other inspects an existing data structure. So why should they be the same method?

    Because mutable stacks are, well, mutable, the implementer of the ADT must somehow work around the inability of callers to reason about the state of the data structure. For this reason, it is very common to see mutable data structures where one method does the work properly done by many different methods, in order to guarantee atomicity.

    This question has come up in almost every part of this series. See the comments to the other parts for more details.

  • > Why did you not include generic properties/indexers in C#?

    Is there a compelling customer scenario for doing so which cannot already be easily solved with a generic method? I am not aware of any, but I am happy to hear any such scenario you've got.  

    > Are you contemplating doing so in the "hypothetical future version of C#".

    Not at this time, no.  

  • Is there a compelling customer cenario for using properties, that cannot already be solved with a method??

    I am not aware of any, but I would be very happy if you would give us one.

    It's all a matter of syntax.

    What led to the creation of generic methods would also lead to the creation of generic properties.

    Yet, I agree that the syntax could become strange...:

    public interface IServiceContainer

       {

           bool     Contains<TService>();

           TService GetInstanceOf<TService>();

           void SetInstanceOf<TService>(TService oInstance);

           /* OR */

           TService Instance<TService> { get; set;}

       }

       public interface ISomeService

       {

       }

       public class Usage

       {

           public Usage()

           {

               IServiceContainer oContainer = null;// new ServiceContainer();

               /*

                * Configure the container

                * ...

                */

               ISomeService oService = oContainer.GetInstanceOf<ISomeService>();

               oContainer.SetInstanceOf<ISomeService>(oService);

               /* OR */

               ISomeService oService = oContainer.InstanceOf<ISomeService>;

               oContainer.InstanceOf<ISomeService> = oService;

           }

       }

Page 2 of 2 (21 items) 12