Thread: Red Black Tree Implementaion

It seems like implementing an RB tree in C++ is a hell of a nightmare.
I have tried to look for an implementation online but couldn't find a good and clean one.

Is there anyone here who had this nightmare before and could share his code?

Thanks.

By the way, for those who wonder, it is a part of a work for university ( supposed to be a tiny part, but actually it's a serious burden V_V )

instead of looking for an implementation, I'd recommend looking for an explanation of how it works, and then write the implementation yourself.

If you just need to USE a red-black tree, not actually implement one yourself, the standard library has std::map and std::set, which are typically implemented as a balanced red-black tree (though other implementations would be valid; the standard doesn't specify how the implementation must work).

Originally Posted by Elkvis

instead of looking for an implementation, I'd recommend looking for an explanation of how it works, and then write the implementation yourself.

Yeah, it's not that it's hard or something, it's just a lot to write and many cases to handle which I find boring and frustrating...

Originally Posted by rcgldr

Is this homework (you're supposed to figure out to implement it), or is this something that university needs you to code up, even it's from some other example implementation?

The homework is to develop an algorithm that solves a specific problem. In order to solve it efficiently (as they demanded) I need to use a red black tree, meaning I need to implement it T_T

Originally Posted by Cat

If you just need to USE a red-black tree, not actually implement one yourself, the standard library has std::map and std::set, which are typically implemented as a balanced red-black tree (though other implementations would be valid; the standard doesn't specify how the implementation must work).

Wish I could do that, they want it to be 'clean' code, I can't use that stuff.

I find red-black trees harder to perform deletion with, and so-so for insertion.

As it seems that your requirements are not as strict as "use a red-black tree", but rather you feel that this would best meet the performance requirements, I strongly suggest you post what those performance requirements are. There are plenty of other data structures that are as performant, or more so, in many of the areas that a red-black tree is. We may be able to suggest a data structure that is easier to implement, and just as effective.

Originally Posted by iMalc

I find red-black trees harder to perform deletion with, and so-so for insertion.

As it seems that your requirements are not as strict as "use a red-black tree", but rather you feel that this would best meet the performance requirements, I strongly suggest you post what those performance requirements are. There are plenty of other data structures that are as performant, or more so, in many of the areas that a red-black tree is. We may be able to suggest a data structure that is easier to implement, and just as effective.

The question is on the chapter of rb trees XD unfortunately..
However, I think I'll just start to implement it hoping it'll go out well

Thanks