Red Black Trees
Red-Black Trees are binary search trees that are named after the way the nodes are coloured.
Each node in a red-black tree is coloured either red or black. The height of a red black tree is at most 2 * log(n+1).
A red black tree must maintain the following colouring rules:
every node must have a colour either red or black.
The root node must be black
If a node is red, its children must be black (note that this also implies that red nodes cannot have red parents)
Every path from root to a null node must have exactly the same number of black nodes.
null nodes are also sometimes called null leafs. these are not really nodes.. they are the "nodes" that null pointers point to... so we when we think about counting black nodes we think about how many black nodes there are to every nullptr in the tree
Insertion
We will begin our look at Red-Black trees with the bottom up insertion algorithm. This insertion algorithm is similar to that of the insertion algorithm we looked at for AVL trees/Binary search trees.
Insert the new node according to regular binary search tree insertion rules. Of the 4 colouring rules, the one rule we don't want to break is rule number 4. Everything we do is to avoid breaking rule 4 (every path from root to every null leaf has same number of black nodes). Thus, New nodes are added as red nodes. We then "fix" the tree if any of the rules are broken.
Note that because we inserted a red node to a proper red-black tree, the only 2 rules that might be broken are:
rule 2: root must be black
rule 3: red node must have black children
Rule 1 is pretty much not broken as we coloured it red. We also won't break rule 4 because we added a red node so the number of black nodes has not increased.
General Insertion Algorithm
To insert into a red-black tree:
find the correct empty tree (like bst) and insert new node as a red node.
working way up the tree back to parent fix the tree so that the red-black tree rules are maintained.
Fixing nodes:
If root becomes red, change it to black.
This won't break any rules because you are just adding 1 black node to every branch of the tree, the number of black nodes increase by 1 everywhere. This can only happen as the root as it is the only node that is part of every path from root to nullleaf
If there are two red nodes in a row:
Identify the following nodes:
upper red node as the Parent (P)
the lower red node as the Child (C)
parent of parent is Grandparent (G)
sibling of Parent as Parent's sibling (PS)
if the PS is black
perform a rotation (look at G->P->C, if they form a straight line do a zig-zig(single) rotation, if there is a bend, do a zig-zag (double rotation)
after rotation exchange G's colour with the node that took over G's spot. In otherwords
make which ever node (depends if it was zigzig or zigzag rotation... it will either be P or C) that took over G's node black
make G red
if the PS is red
exchange the colour of the grand parent with its two children. In otherwords
G becomes red
P and PS becomes black
Example
Starting with an empty tree let us take a look at how red-black tree insertions work.
In the pictures below, null nodes (empty subtrees) are denoted as black circles
Insert 30
All nodes are inserted as red nodes:
If the root is red, make it black:
Insert 50
Insert 50 as a red node, parent is black so we don't have to change anything
Insert 40
Inserting 40 as a red node.
Two red nodes in a row. Identify G, P, PS and C
P - parent (upper red) - 50
C - child (lower red) - 40
G - grandparent 30
PS - parent's sibling - null node to left of 30
What we do depends on colour of PS. In this case PS is black, so we will be fixing this with a rotation
The type of rotation depends on the configuration of G, P and C. If the path is from G to C is straight (both left or both right) do a zigzig (single) rotation. If it is angled (left then right or right then left) we need to do a zigzag (double) rotation.
In this case, we need to do a zig zag (double) rotation.
Rotate first 40 and 50
then rotate again with 30 and 40, this time doing a colour swap. A zigzag rotation is just an extra step that is needed to make the insertion path go in the same direction.
After rotations are complete, we exchange the colour between the node that took over G's spot (40 in this case) and G. Thus, 40 becomes black and 30 becomes red.
Insert 20
inserting 20 as a red node.
Two red nodes in a row. Identify G, P, PS and C
P - parent (upper red) - 30
C - child (lower red) - 20
G - grandparent - 40
PS - parent's sibling - null node to left of 50
What we do depends on colour of PS. In this case PS is red. Thus we exchange colours between G and its two children:
Doing so breaks rule 2: roots must be black. Thus, we need to fix that. As it is the root, we can just change it to black without causing other problems.
Insert 10
inserting 10 as a red node.
Two red nodes in a row. Identify G, P, PS and C
P - parent (upper red) -20
C - child (lower red) - 10
G - grandparent 30
PS - parent's sibling - null node to right of 30
What we do depends on colour of PS. In this case, the parent's sibling is black (null nodes are black). Thus, we will fix this with a rotation. Rotations are always done with G as the root of the rotation (the A in the rotation diagram)
This time, the path from G to P to C is "left" then "left". Thus, we only need to perform a single rotation, followed by swapping the colours of G and the node that took G's spot.
Finally we get:
Last updated
