I have written a set class which acts similarly to the STL set class.
Everything functions properly there.
I am now trying to convert this set class into a multiset.

A set class essentially stores its data as a sorted binary tree.
In order to make this a multiset I assume I just insert duplicate key/value pairs left or right and rebalance the tree.

However, I don't really like to assume things, and I'm not sure about what types of limitations this could impose.
Should I instead make a container in each node or a separate nested node list for identical keys?

For instance, structure with a nested node list:
................A
...........B.......C
........../.|.\...../.|.\
........D.E.F.G.H.I
............|.........|
............J........K

Based on simple sorting:
.................A
...........B.........C
........../...\....../...\
........E....F..H.....I
......./........./
.....J........K
..../......../
..D......G

Where the keys for BEJ are the same, and CHK are the same.

Anyone done something similar? Thoughts on the fastest/best way to implement?

It seems to me that adding a nested node list imposes a pretty significant memory overhead (as nodes without duplicate keys will contain a useless pointer) but will be faster to insert while the simple sorting method will be more memory efficient but take longer to insert.