Nearest neighbors analysis in Red Black Trees


I use a Red Black Tree where each nodes contains a symbol sequence, e.g. top node BB, left child AB, right child CB.

Given a symbol sequence from the tree, is there an efficient way to retrieve n nearest neighbors or all neighbors within a distance radius?

Could I recursively search the children and parent nodes and keep adding each visited node until I have n of them or in the radius case the encountered node is outside the radius?

I know the efficient way for neighborhood queries is e.g. a KD Tree, but I am looking for a data structure that will allow me to insert new sequences without having to rebuild the whole tree each time.