Rodezwartboom

Rodezwartboom (red-black tree) is a self-balancing binary search tree data structure used in computer science to implement ordered associative containers such as maps and sets. Each node stores a key (and possibly a value), and the nodes are arranged to preserve the binary search tree property: keys in the left subtree are smaller than the node’s key, and keys in the right subtree are larger.

Each node has a color, either red or black. The red-black properties are: the root is black; red nodes cannot have red children (no two red nodes in a row); and every path from the root to a leaf (nil node) contains the same number of black nodes. These invariants ensure the tree remains reasonably balanced, limiting its height to a logarithmic bound relative to the number of keys.

Balancing is achieved through recoloring and tree rotations during insertions and deletions. Insertion starts by adding a new red node, followed by recoloring and rotations to restore the invariants. Deletion is more involved and may require several cases to fix potential violations, often including moving blackness up the tree and performing rotations.

Operations such as search, insertion, and deletion all run in O(log n) time, where n is the number of keys. Rodezwartboom is widely used in standard libraries and databases for implementing ordered containers and for operations that require efficient ordered traversal. The concept was introduced by Rudolf Bayer in 1972 and has since become a standard balancing technique in many programming languages and systems.