Immutable Red-Black trees

[Craig Dillabaugh]

On Tuesday, 26 November 2013 at 00:28:34 UTC, bearophile wrote:
> Bartosz Milewski has written the second article about immutable 
> data structures in C++11, this time about Red-Black trees:
> http://bartoszmilewski.com/2013/11/25/functional-data-structures-in-c-trees/
>
> The C++11 code with few small changes (like using "enum class" 
> instead of "enum"):
> http://codepad.org/AEVVnfSc
>
> D has GC and transitive immutability, so I have tried a D 
> translation, a first draft:
> http://dpaste.dzfl.pl/a48452af3
>
> In the D code there are some problems with C++ lines as:
> return RBTree(Color::R, RBTree(), x, RBTree());
>
> And I don't know if this is public:
>     Color rootColor() const {
>
> Bye,
> bearophile

What do you mean by an 'immutable' data structure.  The linked 
article talks about Persistent data structures.  Are these the 
same thing?

When I saw "Immutable" I figured it didn't support 
insertion/deletion - which would sort eliminate the need for a 
Red-Black tree anyways.