Building my own Custom Order-Statistic Tree using RB-Trees!

Revision en6, by Rajveer_100, 2022-05-09 15:52:00

Hey Guys! =========

I am really so happy to share my custom Order-Statistic Tree using Red Black trees, with the Select(x, i) and Rank(x)...which allow in finding the order statistic and the rank of the key element in log(n) time...

Now I do know that PBDS in C++ does exist, but as a challenge I built this..with great hardwork..and also took reference from CLRS which helped me in understanding the working of this data structure...

At first I actually encountered this problem in CSES named Josephus Problem, and that could be solved using Circular Doubly Linked Lists (in O(N) time) as well, but even O(NlogN) would suffice so I thought of doing so...A pretty fun experience in building own custom stuff, apart from the STL...

Also wanted the opinion of you guys, on how can I improve my work or further make some new functionalities to it in the future, or even build more such data structures allowing iterators like begin() and end() for the same..As far as the debugging part I have submitted the code as well just to be sure of any errors..

CSES Josephus Problem 2 -> Accepted Code

Thank You So Much!

Have a great day ahead!!!

Here is my Code in C++ :

Spoiler
Tags tree

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Rajveer_100 2022-05-09 15:52:00 1620 Added common functions like size(), lowerBound(), upperBound(), lessThan()...
en5 English Rajveer_100 2021-10-04 07:57:41 43
en4 English Rajveer_100 2021-10-03 16:39:53 14
en3 English Rajveer_100 2021-10-03 16:38:56 18
en2 English Rajveer_100 2021-10-03 16:34:35 446
en1 English Rajveer_100 2021-10-03 16:33:30 13044 Initial revision (published)