Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

Delay's Blog : Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

Wed, 03 Jun 2009 04:36:29 GMT

PingBack from http://blogs.msdn.com/delay/archive/2009/06/02/maintaining-balance-a-versatile-red-black-tree-implementation-for-net-via-silverlight-wpf-charting.aspx

Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)] - Delay's Blog

DotNetShoutout — Wed, 03 Jun 2009 14:36:13 GMT

Thank you for submitting this cool story - Trackback from DotNetShoutout

re: Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

obsid — Thu, 04 Jun 2009 08:38:56 GMT

You know it would be nice if we could “automatically” use these kinds of cool algorithms just by using an OrderedDictionary. Clearly the current OrderedDictionary works great for reading values/keys, but horrible for insert/delete or memory size. Be nice if there was say a way to do

var myDictionary = new OrderedDictionary(0,1,0, 10000);

Where there is an overload of the constructor that would have PerfMemory, PerfRead, PerfWrite, and PerfSize; expecting a float between 0 and 1 for each other then perfsize which is an estimated size. In the case above, I do almost all read operations and don’t care about memory or insert/delete and expect about 10000 items. Based on which things are important, it would select an algorithm that would be good for that situation. Most (good) algorithms involve tradeoffs between situations which value each of the above types differently. In this way, rather than selecting the algorithm that will be used, the programmer is just expressing the important of various perf goals.

re: Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

Delay — Fri, 05 Jun 2009 03:05:50 GMT

obsid,

This is an interesting idea! I'm not sure how practical I think it is to try to collapse what can sometimes be pretty complicated performance decisions into a just 4 parameters, but I see your point and think this might not be so hard at the low end (i.e., for simpler scenarios). I'll pass this on to a couple of folks I work with to see what they think. Thanks very much for the feedback!

re: Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

Delay — Sat, 06 Jun 2009 03:07:55 GMT

obsid,

I passed this on to someone internally, and their reaction was similar to mine. :) The suggestion was to create an issue for this Connect (http://connect.microsoft.com/) so that other customers can see it and vote for it. If enough people start asking for this, that will increase its chances of being incorporated into a future version of .NET.

Hope this helps! :)

re: Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

hintzen — Thu, 18 Jun 2009 23:58:45 GMT

Have you looked at using a SkipList instead of a binary tree?

http://en.wikipedia.org/wiki/Skip_list

It has efficiecny right up there with binary tree (number of probes proportional to log n) with super fast insert / delete / implementation.

I really don't understand why SkipList is not looked as as the first alternate for BinaryTrees, Microsoft sponsered the original work on this theory I believe.

re: Maintaining balance [A versatile red-black tree implementation for .NET (via Silverlight/WPF Charting)]

Delay — Fri, 19 Jun 2009 05:14:30 GMT

hintzen,

I'd been only peripherally aware of skip lists before reading that article - thank you very much for sharing it! The ideas there sound interesting and the claim that skip lists are simpler than competing data structures is worth looking into. In our case with Charting, because we already had code that was working with a binary tree, switching to a red-black tree seemed like a pretty simple and risk-free move. The code for the left-leaning red-black tree ended up being relatively compact, so I'd be interested to see how a skip list implementation compares. At any rate, if we end up revisiting this decision some day, I'll definitely give skip lists some consideration.

Thanks again!