It is a straightforward adaptation of red-black trees to allow multiple instances of the same value -- internally you just need a counter on the nodes. The problem with doing this for NaN is that the value of NaN is indeterminate, which is why comparison on NaN is undefined.