Hello, I just stumbled upon this page when searching info about quadtrees, and I notice there's lot of talk about algorithms on this website. So I created an account just to give my two cents.
I have been able to use modified quadtrees for an efficient implementation of nearest neighbor algorithm on c++. The choice of language doesn't really matter, but the balancing conditions do.
It's quadtree with variable width/height buckets. I insert the first five items to a bucket in no particular order. When a bucket is filled (it has five items), I take the most centre point of the five and make it a pivot. The other four points are then re-inserted into some or all of the quadrants defined by said pivot: upper right quadrant, upper left, lower left, lower right.
Each node in the tree is balanced at most 1 time. As I keep the pivot in the branch (not in the leaves), even a pathological input will lead to a working tree, because at each branch the number of items in the biggest bucket is reduced by at least 1 item, the pivot. In practice the branching factor becomes a bit more than 2.0 on average.
When a node is searched, start from the root, check if the item in current branch is the item you seek. If not, if it's a branch with 4 quadrants, check which quadrant the item should be in and search that subtree (recursively). If it's a branch with 1..4 items in no particular order, search all of them.
I've chosen the center item with simple heuristic: remove from the 5 items in order a) the rightmost b) the leftmost c) the top item d) the bottom item. The item that's now left is pretty much in the center, with good probability to divide the current and future items in a balanced manner.
Hope it helps.