1procedure insert(tree, value)
2 perform BST insert (new node is RED)
3 fix-up(tree, node)
4procedure fix-up(tree, z)
5 while z.parent is RED do
6 if z.parent is left child
7 uncle ← z.parent.parent.right
8 if uncle is RED then recolor
9 else if z is right child, left rotate
10 recolor and right rotate grandparent
11 else mirror case (parent is right child)
12 tree.root.color ← BLACK