Boost logo

Geometry :

Subject: [ggl] rtree - remove
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-05-05 09:45:48

Adam Wulkiewicz wrote:
> 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?

I've implemented remove algorithm. It's an implementation of the
original algorithm so it's different than the old one. Trees produced by
both implementations are different. I only tested it for max:32 min:8
and it's a lot faster. Removing 0.5M values from tree containing 1M
takes 3.6s instead of 23.5s(old implementation).


Geometry list run by mateusz at