# Insertions in Red-Black Trees

I studied methods for inserting new nodes into Red-black trees for the first time this month.

In doing so, I read a lot of pages on the internet and found that ( if I'm not mistaken ) there are many, many, many accepted algorithms for inserting nodes into red-black trees.

Furthermore, I noticed that it is possible to have two insertion algorithms that don't break red-black tree invariants, but also can start with the same initial tree, insert the same node, and end up with different resulting trees.

I think.

For example, take this website's algorithm for insertion: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

And then there's this famous example from 'Purely Functional Data Structures' by Chris Okasaki:

And then there's this algorithm from Ohio State: https://www.pdf-archive.com/2017/03/28/08-red-black-tree/08-red-black-tree.pdf

Is it true that there are many red-black tree insertion algorithms that, given the same domain, will map the elements in that domain differently?

The easiest way of seeing this is to focus on the correspondence between red-black trees and $(2, 4)$-B-trees. A black node with its red children correspond to a B-tree node.