data structures - Quadtree equivalent of AVL tree -

i looking quadtree/octree/2^n tree self-balances accepts new observations, without knowledge of every other point, iow, cannot rely on median writing in 'streaming' context. avl tree balances goes pivoting, there similar data structure higher dimensioned data?

the avl tree, returns 1 result, element find. especiall ebucket based quadtrees return list of objects near queried location. calling programm has inspect objects in result ones fullfill application task.

from perspective balancing makes little sense. more dense region (e.g city) has more detailed structures , therefore has deeper quadtree. not bad. don't see need quad balancing.

further quadtree types (point, lines, object quadtrees) quad node when splitted, splitts in 4 equal size sub rectangular or quadratic sub nodes. these types called restricted quad trees. there 1 hint in literature have found on balanced quadtrees (m.bern, d-eppstein , j.gilbert: mesh generations, cited in hanan samet: foundations on multidimensional spatial data strcutures). if have academic interest might read paper, otherwise doubt has value you.

otherwise not normal (i.e restricted) quad tree. read more on r-trees sub dividinbg space in individual rectangles. (r-trees competitor quad trees) quad type balancing corresponds quad tree, dynamic bucket size. don't see advantage.

about garuantees: maximum depth of final built static quad tree, gives upper bound. (feel free measure average depth). max bucket size, gives upper bound. (again measure avg bucket size).

balancing: structure of quad tree depends on order of inserted values. values insert quad tree static, can ordered in advance. there specific pre-orderings give (slightly) better balance.

please note quad tree spatial index wich not usefull deletions.