There were two rb-tree related bugs kind of canceling each other.
Because they complemented each other so well, I don't know if I really fixed anything with this commit.
But it's under better control now.