Redblack Trees
3 mins readJanuary 25, 2020
red-black-tree
rb-trees
data-structures
This post is not an another article which describes RB Trees. This one tries to explain the need for node coloring constraints described in the RB Tree design.
What are RB-Trees
- These are balanced binary trees with each node having one extra property.
color
- The node colors can be
- Red
- Black
Constraints while coloring the tree
- Root is
black
- Red node can have only black children
- For each path to every leaf in the tree, there are same number of black nodes.
Need for these constraints.
The need for the RB Trees and these constraints is to keep a binary tree as balanced as possible. In this section we will prove these constraints help us in doing so.
Let’s start with an assumption that, there exists a completely balanced binary tree with height h
and we color every node in this tree with a single color black
.
Balanced binary tree with all nodes colored black
When a new node is inserted in to this binary tree, it creates an imbalance. Because path to one of the leaf is longer than the paths to other leaves.
Imbalance created after one node insertion
Constraint 3 tries to keep this imbalance in control. It enforces us to color one of the node as red in the new path (the one which is longer than others).
Leaf is colored red. Constraint 3 holds.
But we can still create imbalance by coloring every new node inserted in this new path as red
. This way the new path can grow without a limit.
Constraint 3 holds, but still we can cause imbalance
Constraint 2 solves this problem. Now a red node cannot have red children. So at worst case, the path can grow up to twice the number of black nodes in that path (2 * h). (The node colors alternate from root to the leaf in the path)
Tree honoring constraint 2. (We recolored the tree)
There are two ways possible to color such path. One starts with black
root and other with red
.
If the root was colored red
, the children of root should be colored black
(Constraint 2). In this case a RB-Tree with only two nodes violates the constraint 3. So constraint 1 says color the root with black
.