Red–black tree

Computers use special trees to store information.

These trees use red and black colors. Each part of the tree is one color. The colors help keep the tree even.

If the tree gets messy, the computer changes the colors. It can also move the parts around. This keeps the tree balanced. A balanced tree helps the computer work fast. It makes finding things very quick.

Computers use these trees to stay organized.

Computers use special tools to store and find information quickly. One tool is called a red-black tree.

A red-black tree is a type of binary search tree. It is a way to organize data in parts called nodes. Each node holds a piece of information. In this tree, every node also has a color. The color is either red or black.

The colors help keep the tree balanced. A balanced tree is not too tall or lopsided. This helps the computer find things fast. The tree follows strict rules. For example, a red node cannot have a red child. Also, every path from the top to the bottom must have the same number of black nodes.

When you add or remove information, the tree might break these rules. To fix it, the computer uses a set of steps called rebalancing. It can change the colors of the nodes. It can also move parts around using a way called rotation.

These trees are very useful. They help the Linux kernel work well. They are also used in the Java HashMap to make searching better.

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.

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.