Is there a Tree with deterministic traversal, but which nodes can vary?
You can do this with any binary space partitioning tree, such as a k-d tree or an octree.

Your basic approach can actually be made to work.  The reason you think it won't work is because you have a misunderstanding about how nearest-neighbor search is done in these trees.  Let me show you how they work and how to adapt them to your situation: you'll see that your idea does work fine and is quite a nice approach.



The basic principle of nearest-neighbor search is:


Each subtree represents a (rectangular) region of space.
You'll keep track of the closest point to $p$ found so far.
For each subtree T, you'll figure out whether it's possible that any point in the region corresponding to T could be closer to $p$ than the closest found so far.  If not (if it's impossible), then you won't look at T or any subtree of T.  Otherwise, you'll recursively test each child of T.


This yields a recursive algorithm that explores some subset of the nodes in the tree.

The basic point is that nearest-neighbor search doesn't explore just one path through the tree.  Rather, it might "fork" and explore multiple paths.  However, it's still faster than looking at every leaf, because they're able to prune some (but not all) subtrees.



For example, build an octree representing $P$, the set of all points.  Each leaf of the octree corresponds to one point in $P$.  Each internal node of the octree corresponds to an "octant" (a rectangular volume of 3D space).

Next, augment the octree as follows: each internal node $x$ has a bit that indicates whether any of the leaves under $x$ are active (whether any of them correspond to points in $S$).  Call the octant "active" if it contains at least one point of $S$, so the bit for node $x$ indicates whether the corresponding octant is active.  You can update these active bits efficiently: adding or removing a point to $S$ can be done in $O(\log |P|)$ time.

Now, to find the neighbor nearest to point $p$, invoke $\text{Closest}(p, r)$, where $r$ is the root node of the octree and the procedure Closest is defined as follows:

$\text{Closest}(p, x)$:


If $x$ is not active, return $\infty$.
If $x$ is a leaf, return $d(p,x)$.
Otherwise, set $\text{curBest}$ to $\infty$.
For each child $y$ of $x$, do:


If $y$ is active and $d(p,y) &lt; \text{curBest}$, set $\text{curBest} := \min(\text{curBest}, \text{Closest}(p, y))$.

Return $\text{curBest}$.


Here we define $d(p,y)$ (the distance from $p$ to an octant $y$) to be the distance from $p$ to the nearest point in $y$, i.e., the minimum of $d(p,z)$ where $z$ ranges over all points in $y$.  Notice that this can be computed efficiently through a straightforward but ugly case analysis.

Notice that the structure of the octree depends only on $P$, but not on which points are active.  Thus, you don't need to adjust the partitioning or split points as you change which points are active.

You can do the same with a k-d tree instead of an octree.

There is no guarantee about what the worst-case running time of this procedure will be.  However, in practice, I would expect this to be pretty efficient, as large swathes of the octree can be "pruned".  In particular, I would expect it to be faster than the naive algorithm of computing $d(p,s)$ for each $s \in S$, if $S$ is large.