question about red black tree coloring

[dotnwat]

The port to C++ I've made of the red-black tree is working perfectly with a range of tests. While I was porting, I ran across a operation in the Rust implementation that raised a question for me.

It's in reference to make_black and make_red. These two methods appear to be modifying the color of an existing node, rather than returning a copy of a node with a new color. At least that's how I'm reading the Rust code, but I'm by no means very comfortable in the language.

https://github.com/orium/rpds/blob/master/src/map/red_black_tree_map/mod.rs#L166

In my port I made Node be fully immutable, such that make_black and make_red return copies with only the color modified. I have not encountered any issue, but it occurs to me that perhaps there is an inefficiency that results by breaking some structure sharing in the underlying tree.

I was hoping you could perhaps comment on those methods and their semantics / role in the algorithm.

Best, Noah

[dotnwat]

Although now I look at it again and realize that perhaps node is actually a mutable copy of self, and I just assumed it was a mutable pointer/reference to self. Could you clarify?

        let mut node = self;
        node.color = Color::Red;
        node

[orium]

In rust a function like fn foo(self) is said to receive self by move (ref1, ref2). This means that the original value will no longer be accessible in the caller scope and no reference to this node exists anywere. This is ensured statically by the rust compiler.

So, these methods do not take a reference, they take the value itseft with the guarantee that that value is not referenced by anyone (otherwise we would not be able to move it), change the value, and return it. (It would also be possible to receive a mutable reference and change the color, since rust's borrow system would also ensures no other reference to the node exists.)

If you look at places you will find that we clone() the node when the original node is being referenced by the original tree (https://github.com/orium/rpds/blob/master/src/map/red_black_tree_map/mod.rs#L689); and that we do not apply clone() when we have ownership of the node (https://github.com/orium/rpds/blob/master/src/map/red_black_tree_map/mod.rs#L853).

Let me know if you need any further clarification. Also, if you feel that the kind of guarantees that rust statically gives are amazing I highly recommend this talk.