# Red-black tree
A **red-black tree** is a self-balancing [[binary-tree|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)$.

```c
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 [[binary-tree|BST]] which degrades to O(n) on sorted input.

| Operation | Time |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
| Min/Max | O(log n) |