I'm missing why any tree implementation doesn't fit your needs. They can be traversed in order (forwards or backwards), they are in order if you traverse them in order, they are quick to add and remove, they are quick to find elements and distance should just be a traversal counting nodes on the way (i think). It is hard to say without any idea what the data you are storing is and wehatehr you are talking about the data being in order or some form of index.