I'm trying to implement a simple red-black tree. Node of the tree contains fields for key:int and value:string. I have not seen examples with same keys stored in the tree. But there is multimap class in C++ or TreeMap in Java that utilizes red-black tree and it can store two ore more same keys. So, is red-black tree stores only unique keys? Is there any strict rule about this or universal definition? P.S.:Imho, as red-black tree is a binary search tree, so it cannot store duplicate keys because a binary search tree stores only unique values by definition.
By the BST definition
key in each node must be greater than or equal to any key stored in the left subtree, and less than or equal to any key stored in the right subtree
Thus, BST allows duplicate keys.
If you take a look of for instance insert operation, there is a line which decides whether to insert to the left (key is less) or to the right (key is greater or equal). Thus, there is no problem to insert duplicate keys.
When one traverses a tree for a key, it can easily find all values for the given key.