# R-tree insertion procedure when leaf is full

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

Or is there something else that I did not understand?

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)