# All possible Red Black Trees with this set {1,2,3,4,5}

I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}.

Now we have 120 ways to write 1,2,3,4,5

{1,2,3,4,5} {1,2,3,5,4} {1,2,4,3,5} {1,2,4,5,3} {1,2,5,3,4}
{1,2,5,4,3} {1,3,2,4,5} {1,3,2,5,4} {1,3,4,2,5} {1,3,4,5,2}
{1,3,5,2,4} {1,3,5,4,2} {1,4,2,3,5} {1,4,2,5,3} {1,4,3,2,5}
{1,4,3,5,2} {1,4,5,2,3} {1,4,5,3,2} {1,5,2,3,4} {1,5,2,4,3}
{1,5,3,2,4} {1,5,3,4,2} {1,5,4,2,3} {1,5,4,3,2} {2,1,3,4,5}
{2,1,3,5,4} {2,1,4,3,5} {2,1,4,5,3} {2,1,5,3,4} {2,1,5,4,3}
{2,3,1,4,5} {2,3,1,5,4} {2,3,4,1,5} {2,3,4,5,1} {2,3,5,1,4}
{2,3,5,4,1} {2,4,1,3,5} {2,4,1,5,3} {2,4,3,1,5} {2,4,3,5,1}
{2,4,5,1,3} {2,4,5,3,1} {2,5,1,3,4} {2,5,1,4,3} {2,5,3,1,4}
{2,5,3,4,1} {2,5,4,1,3} {2,5,4,3,1} {3,1,2,4,5} {3,1,2,5,4}
{3,1,4,2,5} {3,1,4,5,2} {3,1,5,2,4} {3,1,5,4,2} {3,2,1,4,5}
{3,2,1,5,4} {3,2,4,1,5} {3,2,4,5,1} {3,2,5,1,4} {3,2,5,4,1}
{3,4,1,2,5} {3,4,1,5,2} {3,4,2,1,5} {3,4,2,5,1} {3,4,5,1,2}
{3,4,5,2,1} {3,5,1,2,4} {3,5,1,4,2} {3,5,2,1,4} {3,5,2,4,1}
{3,5,4,1,2} {3,5,4,2,1} {4,1,2,3,5} {4,1,2,5,3} {4,1,3,2,5}
{4,1,3,5,2} {4,1,5,2,3} {4,1,5,3,2} {4,2,1,3,5} {4,2,1,5,3}
{4,2,3,1,5} {4,2,3,5,1} {4,2,5,1,3} {4,2,5,3,1} {4,3,1,2,5}
{4,3,1,5,2} {4,3,2,1,5} {4,3,2,5,1} {4,3,5,1,2} {4,3,5,2,1}
{4,5,1,2,3} {4,5,1,3,2} {4,5,2,1,3} {4,5,2,3,1} {4,5,3,1,2}
{4,5,3,2,1} {5,1,2,3,4} {5,1,2,4,3} {5,1,3,2,4} {5,1,3,4,2}
{5,1,4,2,3} {5,1,4,3,2} {5,2,1,3,4} {5,2,1,4,3} {5,2,3,1,4}
{5,2,3,4,1} {5,2,4,1,3} {5,2,4,3,1} {5,3,1,2,4} {5,3,1,4,2}
{5,3,2,1,4} {5,3,2,4,1} {5,3,4,1,2} {5,3,4,2,1} {5,4,1,2,3}
{5,4,1,3,2} {5,4,2,1,3} {5,4,2,3,1} {5,4,3,1,2} {5,4,3,2,1}


But this is too much, I need to construct 120 RBT and then take out the ones which are the same, is there any tip how can I take some out immediately before even trying to construct the RBT for them ?

## 1 Answer

Testing all 120 insertion orders is indeed much to much work in order to check out all trees. Moreover, there might be trees that are valid, but which are not found by inserting keys in some order.

A better appraoch would be to designing the trees by level. The number of black nodes on each path is equal, so a RB-tree with five keys can at most have two levels with black nodes: three levels would need seven keys.

It is perhaps helpful to consider a black node together with its red children as one single node with 1,2 or 3 keys (and 2,3 or 4 children). (In that way we get 2-3-4-trees.) Now either (1) the root has 2 keys and three children with each a single child, or (2) the root has 1 key with 2 children with a total of 4 keys. Remember a node with two keys can be represented in two ways as a RB-tree (the red child can be left or right.)

According to the OEIS there are eight such trees. Good luck.

• Oohh, good call exploiting the equivalence with 2-3-4-trees! That's indeed a much more clear route than anything I could come up with. Cool! – Raphael Apr 17 '18 at 10:05