Red-black trees are similar to binary search trees with a new parameter for every node, the color of that node.
The color of the node can be either red or black. So, the data structure needed for red-black tree nodes contains a key value, a color, the reference to a parent, and the references to the left and right child.
Red-black trees need to satisfy the following color conditions:
Every node must have a color red or black
The root is black
All the NULL/nil leaves are black
For any red node, both children are black
For each node, all simple paths from the node to descendant leaves contains the same number of black nodes
Red-black tree data structure
Because of color condition number five (see the preceding figure), red-black trees offer worst-case guarantees for key operations such as search, insertion, and deletions that are proportional to its tree height. Unlike regular binary search trees, this makes red-black trees a great candidate to be used in real-time processes and applications...
