Complexity
What is the runtime complexity of node insertion? A Red-Black tree of n internal nodes has height at 2*log(n+1).
This means that operations, such as searching for a node, have logarithmic time. The insertion operation we just saw is also proportional to the height of the tree.
When we insert a new node and violate the second invariant, we fix it and always color the subtree's root red. This could create further invariant violation upward in the tree.
However, as the height is at most 2*log(n+1), the insertion operation has a runtime complexity of O(logn). So, for example, for a tree with 4294967296 nodes, which is 232, we have to perform up to 32 invariant fixes. This is a very good number, making Red-Black trees one of the most popular variants of Binary Search Trees.
Linux's completely fair scheduler uses Red-Black trees. See http://www.ibm.com/developerworks/library/l-completely-fair-scheduler/ for more information.
Java 8's TreeMap is implemented using Red-Black trees. See https...
