CODEWITHSUNDEEP
data-structuresgraphicsbinary-search-treecomputer-sciencequadtree
Kyle Pena
Kyle Pena

Reputation: 537

Quadtree equivalent of AVL tree

I am looking for a quadtree/octree/2^n tree that self-balances as it accepts new observations, without knowledge of every other point, iow, it cannot rely on the median as I am writing in a 'streaming' context. The AVL tree balances as it goes by pivoting, is there another similar data structure for higher dimensioned data?

Upvotes: 1

Views: 536

Answers (1)

AlexWien
AlexWien

Reputation: 28767

The AVL tree, returns only one result, the element to find. But especiall the ebucket based quadtrees return a list of objects near the queried location. The calling programm finally has to inspect all objects in the result for that ones that fullfill the application task.

From that perspective balancing makes little sense. A more dense region (e.g city) has more detailed structures and therefore has a deeper quadtree. This is not bad. I don't see any need for quad balancing.

Further for all quadtree types (point, lines, object quadtrees) a quad node when it is splitted, it always splitts in 4 equal size sub rectangular or quadratic sub nodes. These types are called restricted quad trees. There is only one hint in literature I have found on balanced quadtrees (M.Bern, D-Eppstein and J.Gilbert: Probably good mesh generations, cited in Hanan Samet: Foundations on Multidimensional Spatial Data Strcutures). If you have academic interest you might read the paper, otherwise I doubt it has value to you.

Otherwise it is not a normal (i.e restricted) quad tree. Read more on R-Trees for sub dividinbg the space in individual rectangles. (R-trees are a competitor to quad trees) The only quad type balancing that corresponds to a quad tree, could be a dynamic bucket size. But for that I don't see an advantage.

About garuantees: The maximum depth of the final built up static quad tree, gives an upper bound. (Feel free to measure an average depth). The max bucket size, too gives an upper bound. (Again measure the avg bucket size).

Balancing: The structure of a quad tree depends on the order of the inserted values. The values to insert into a quad tree are usually static, so the can be ordered in advance. There are specific pre-orderings that give a (slightly) better balance.

Please note that a quad tree is a spatial index wich is not well usefull for deletions.

Upvotes: 2

Related Questions