Immutability in C# Part Seven: More on Binary Trees

re: Immutability in C# Part Seven: More on Binary Trees

Vadmyst — Thu, 20 Dec 2007 00:55:10 GMT

Great series!!

Tree traversal can also be done without using stack. For example, http://vadmyst.blogspot.com/2007/09/non-recursive-binary-tree-traversal.html. But, this approach makes tree node more "heavy" as additional information has to be used.

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Thu, 20 Dec 2007 01:54:36 GMT

In your approach how do you traverse the tree for a second time? All the nodes will be marked as visited.

I think what you want to do is store the "visited" information in a separate dictionary object which is owned by the traverser.

re: Immutability in C# Part Seven: More on Binary Trees

Dean Harding — Thu, 20 Dec 2007 03:41:06 GMT

You could make Visited an integer, incrementing it each time you visit a node.

Obviously, it also doesn't work for immutable trees :-)

re: Immutability in C# Part Seven: More on Binary Trees

Dean Harding — Thu, 20 Dec 2007 03:43:46 GMT

I should say "incrementing it each time you TRAVERSE THE TREE"...

re: Immutability in C# Part Seven: More on Binary Trees

Vadmyst — Thu, 20 Dec 2007 12:37:28 GMT

Dictionary approach seems to be better, in scenarios when traversing is done only with search purpose. In this case not all nodes will be visited and "visited" counter can be useless.

re: Immutability in C# Part Seven: More on Binary Trees

Gabe — Thu, 20 Dec 2007 18:02:40 GMT

Perhaps a nice feature of a future C# would be to allow a function to delegate the yield ability to some deeper function. That would allow you to write InOrder like this maybe:

public static IEnumerable<T> InOrder<T>(this IBinaryTree<T> tree) { yield tree.left.InOrder(); yield return tree.value; yield tree.right.InOrder(); }

Of course that's not a trivial feature to implement, but maybe someday C# will have continuations.

re: Immutability in C# Part Seven: More on Binary Trees

DRBlaise — Thu, 20 Dec 2007 21:29:18 GMT

The InOrder function should be checking against IsEmpty instead of null or Count > 0.

And speaking of null, it would be a nice feature to be able to specify that a variable of a class can not be set to null. This would simplify code so that we would not have to check that a value passed into a method is null because it would not be allowed by the compiler. This would require being able to identity a default value so that an array could be initialized. In the case of these immutible data structues, the default would of course by Empty.

re: Immutability in C# Part Seven: More on Binary Trees

Gabe — Thu, 20 Dec 2007 23:45:18 GMT

"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."

It's called F#.

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Fri, 21 Dec 2007 00:55:57 GMT

Whoops, that's what I get for modifying the code from another project and posting it without compiling it. Thanks for the note.

re: Immutability in C# Part Seven: More on Binary Trees

Yuval Gilboa — Tue, 25 Dec 2007 04:26:30 GMT

I've a small question unrelated to this immutables series, but I hope is still relevant for this blog:

Why did you not include generic properties/indexers in C#? Are you contemplating doing so in the "hypothetical future version of C#".

re: Immutability in C# Part Seven: More on Binary Trees

mattiasw — Thu, 27 Dec 2007 21:39:35 GMT

Why do we have to bother about "out-of-stack". Using the stack for recursion in trees are done in functional programming like F#, Lisp all the time.

The only datastructure too big to use the stack is lists and similar, which can be several thousand elements. Trees on the other seldom becomes deeper than 100 levels, especially if you use balanced trees like AVL or red-black trees.

re: Immutability in C# Part Seven: More on Binary Trees

Ifeanyi Echeruo [MSFT] — Sun, 30 Dec 2007 22:17:56 GMT

Stackless in-order binary tree traversal with left, right and parent pointers only

Off the top of my head and untested

class Node {

Node Parent;

Node Left;

Node Right;

Object Value;

}

class InOrderTreeWalk {

bool descendLeft;

Node current;

InOrderTreeWalk(Node start) {

this.descendLeft = true;

this.current = start;

}

bool moveNext() {

if(this.current == null) {

return false;

}

if(this.descendLeft) {

this.descendLeft = false;

while(this.current.left != null) {

this.current = this.current.left;

}

else {

if(this.current.right != null) {

this.current = this.current.right;

while(this.current.left != null) {

this.current = this.current.left;

}

else {

if(this.current.parent != null && this.current == this.current.parent.left) {

this.current = this.current.parent;

}

else {

while(this.current.parent != null && this.current == this.current.parent.right) {

this.current = this.current.parent;

}

if(this.current.parent == null) {

this.current = null;

}

return this.current != null;

}

object getValue() {

return (this.current != null) ? this.current.Value : null;

}

re: Immutability in C# Part Seven: More on Binary Trees

Smirnov — Tue, 01 Jan 2008 23:30:04 GMT

Note that in Ifeanyi's code you are still using an additional O(n) memory for the parent pointers vs Eric's b-tree implementation. A binary tree already takes up O(n) memory for n nodes though, so you could just add it together and get back O(n) total memory usage. This doesn't sound so bad in theory.

On the other hand, if you are using a balanced binary search tree, with recursion or explicit stack a traversal will only use O(log n) for extra memory. In practice it will then use less memory, as you'd have to run O(n/logn) traversals concurrently for it to actually use more.

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Wed, 02 Jan 2008 02:28:43 GMT

How are you going to build an immutable binary tree that has parent pointers?

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Wed, 02 Jan 2008 02:29:27 GMT

Note that "binary tree" and "b tree" are two entirely different data structures. "b tree" is NOT short for "binary tree".

Immutability in C#

Sat, 19 Jan 2008 00:05:11 GMT

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

re: Immutability in C# Part Seven: More on Binary Trees

Smirnov — Sun, 20 Jan 2008 04:59:03 GMT

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.

re: Immutability in C# Part Seven: More on Binary Trees

wesele — Thu, 14 Feb 2008 04:35:47 GMT

why?

current = stack.Peek();

stack = stack.Pop();

why not?

current = stack.Pop();

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Thu, 14 Feb 2008 05:16:17 GMT

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.

re: Immutability in C# Part Seven: More on Binary Trees

Eric Lippert — Thu, 14 Feb 2008 05:21:44 GMT

> 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.

re: Immutability in C# Part Seven: More on Binary Trees

Duarte Cunha Leão — Tue, 17 Jun 2008 16:23:55 GMT

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;

}