Red-black tree with Graphviz insertion example – 以 Graphviz 讲解红黑树添加节点

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/