Also, updating the tree might be much faster if you don't use it for the moving enemies, but the static towers. A primitive method without a tree can be sorting your enemies by their x coordinate, so towers will only have to check a much smaller subset.
Bottom line: smart and clever algorithms are great to drastically reduce workload by avoiding lots of expensive operations. However, your operation (basically
const float enemyDistance = dot(tower.pos, enemy.pos); if (enemyDistance < previousMinDistance) previousMinDistance = enemyDistance;is the opposite of expensive, making it important to consider the overhead of other methods, find the break-even point and most of all, decide if the performance increase is worth the headache and potential bugs of a more complicated algorithm.
Another thing to keep in mind in the days of up to 8 cores: how well can you execute it in parallel? Though I'd expect that with your setup, any algorithm can be run independently for each tower, so you can process your tower in (not quite) an nth of the time (with n being the number of cores). As long as you stay away from globals or static variables in your functions. Just grab Intels tbb library and enjoy how easy to use that parallel_for can be.