May binary search tree get broken by rotation?

Question

I'm learning algorithms now, and while implementing red-black tree insertion I came up to the idea described in the question's header. This takes place when equal value nodes are involved.

Let's start with a simple example tree, where left children are less than the parent and right children are greater or equal to the parent.

Initial state of such tree might be the following:

Then, if I rotate this tree left, I get:

The node which violates the BST condition that all left children are less than the parent is shown in red.

---

So the question is: why lots of algorithms which implement insertion, deletion or else on binary search trees use rotation when rotations break BSTs (or do I just do the rotation wrong)?

Answer 1

The question is why you want to rotate your BST when it satisfies all conditions. The rotation in your example will not be implemented in any sense. In 'lots of algorithms', the rotation is only required when 'insertion' or 'deletion' or 'else' makes a new tree that violates BST properties. Lets say if you replace 6 by 8 as the root of BST, now your rotation will make sense.

Answer 2

To the best of my knowledge, most textbooks introduce BSTs by considering unique keys, that is: left < root < right. Everything is based on this, including rotations. How to deal with duplicates is usually left as an exercise, and no one says it has to be as simple as just changing that invariant to left <= root < right.

This is done exactly because of the problem you describe: in some cases, rotations might not work "out of the box" with duplicates. There's probably always a way to make them work even if you add duplicate nodes (and don't resort to storing a count in each node), but it would just distract from the general idea to have to mention that edge case and its solution for various trees involving rotations.

So basically:

• Depending on your tree, rotations might not always work the "standard" way described in a textbook if you change the textbook's preconditions: if the textbook says left < root < right, you shouldn't assume its algorithms also work as given for left <= root < right or any other precondition. You might need to change some things. In RB trees for example, you might need to do the rotation at a lower level.
• If you don't want to bother changing anything, just add another field in your node that counts how many times that node's key appears.