Geometry Boost List: [ggl] rtree - remove

Subject: [ggl] rtree - remove
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-03 19:52:11

Hi,

I'm currently implementing algorithm removing element from the tree. In 
general it looks as follows:

1. Traverse the tree in order to find the leaf containing the element
2. Traverse back to the root deleting nodes which has less than min 
number of elements and adjusting parent's boxes
3. Storing the elements removed from those nodes to reinsert them later
4. Reinsert those elements

If element were retrieved from leaf node, it's a value. If it were 
retrieved from some internal node on some level, it is a node on 
level+1. Internal node is a root of a subtree containing nodes structure 
and leafs with values.

In the original algorithm [Gut84] elements retrieved from node on some 
level (e.g. some internal nodes) are reinserted to the tree and placed 
in the level where they belong. Values are of course inserted in leafs.

But in the old implementation different algorithm is used. All values 
are retrieved from leaf and all retrieved nodes' subtrees. Then those 
all values from all deleted subtrees are reinserted to the tree one by one.

Is there some reason, why this is done this way?

[Gut84] A. Guttman - R-TREES. A DYNAMIC INDEX STRUCTURE FOR SPATIAL 
SEARCHING.

Regards,
Adam