4 ms·

I didn't realize you could implement a red-black tree with this little code. The code shown here seems to indicate that insert has at least four cases, and del

I didn't realize you could implement a red-black tree with this little code. The code shown here seems to indicate that insert has at least four cases, and delete has six: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree https://en.wikipedia.org/wiki/Red%E2%80%93black_tree But the code I see here is very small: https://github.com/codr7/libcodr7/blob/master/source/codr7/rbnode.c https://github.com/codr7/libcodr7/blob/master/source/codr7/r... I guess it's not handling delete, which probably accounts for a lot of the difference. EDIT: I see that it's implementing a left-leaning red/black tree. I see some caution about that approach here? Would love to get the author's opinion about this: http://read.seas.harvard.edu/~kohler/notes/llrb.html http://read.seas.harvard.edu/~kohler/notes/llrb.html

hairtuq 7y ago
Red-black tree presentations are often more complicated than necessary, mostly because of (premature?) optimizations. A simple presentation can be found here: https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/redblack99.pdf https://www.cs.tufts.edu/~nr/cs257/archive/chris-okasaki/red... I haven't checked how this relates to the code in this library.
codr7 7y ago
You'll find delete on top of the todo list, it's more complex but not horribly so. I skimmed the link, but from what I can see there are no issues there that outweigh the significantly simpler code for me. This may very well change once I get more experience with them, time will tell.