<p>the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s 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. </p>

<p>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.</p>

<p>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.</p>

<p>a close alternative that can be adjusted to have the "order invariant" property you describe is the <a href="http://en.wikipedia.org/wiki/Quadtree" rel="nofollow">Quadtree</a> 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.</p>

CC BY-SA 3.0
2012-10-21T14:46:00.923Z
clarification, order invariance as "not generally desired" here does not mean it is "undesirable" just that its apparently not a typical design requirement in the literature. in other words few applications that use R-trees seem to have the requirement that the trees be order invariant. for the questioner however, exceptionally, it is apparently "undesirable" although would like a clarification why that is really so.
vzn
CC BY-SA 3.0
2012-10-21T02:22:40.940Z
2012-10-21T02:40:15.023Z
2012-10-21T02:40:15.023Z
vzn
<p>Say I have 2 permutations of the the same set of elements.
I create 2 <a href="http://en.wikipedia.org/wiki/R-tree" rel="nofollow noreferrer">R-Trees</a>, one for each permutation.</p>
<p>Do I end up with 2 structurally identical R-Trees or not?</p>
<p>PS: My elements are rectangles on a plane.</p>
<h3>Edit:</h3>
<p>Reformulation of the question: is there an insertion algorithm that reconstructs the same R-Tree regardless of the order of elements in use?</p>

CC BY-SA 3.0
2012-10-15T13:58:54.407Z
What is an R-tree?
Tyson Williams
CC BY-SA 3.0
2012-10-15T15:14:18.913Z
@TysonWilliams http://en.wikipedia.org/wiki/R-tree I Assume (esp. as elements are rectangle on a plane)
jk.
CC BY-SA 3.0
2012-10-15T18:46:22.697Z
Yes, this R-Tree
firas
CC BY-SA 3.0
2012-10-15T22:25:21.863Z
The answer obviously depends on your insertion/construction algorithm!
Jeffε
CC BY-SA 3.0
2012-10-16T19:36:32.683Z
Yes of course, but I will edit the question to clarify my objective
firas
CC BY-SA 3.0
2012-10-21T02:23:52.577Z
it would help if you describe why that property is desirable or for what application etc. ... you will end up with Rtrees of similar performance except for "pathological cases" of inputs but not identical in structure.
vzn
<ds.data-structures><tree>
Does the order of insertion affect the topology of an R-Tree
firas
# Does the order of insertion affect the topology of an R-Tree

(Asked by: username_0 on 2012-10-15)

Say I have 2 permutations of the the same set of elements.
I create 2 [R-Trees](http://en.wikipedia.org/wiki/R-tree), 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?

**Tags:** ds.data-structures, tree
> **Comments:**
> **username_1**: What is an R-tree?  
> **username_2**: @TysonWilliams http://en.wikipedia.org/wiki/R-tree I Assume (esp. as elements are rectangle on a plane)  
> **username_0**: Yes, this R-Tree  
> **username_3**: The answer obviously depends on your insertion/construction algorithm!  
> **username_0**: Yes of course, but I will edit the question to clarify my objective  
> **username_4**: it would help if you describe why that property is desirable or for what application etc. ... you will end up with Rtrees of similar performance except for "pathological cases" of inputs but not identical in structure.  

---

## 1 answers

### Answer by username_4 on 2012-10-21. Score: 1 | Accepted answer

the R tree algorithms typically create "R"s (rectangles) iteratively/sequentially based on the order of insertion of the data. the "R"s 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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_4**: clarification, order invariance as "not generally desired" here does not mean it is "undesirable" just that its apparently not a typical design requirement in the literature. in other words few applications that use R-trees seem to have the requirement that the trees be order invariant. for the questioner however, exceptionally, it is apparently "undesirable" although would like a clarification why that is really so.  

---

