added a comment - - edited
subseq and rsubseq + first solve the "neightbour lookup" part of NavigableMap, but not the submap methods.
Subsetting red-black trees in logarithmic time is entirely possible, but, as mentioned in my previous comment, not if you want to maintain the property that count on the resulting structure is, if not O(1), then at least significantly better than O(n). This is because there is no way of knowing how many nodes are contained in any subrange of a BST without actually walking it or storing annotations in (at least some of) the nodes ahead of time.
I have described a possible workaround in my Conj talk last November and I have a sketch lying around somewhere, but it's not going to offer the type of convenience that data.avl does – the limitation described above is fundamental; it could be workable for use cases where count is (almost) never called.
As a side note, data.avl uses an implementation of neighbour lookup based on subseq et al. in its test suite, as a sanity check on the direct implementation used by clojure.data.avl/nearest. There's also an implementation of subrange (the universal subsetting function for data.avl collections) based on subseq in there; as you'd expect, it's extremely slow for all but the smallest output sizes.