Red–black tree

A red-black tree is a sophisticated self-balancing binary search tree data structure. It is used in computer science for the fast storage and retrieval of ordered information. In a standard binary search tree, data is organized into nodes. However, if data is added in a specific order, the tree can become lopsided or "unbalanced." An unbalanced tree is slow to search. To prevent this, red-black trees use an extra "color" bit for each node. This bit is either red or black. These colors act as a guide to keep the tree approximately balanced.

The tree maintains its shape by following four strict structural rules. First, every node must be either red or black. Second, all null nodes, which are the empty spaces at the end of branches, are considered black. Third, a red node cannot have a red child. This means you can never have two red nodes in a row vertically. Fourth, every path from a given node to any of its descendant null nodes must pass through the same number of black nodes. This constant number is known as the black height.

When you modify the tree by inserting or deleting data, these rules might be broken. A violation of the third rule is called a red-violation. A violation of the fourth rule is called a black-violation. To fix these issues, the tree performs a process called rebalancing. This process involves two main actions: recoloring and rotation. Recoloring changes the color bits of specific nodes. Rotation moves the nodes around to change the tree's structure while keeping the data in the correct order.

Rebalancing is very efficient. It requires no more than three rotations for an insertion.

The history of this structure is tied to earlier mathematical discoveries. In 1972, Rudolf Bayer invented the B-tree, which was a special order-4 case of a data structure. B-trees were perfectly balanced but were not binary search trees. In 1978, Leonidas J. Guibas and Robert Sedgewick derived the red-black tree from these symmetric binary B-trees. They published their work in a paper titled "A Dichromatic Framework for Balanced Trees." The choice of the color red was quite practical. The authors chose it because red looked best on the color laser printers available at Xerox PARC. They also noted that red and black pens were simply what they had available to draw their diagrams.

Red-black trees are highly significant because they guarantee efficient performance. The rules ensure that the path from the root to the farthest leaf is no more than twice as long as the path to the nearest leaf. This property makes the tree height-balanced. Because of this balance, searching, inserting, and deleting all happen in logarithmic time. This means the time required grows very slowly even as the number of entries increases. In 1993, Arne Andersson introduced the right-leaning tree to simplify operations. Later, in 2008, Robert Sedgewick proposed the left-leaning red-black tree. This version uses Andersson's ideas to make the code even simpler. Sedgewick showed that an insert operation could be written in just 46 lines of Java. He later reduced this to only 33 lines of code.

These trees are closely related to 2-3-4 trees. A 2-3-4 tree is a type of B-tree where each node can contain between one and three values. In a red-black tree, these groups are represented by a black node and its red children. For example, a 2-node maps to a single black node. A 3-node maps to a black node with one red child. A 4-node maps to a black node with two red children.

While 2-3-4 trees are perfectly balanced, red-black trees are more economical to use. This is because red-black trees are simple binary trees and do not need to manage complex variable-length vectors.

Today, red-black trees are used in many essential computer systems. The Linux kernel uses them in the Completely Fair Scheduler and the epoll system call. In the Java programming language, the HashMap uses red-black trees to handle cases where different elements have colliding hashcodes. This improves the time complexity of searching for those elements. They are also very important in functional programming. In this field, they are used to build "persistent" data structures. These allow a computer to keep old versions of data even after it has been changed. By providing fast, guaranteed performance, red-black trees serve as a vital building block for modern technology.