What's the point of the colors in red/black trees?

Question

We know AVL trees are better for searching and red-black trees are better for insertion and deletion because they require lesser rotations, but what is the need for colouring the nodes?

Answer 1

At a high level, the color rules in a red/black tree are what keep the tree balanced. The rules are very strict: if you require all root-null paths to pass through the same number of black nodes, and if red nodes can't have red children, then you can't have wide imbalances between the lengths of different paths down the tree. That in turn requires the nodes to be reasonably balanced around the tree, keeping the height low.

On a more technical level, the color rules in red/black trees connect the shape of the tree to that of another data structure called a 2-3-4 tree. You can learn more about that through this set of lecture slides, which explains where the red/black tree rules come from.

Answer 2

You probably know that the rules are (i) A red parent cannot have red children (ii) The black node count from root to a leaf node is the same in every path. They are the main rules. Two other rules are normally (iii) The root node is black (iv) all null nodes (the pointers for a leaf node which has 0 children), they are regarded as black

Basically the main two rules ensure that the tree is balanced. If the black tree height is N, then at minimum the number of nodes from root to leaf node is N (nothing but black nodes all the way) and at most 2 * N (alternative nodes are black - red - black - red etc).

Finally when doing Inserts or Deletes, many times rotates are not needed, colour flips will suffice as long as they leave the tree with the rules satisfied. It can be shown that Insert operation requires at most 2 rotations (and sometimes 0). And a Delete operation at most 3 rotations (and sometimes 0).

So a combination of colour flips and rotations keeps a red-black tree balanced.