I've implemented a red-black tree (which is a kind of self-balancing binary search trees) with duplicated keys allowed. In the Insert method I put nodes with equal keys as right child nodes. As you may know, after insertion of a node we need to fix up the tree to preserve its properties. I've noticed that after fixup, nodes with equal keys can be placed as left child nodes too, like this:
...
/
5
/ \
5 5
As far as I understand this happens because we need to preserve minimum height of a tree. So if all keys are the same, this situation is completely wrong for a self-balancing tree:
5
\
5
\
5
...
My question is: can you please confirm that we cannot keep equal keys strictly right or left if we are talking about self-balancing trees?
we cannot keep equal keys strictly right or left if we are talking about self-balancing trees
This is true, and the example you have given proves the point.
Most often the values in a search tree are assumed to unique. If you have a data set with duplicate keys, you can go for the alternative where each node has a count, so that if you are about to insert a duplicate key you instead increment the found node's count. With deletion you delete the count until it is zero -- then you really remove the node.
If you have associated values to the keys (payload), then instead of a count, store all associated data in the single node, possibly as an array. This is better than continuing with duplicate keys, as that will affect the worst-case time complexity of the search.
Alternatively you could identify a composite key to use that would make it unique. This way you can use the search algorithm to have a more targeted search that will also have the promised time complexity.