A red-black tree is a self-balancing binary search tree that maintains O(log n) height through a set of colour invariants enforced on every insert and delete. Each node is coloured red or black, and the invariants constrain how colours can be arranged: the root is black, red nodes can only have black children, and every path from any node to a descendant NULL leaf passes through the same number of black nodes. These rules together bound the height to at most $2 \log_2(n+1)$.

typedef enum { RED, BLACK } colour_t;
 
struct node {
    int          key;
    colour_t     colour;
    struct node *left, *right, *parent;
};

When an insertion or deletion would violate a colour invariant, the tree repairs itself through rotations (local restructuring that preserves BST order) and recolouring. A rotation around a node takes O(1) and changes the shape of a subtree without altering in-order traversal. At most O(log n) rotations are needed per operation.

Red-black trees are the implementation behind most ordered set and map types in standard libraries: the Linux kernel's interval tree and scheduler, C++'s std::map and std::set, and Java's TreeMap all use red-black trees. The invariants are complex to implement correctly but provide guaranteed O(log n) worst-case performance, unlike an unbalanced BST which degrades to O(n) on sorted input.