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?
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?
Share Improve this question asked Mar 3 at 14:06 MaximMaxim 2,1441 gold badge21 silver badges27 bronze badges 2- I don't really think there is a correct answer to this since red-black trees have unique keys. You could do something where the "end node" has a list or something and call it red-black. – Thomas Koelle Commented Mar 3 at 15:01
- It's just a matter of construction of a tree. There is nothing tricky there to have nodes with duplicated keys. As I've said, I already have implementation and it works just fine. – Maxim Commented Mar 3 at 17:26
2 Answers
Reset to default 2we 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.
I'm not 100% sure but for what I know you should always follow a specific rule while inserting duplicate keys, as inserting them without specific rules could lead to not may be able to use correctly the properties of red black-tree, hope it answers your question.