Sure, it might be that only a tree based structure is able to fulfill the required complexity, but it doesn't need to be a RB one necessarly.

On programming languages with ISO/ANSI specifications, relying on implementation details is a trap for writing portable code.