I've been reading up on some of the more advanced data structures, and I'm kinda stuck on the red-black tree concept.
I'm not able to grasp how the whole thing works. When I set out to implement it, I realized that I hadn't really "understood" anything about the RB tree other than the fact that it provides O(log n) operations.
- Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.
I find that rule very... unintuitive, Who would have thought of that? what's the rationale behind that?
These constraints enforce a critical property of red–black trees: that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf
How? I'm not really able to visualize how there constraints imply something even CLOSE to that.
So, could someone give me an intuitive description of the Red Black tree?