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?


1 Answer 1


Nope, you are wrong!

In your example, if you keep adding nodes to the leftmost entry, the splits propagate upwards. There will be more levels, but as they propagate upwards, the leafs are always in the same level, thus it always makes a balanced tree, as long as you make sure you follow the insertion and splitting rules tightly (e.g. make sure there are always $m$ minimum objects in a node)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.