Pergunta

I am implementing an R-tree with the quadratic splitting method.

However in most articles I have read there a piece of information that is missing or misleading (or the most probably case, I completely misunderstood something).

R-trees are supposed to be balanced, yet you need to find the node that will increase less in area to insert your new object, and split such node if full. However this can clearly lead to having a very unbalanced tree in depth, as that node can always be on a single branch (say, leftmost in a graph-type representation of the tree).

Should the insertion criteria say " find the node that will increase less in area to insert your new object among those that are not full, [...]" ?

OR can the quadratic splitting method create very unbalanced trees if you are unlucky with new entries? Say if after N insertions all the new insertions are are very localized, e.g. in always fit in the leftmost leaf in the following figure

enter image description here

Or is there something else that I did not understand?

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top