Introduction to Red-Black Trees

A red-black tree is a self-balancing binary search tree, with an additional attribute color stored with each node. Red–black tree offers worst-case guarantees for insertion, deletion, and search time.

BST provides an average-case complexity of O(logN) but in worst-case complexity can go up to O(N).

red-black tree ensures that the height of the tree always remains O(logN) after every insertion and deletion that in turn guarantees an upper bound on the complexity of insert/delete/search to O(logN).

A red-black tree should accompany the below properties:

Every node is either red or black.

The root and leaves (NIL’s) are black.

If a node is red, then its parent is black.

All simple paths from any node x to a descendant leaf have the same number of black nodes = black-height(x )

These constraints enforce a critical property of red-black trees: that the path from the root to the furthest leaf is no more than twice as long as the path from the root to the nearest leaf. The result is that the tree is roughly balanced. Since operations such as inserting, deleting, and finding values require worst-case time proportional to the height of the tree, this theoretical upper bound on the height allows red-black trees to be efficient in the worst-case, unlike ordinary binary search trees.

When the tree is modified, the new tree is rearranged and “repainted” to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.

The re-balancing is not perfect, but guarantees searching in O(logN) time, where N is the number of nodes of the tree. The insertion and deletion operations and tree rearrangement and recoloring are also performed in O(log N) time.

A simple scheme of a red-black tree is similar to that of the BS tree with an additional attribute color which can either be RED or BLACK.

Applications:

red-black trees are widely used in java collection implementations which include TreeSet, TreeMap, and HashMap. Also, the Completely Fair Scheduler used in current Linux kernels and epoll system call implementation uses red-black trees.