Exercise 3.3.18. There is one more possible variant

[markoved]

Hello! First, thank you very much for this great repository!

Second, I think there is one more possible variant in exercise 3.3.18. For n = 6 another one tree is also suitable: And from this also more trees can be derived for n = 7, 8, 9 and 10.

[reneargento]

I'm happy to know the repository is being useful to you!

About the tree you mention, I'm afraid that the variant you describe has the same structure as the one written in the answer.

Putting it into drawing should make it more clear: This is the structure for the red-black BST with N = 6 currently in the answer:

   (  )
() () ( )

And this is the structure of the red-black BST you mention:

   (  )
(  ) () ()

Notice that there is a difference on the order of the subtrees on the "second level" of the tree structure, but it does not mean that the structure itself is different.

You can also confirm this by looking into the description of exercise 3.3.5. There is a drawing on its right side of all structures for 2-3 trees of sizes 2, 3, 4, 5 and 6. On that drawing, there is only one 2-3 tree structure of size 6. And since red-black trees are a representation of 2-3 trees, they also have only one structure of size 6.

[markoved]

I expected you to answer like that.

The point is that yes, the variant I described and the one written in the answer have the same structure, but only as 2-3 trees. But considering them as red-black trees, their structure is different. That can be seen on the picture below.

As can be seen, their structures as of red-black trees are very different. Especially, height (one has 2, and another has 3), that causes different worst-case performances. That why it is important to think of them as different trees. Red-black trees are a representation of 2-3 trees, but one 2-3 tree can be represented by several red-black trees.

Since the exercise asks to "draw all the structurally different red-black BSTs", the structure of trees as red-black trees must be taken into account, not as 2-3 trees, and 2 cases above should be consisdered as different.

[reneargento]

Your distinction between 2-3 trees and red-back tree structures make sense. I updated the exercise here: https://github.com/reneargento/algorithms-sedgewick-wayne/commit/879d3043f2d81f63ae1fa2dd1ea2a742298eebae Thanks for the contribution!