Red–black tree

A red–black tree is a binary search tree whose red and black node colors obey invariants that keep its height logarithmic in the number of nodes.

Binary search tree: A binary tree in which each node’s keys are ordered relative to the keys in its left and right subtrees. Red–black trees retain this ordering while adding color constraints to control height.
Binary tree: A tree data structure in which each node has at most two children. The red–black structure is a constrained binary tree.
AVL tree: A self-balancing binary search tree that tightly limits the height difference between each node’s subtrees. AVL trees enforce stricter balance, often favoring lookups over update simplicity.
Associative array: A data structure that maps keys to values and supports lookup, insertion, and deletion by key. Red–black trees can implement ordered associative arrays with logarithmic operations.
Rudolf Bayer: A German computer scientist who introduced a balanced multiway search-tree structure later connected to red–black trees. Bayer’s symmetric binary B-tree supplied an early basis for the color-based representation.
Tree rotation: A local restructuring of a binary search tree that changes parent-child links while preserving key order. Rotations repair shape after updates without changing the search-tree ordering.
Binary search: A search method that repeatedly halves a sorted range by comparing a target with its midpoint. Its logarithmic search illustrates the benefit of keeping tree paths short.
B-tree: A balanced search tree whose nodes can contain multiple keys and have many children. B-trees reduce storage-access depth and suit disks better than pointer-based binary trees.
Linux kernel: The open-source operating-system kernel that manages hardware, processes, memory, and system calls. The kernel uses red–black trees in selected subsystems for ordered data and efficient updates.
Leonidas J. Guibas: An American computer scientist whose work includes geometric algorithms and data structures. Guibas coauthored the 1978 paper that formalized red–black trees.

Linked from 3 pages