Please note that this post has been created more than 3 months ago. It might contain inaccurate or stale (or both!) information. Use with caution!
A Red-Black tree is a binary search tree (BST) that takes some action to try and keep itself balanced. We know that BSTs are great at storing nodes identified by some key for which an order relationship exists (e.g., integers). They have the property that the values in the left sub-tree of each node _n_ have keys smaller-than _n_’s key
n.k, and those in the right sub-tree have keys greater-than