Complexity and Applications of Red–Black Trees
There's really nothing new here—because a Red–Black tree is a specific way of representing a 2–3–4 tree, operations on Red–Black trees have the same cost (within constant factors) as their corresponding 2–3–4 trees!
std::set and std::map
Because of of their good worst-case complexity, Red–Black trees are commonly used to implement standard C++ data structures such as std::set and std::map.
What do you mean, “commonly”?
The C++ standard does not mandate any specific implementation for
std::setorstd::map. It just says that they have to have certain properties and provide certain operations.
In practice, every popular C++ compiler implements
std::setandstd::mapusing a Red–Black tree.-
But in principle they could pick a different kind of balanced tree, such an an AVL tree or a AA tree.
Meh. Do I need to care about those other techniques, especially if no one bothers to use them these days?
-
No, not really. But it's good to know that the standard doesn't mandate a specific implementation.
Completely Fair Scheduling
Red–Black trees also have an important role in the Linux kernel.
When you are running lots of jobs on one CPU, the operating system has to decide how to divvy up processor time to the different tasks. That can be tricky because sometimes you give CPU time to a job but it can't use it because it's waiting for the disk or for user input or for some other slow resource. You want to put that process back in line to wait for the CPU again, but maybe you don't want it to wait for a super long time; you want it to have access to the CPU when it is finally ready to use it.
Linux uses an algorithm called the “Completely Fair Scheduler”, which stores process information in… a Red–Black tree! The keys in the tree are the amount of time that a process has had with the CPU. The tree structure makes it easy to find the process with the smallest amount of CPU time that is also currently ready to use the CPU.
(When logged in, completion status appears here.)