Red-Black Tree
A red-black tree is a self-balancing binary search tree in which each node carries an extra bit of information — its color (red or black) — and the tree satisfies a set of coloring rules that ensure the tree remains approximately balanced. Introduced by Rudolf Bayer in 1972 and further developed by Leonidas Guibas and Robert Sedgewick in 1978, it guarantees O(log n) worst-case performance for search, insert, and delete. Red-black trees are widely used in language standard libraries, including C++ STL's map and Java's TreeMap.
Red-Black Tree Properties and Rules
| Rule | Description | Implication |
|---|---|---|
| Rule 1 | Every node is red or black | Binary coloring constraint |
| Rule 2 | Root is always black | Establishes tree anchor |
| Rule 3 | Red nodes cannot have red children | No two consecutive reds |
| Rule 4 | All paths from node to leaves have equal black-height | Ensures balance |
| Rule 5 | Null leaves are considered black | Simplifies rule 4 checking |
Interactive Tools
Wikimedia Commons, CC BY-SA
Related Terms
AVL Tree
An AVL tree is a self-balancing binary search tree in which the difference in heights between the left and right subtrees (the balance factor) of any node is at most 1. Named after its inventors Adelson-Velsky and Landis (1962), it was the first self-balancing BST ever invented. The tree automatically performs rotations (single or double) during insertions and deletions to maintain balance, guaranteeing O(log n) time for all operations.
Binary Search Tree
A binary search tree (BST) is a binary tree in which every node satisfies the property that all keys in its left subtree are less than the node's key and all keys in its right subtree are greater. This ordering property makes search, insertion, and deletion operations efficient, averaging O(log n) for balanced trees. BSTs are foundational in database indexing, symbol tables, and dynamic set operations.
Binary Tree
A binary tree is a hierarchical data structure in which each node has at most two children, referred to as the left child and the right child. It is one of the most fundamental structures in computer science, forming the basis for more specialized trees like binary search trees and heaps. Binary trees are widely used in expression parsing, Huffman coding, and database indexing.
The term "red-black tree" was coined by Leonidas Guibas and Robert Sedgewick in 1978. The choice of colors is said to be due to the red and black pens available on a laser printer at the time, though some sources attribute it to aesthetic preference. Rudolf Bayer originally called the structure a "symmetric binary B-tree" in 1972.