Say I have 2 permutations of the the same set of elements.I create 2 R-Trees, one for each permutation.Do I end up with 2 structurally identical R-Trees or not?PS: My elements are rectangles on a plane.Edit:Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?
Does the order of insertion affect the topology of an R-Tree
ds.data structures;tree
the R tree algorithms typically create Rs (rectangles) iteratively/sequentially based on the order of insertion of the data. the Rs are built directly out of the coordinates of the data seen so far. it does not appear that there are widely studied R-tree variants that build identical trees no matter what the order is, it does not seem to be a generally desired design criteria for the algorithms, which are judged on other criteria such as performance of search, insertion, overflow splitting etc. except in artificial/contrived/pathological cases, the resulting R-trees will be close in structure and performance no matter what order the insertion. however it is not inconceivable that such an algorithm could be devised with the property of resultant tree invariance based on adjusting the insertion and overflow splitting logic.on the other hand if you dont require an online algorithm you could just sort your data according to any criteria beforehand and the R tree will end up with the same structure of course.a close alternative that can be adjusted to have the order invariant property you describe is the Quadtree because it is based on partitioning the overall space (assuming its dimensions are known) in a fractal 4-square pattern that does not depend on ordering of the input or directly use the individual points for bounding coordinates.