Red black tree implementation in c++

general
1

Hi guys,

Could any one point me to a good,simple implementation of red-black trees in c++ , which i can use in competitive coding as a general balanced binary tree. I am not particularly looking for template based implementations. Simple implementations with integer nodes(STRUCT) would do.

thanks

2

you can see the submissions of the questions with the above tag(and for all other algos) here…LINK…hope this helps…:slight_smile:

Edit:

mostly that tag is not present or maybe not added…u can see this link!!

1 Like
3

Use set or map in C++.Under the hood they’re red black trees with O(logn) insertion,deletion and find.

1 Like
4

Hey, you should check my answer on this question.
Quora

It contains implementation of augmented red black tree(i.e. node with size attribute) and its explanation.

If you want simple red black tree. Here’s its code
Ideone link

1 Like
5

Hm, I’ve thought of that. Could you please elaborate on the same…
I know i can give my own comparator function for a set.
Will I be able to modify the insert,search,delete operations to augment the structure? (as in an interval tree lets say)

6

The search,insert and delete operations will take place depending upon how you’ve implemented the comparator function.I don’t think we can augment a set or map using STL.I’d suggest using a skiplist.Which is very easy to implement as compared to a red-black tree.

7

Thanks…