Red–black tree

Computers need smart ways to store and find information quickly. A red-black tree is a special tool used for this job. It is a type of binary search tree data structure. This means it organizes data into parts called nodes.

Each node holds a piece of information. In this tree, every node also has a color bit. This bit is either red or black. These colors help keep the tree balanced. A balanced tree is not too tall or lopsided. This ensures the computer can find data very fast.

The tree stays balanced by following strict rules. First, every node must be either red or black. All empty nodes, called null nodes, are considered black. Second, a red node cannot have a red child. Third, every path from a node to its empty leaves must have the same number of black nodes.

If you add or remove data, these rules might break. This is called a red-violation or a black-violation. To fix it, the tree performs rebalancing. The computer can change colors or move parts using rotations.

These steps keep the tree efficient.

History shows how these trees were discovered. In 1972, Rudolf Bayer invented a different structure called a B-tree. These trees were perfectly balanced but were not binary search trees. Later, in 1978, Leonidas J. Guibas and Robert Sedgewick derived the red-black tree from those B-trees. They wrote a paper called "A Dichromatic Framework for Balanced Trees." Interestingly, they chose the color red because it looked best on their laser printer.

They also had red and black pens available to draw them. In 1993, Arne Andersson later introduced a way to simplify the tree.

There are many important facts about how these trees work. The path from the top to the farthest leaf is never more than twice as long as the path to the nearest leaf. This keeps the tree height-balanced.

Because of this, searching takes time proportional to the height. In 1999, Chris Okasaki showed how to make the insert operation purely functional. Robert Sedgewick later showed that an insert could be done in just 46 lines of Java code. He even shortened this to 33 lines in 2008. These numbers show how efficient the math behind the tree can be.

You can see red-black trees working in things you might know. The Linux kernel uses them in its Completely Fair Scheduler and epoll system call. They are also used in the Java HashMap to help find items better.

They are also great for functional programming. This helps computers keep old versions of data even after changes are made. If you have ever used a computer to search a large list, a red-black tree might have helped find your answer. They turn a hard job into a very fast one.