Preface
I spent sometime on learning Red-Black tree. While it’s pretty time consuming as I couldn’t find a convincing tutorial in Youtube. So I decided to make it myself, with Graphviz.
Sample data
We will generate a tree with
[0, -1, 2, 3, 4, 5, 6, 7, 100, 50, 10, -10, -7]
Red-back tree rules
Please read this and this before continue.
Example, make a Red-black tree with number 0 to 9
Rules
- Root node and nil nodes are always black
- New node is always red
- No two connected nodes are red
- Every path from Root to leaf must have the same black nodes
- Must be a balanced BST
Insert 0, -1, 2
Insert 3
Two connected red nodes, with red uncle (uncle node is the sibling to parent node)
* Recolor uncle and parent to black
* Recolor grandparent as red (unless Root node)
Insert 4
two connected red nodes with black uncle (nil uncle is black), Right-Right case
- Left rotate grandparent
- Swap color of grandparent and parent
Insert 5
Two connected red nodes with red uncle
Insert:
Fix:
fix two connected red nodes with red uncle
* Recolor uncle and parent as black
* Recolor grandparent as red
Insert 6
Two connected red nodes with black uncle (nil uncle is black), Right-Right case
Insert
Fix:
Two connected red nodes with black uncle (nil uncle is black), Right-Right case
- Left rotate grandparent
- Swap color of grandparent and parent
Insert 7
fix two connected red nodes with red uncle
Insert
Fix 1:
fix two connected red nodes with red uncle
* Recolor uncle and parent as black
* Recolor grandparent as red
Fix 2:
Two connected red nodes with black uncle (nil uncle is black), Right-Right case
- Fix up all conflicts all the way up
- Left rotate grandparent
- Swap color of grandparent and parent
Insert 100
Two connected red nodes with black uncle (nil uncle is black), Right-Right case
Insert
Fix
Two connected red nodes with black uncle (nil uncle is black), Right-Right case
* Left rotate grandparent
* Swap color of grandparent and parent
Insert 50
fix two connected red nodes with red uncle
Insert
Fix 1
fix two connected red nodes with red uncle
* Recolor uncle and parent as black
* Recolor grandparent as red
Fix 2
fix two connected red nodes with red uncle (again)
* Recolor uncle and parent as black
* Recolor grandparent as red
Insert 10
Insert
Two connected red nodes with black uncle (nil uncle is black), Right-Left case
Fix
Two connected red nodes with black uncle (nil uncle is black), Left-Left case
* Right rotate grandparent
* Swap color of grandparent and parent
Insert -10, -7
Two connected red nodes with black uncle (nil uncle is black), Left-Right case
Insert
Fix 1:
Two connected red nodes with black uncle (nil uncle is black), Left-Right case
* Left rotate parent
Fix 2:
Two connected red nodes with black uncle (nil uncle is black), Left-Left case
* Right rotate grandparent
* Swap color of grandparent and parent
Reference and credits
- https://www.geeksforgeeks.org/red-black-tree-set-1-introduction-2/
- https://www.geeksforgeeks.org/red-black-tree-set-2-insert/