2 years ago

The color ensures that the tree remains approximately balanced during insertions and deletions. 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 purpose of a red-black tree is to stay balanced which ensures that its common operations, like lookup and delete, never degrade to worse than O(n*log(n)).

Since the reason colors are added to a binary tree is to ensure that it remains balanced, we need to understand how and why a binary tree is balanced.

The following tree is balanced because between its two branches one has a height of 2, and the other 3, meaning they differ by no more than 1.