Red-Black tree and its purpose

Definition

A Red-Black tree is a self-balancing binary search tree in which every node has an extra bit of information, its colour (red or black). The colours obey these rules:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL / null link) is black.
4. A red node cannot have a red child (no two red nodes in a row).
5. Every path from a node to its descendant leaves has the same number of black nodes (equal black-height).

These rules guarantee that the longest path from the root is at most twice the shortest path, so the tree height is at most 2·log₂(n + 1).

        13(B)
       /     \
    8(R)      17(R)
   /   \     /    \
 1(B) 11(B) 15(B)  25(B)

Purpose

• An ordinary BST can become skewed and degrade to O(n) search. A Red-Black tree keeps the height O(log n), so search, insertion and deletion all take O(log n) time in the worst case.
• It restores balance after an update using only recolouring and at most 2 rotations on insertion (3 on deletion), so updates are cheaper than in a strict AVL tree.
• It is used where frequent insertions and deletions occur, e.g. map/set in the C++ STL, Java TreeMap, and process scheduling in the Linux kernel.