Insertions in Red-Black Trees

Question

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?

Answer 1

Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time. That is, there exists more than one valid red-black tree insertion algorithm, whose outputs are not always equal.

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.

In particular, if you have two sibling B-tree nodes with four elements in total, they can be distributed 1/3 or 2/2. In red-black terms, if two black nodes are cousins, it's possible for each to have one red child, or for one of them to have two red children and the other to have none. More than that, you can shuffle the elements around between the nodes locally to transform one such pattern into the other.

As wikipedia says, "The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time"; the imperfection of balancing gives room for multiple tree representations of the same set.