Red black trees

Frits van Bommel fvbommel at REMwOVExCAPSs.nl
Thu Oct 26 17:26:40 PDT 2006


Walter Bright wrote:
> Frits van Bommel wrote:
>> Well, I suppose the user is likely to be some library class anyway:
>>
>> struct Tuple(Key, Value) { ... }
>>
>> class Map(Key, Value) : RedBlackTree!(Tuple(Key, Value)) {
>>     // Some extra methods
>> }
> 
> I use associative arrays, and I never use them like that <g>.

Well, that's not ideal code obviously, but it was shorter to type into 
my newsreader :P. You get the idea, you can use RedBlackTrees with a 
special value type to implement maps.

 > They
> always have a key/value. Shouldn't rbtrees be simply an alternate 
> container that has the same interface, but has different operating 
> characteristics?

I myself never considered RedBlackTrees as associative arrays, just as a 
data structure that can be used to implement them. But also to implement 
sets (or bags (multisets) and multimaps if you allow duplicates).

>> Will you at least consider something like this:
>>
>>>> Though you could also allow Value to be void and specialize the node 
>>>> type for that so it doesn't contain a Value in that case. Maybe even 
>>>> make void the default type for Value?
> 
> You could do that, though I'd call the result something else (like the 
> Set type you mentioned).

But I think it should be possible to implement a Set using a 
RedBlackTree without wasting space in the nodes.

And I think the code wouldn't be so much different, so a few 'static 
if(is(Value == void))' would likely avoid quite a bit of code duplication.



More information about the Digitalmars-d mailing list