<p>An N-ary tree is the general term describing a tree data structure containing/organizing a list of numbers.</p>

<p>A B-tree is an N-ary tree opimized for block/disk access. Each leaves contain ranges of elements.</p>

<p>An R-tree is an N-ary tree but the order imposed on the list of elements is no longer the "greater than" order on a list of numbers but a"close to" metric on points in 2D and more. The "close to" metric is approximated by bounding boxes. An R-tree can be implemented over a B-tree, technically speaking. </p>

<p>Furthermore, any data set in n-dimensions has representations in 1D. Therefore, given some metric, all these tree topologies are isomorphic...</p>

CC BY-SA 3.0
2013-07-25T18:03:44.623Z
2013-07-25T18:03:44.623Z
Phil
<p>Any data structure can be serialised to any data structure, provided that they can hold the same information.</p>

<p><strong>Insertion</strong> works by locating the place to insert nodes through searching and insert.
If a node is full, then a split needs to be done.</p>

<p><strong>Splits</strong> need to check every possible partition, giving optimal solution of <code>O(2^{M+1})</code></p>

CC BY-SA 3.0
2012-03-05T14:11:04.483Z
2012-03-05T14:11:04.483Z
A T
<p>I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an arbitrary number of directed edges linking it to other nodes (i.e. children, parent and different grammatical relations such as subject_of, complement_of, etc.). Note that all these features are absolutely necessary to accurately represent the syntactical structure of a sentence.</p>

<p>Now, given such an initial tree with a totally unconstrained structure, I want to know if it is possible to convert that tree into a form that is more search-efficient (i.e. so that search involves less recursion). The only operation I <em>really</em> need to support is finding nodes with an arbitrary combination of type, id, value, and/or feature(s). I also need to be able to match a node back to the original tree if other operations are necessary. What is of primary importance is read-time and query efficiency.</p>

<p>From what I understand, B-trees and R-trees are generally search efficient. From Wikipedia, "like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory." This is exactly the situation I am in right now. However, I have very limited knowledge of the different types of trees and how they convert to another.</p>

<p>So, I am wondering if it is possible in theory to convert any N-ary tree (i.e. in my case, a completely unconstrained tree with an arbitrary number of children, edges and features for each node) into a B-tree or an R-tree to make it more search efficient? How would one go about doing this? </p>

CC BY-SA 3.0
2012-03-05T03:43:34.000Z
What is the motivation for converting to an R-tree?
Joe
CC BY-SA 3.0
2012-03-05T04:48:21.373Z
I am looking for a more efficient way to search a tree where the nodes each have an id, a value and multiple features. The tree is pretty deep and simple recursion has become completely inefficient.
user2398029
CC BY-SA 3.0
2012-03-05T12:23:01.013Z
What _exactly_ is a "feature"?  What _exactly_ does "search" mean?  _Exactly_ what operations do you want your data structure to support?
Jeffε
CC BY-SA 3.0
2012-03-05T12:56:56.477Z
A feature can be any primitive data type - I'm working in Ruby, so that would be integers, strings, arrays or hashes. The most common search operation is to find nodes on the basis of a combination of id, value and/or features. But, in theory, I'd like any "standard" tree operation (iterate children, get next sibling, retrieve parent, etc.) to be supported. Hope that clarifies what I'm looking for.
user2398029
CC BY-SA 3.0
2012-03-05T13:01:57.767Z
And if I said something horrible that deserves downvoting on my first post here, please do explain. If the question doesn't make much sense, that's _precisely_ why I'm here.
user2398029
CC BY-SA 3.0
2012-03-05T16:19:02.030Z
What is it in particular about an R-tree that you like ? In general, B-trees are used for disk-efficient access to large sets of data
Suresh Venkat
CC BY-SA 3.0
2012-03-05T16:52:20.317Z
There is no pre-defined range of number of child nodes within my tree (which is used to represent the syntactic structure of documents), therefore (from what I understand), a B-tree isn't suitable.
user2398029
CC BY-SA 3.0
2012-03-05T17:00:10.480Z
Given an initial tree with an unconstrained structure, I want to convert that tree into a form that is more search-efficient (i.e. involves less recursion) but without losing any information about the way the tree was initially structured. I understand the concept of a B-tree, but it seems to me that converting to a B-tree would necessarily imply losing information about the initial tree structure (simply due to the fact that there is a constraint on the number/range of child nodes?)
user2398029
CC BY-SA 3.0
2012-03-05T17:10:34.930Z
@SureshVenkat, see edited post for more info.
user2398029
CC BY-SA 3.0
2012-03-05T17:16:28.527Z
There's no reason that converting to a B-tree loses information. a B-tree merely collapses levels of the tree to take advantage of page sizes and block access. Look up 
"external memory data structures" for more on this.
Suresh Venkat
CC BY-SA 3.0
2012-03-05T18:38:17.767Z
@louism After your "conversion", do you only need efficient searches? Meaning no deletions and/or insertions are made after it.
Juho
CC BY-SA 3.0
2012-03-06T12:43:51.703Z
@mrm That's right.
user2398029
<reference-request><ds.data-structures>
Is it possible to convert any tree to a B-tree or an R-tree?
user2398029
# Is it possible to convert any tree to a B-tree or an R-tree?

(Asked by: username_0 on 2012-03-05)

I have a tree structure representing sentences. My tree's nodes are characterized by a type (sentence, phrase, or word), unique ID, text value and an arbitrary number of features. Each node has an arbitrary number of directed edges linking it to other nodes (i.e. children, parent and different grammatical relations such as subject\_of, complement\_of, etc.). Note that all these features are absolutely necessary to accurately represent the syntactical structure of a sentence.

Now, given such an initial tree with a totally unconstrained structure, I want to know if it is possible to convert that tree into a form that is more search-efficient (i.e. so that search involves less recursion). The only operation I *really* need to support is finding nodes with an arbitrary combination of type, id, value, and/or feature(s). I also need to be able to match a node back to the original tree if other operations are necessary. What is of primary importance is read-time and query efficiency.

From what I understand, B-trees and R-trees are generally search efficient. From Wikipedia, "like B-trees, this makes R-trees suitable for large data sets and databases, where nodes can be paged to memory when needed, and the whole tree cannot be kept in main memory." This is exactly the situation I am in right now. However, I have very limited knowledge of the different types of trees and how they convert to another.

So, I am wondering if it is possible in theory to convert any N-ary tree (i.e. in my case, a completely unconstrained tree with an arbitrary number of children, edges and features for each node) into a B-tree or an R-tree to make it more search efficient? How would one go about doing this?

**Tags:** reference-request, ds.data-structures
> **Comments:**
> **username_1**: What is the motivation for converting to an R-tree?  
> **username_0**: I am looking for a more efficient way to search a tree where the nodes each have an id, a value and multiple features. The tree is pretty deep and simple recursion has become completely inefficient.  
> **username_2**: What _exactly_ is a "feature"?  What _exactly_ does "search" mean?  _Exactly_ what operations do you want your data structure to support?  
> **username_0**: A feature can be any primitive data type - I'm working in Ruby, so that would be integers, strings, arrays or hashes. The most common search operation is to find nodes on the basis of a combination of id, value and/or features. But, in theory, I'd like any "standard" tree operation (iterate children, get next sibling, retrieve parent, etc.) to be supported. Hope that clarifies what I'm looking for.  
> **username_0**: And if I said something horrible that deserves downvoting on my first post here, please do explain. If the question doesn't make much sense, that's _precisely_ why I'm here.  
> **username_3**: What is it in particular about an R-tree that you like ? In general, B-trees are used for disk-efficient access to large sets of data  
> **username_0**: There is no pre-defined range of number of child nodes within my tree (which is used to represent the syntactic structure of documents), therefore (from what I understand), a B-tree isn't suitable.  
> **username_0**: Given an initial tree with an unconstrained structure, I want to convert that tree into a form that is more search-efficient (i.e. involves less recursion) but without losing any information about the way the tree was initially structured. I understand the concept of a B-tree, but it seems to me that converting to a B-tree would necessarily imply losing information about the initial tree structure (simply due to the fact that there is a constraint on the number/range of child nodes?)  
> **username_0**: @SureshVenkat, see edited post for more info.  
> **username_3**: There's no reason that converting to a B-tree loses information. a B-tree merely collapses levels of the tree to take advantage of page sizes and block access. Look up  "external memory data structures" for more on this.  
> **username_4**: @louism After your "conversion", do you only need efficient searches? Meaning no deletions and/or insertions are made after it.  
> **username_0**: @mrm That's right.  

---

## 2 answers

### Answer by username_5 on 2013-07-25. Score: 1

An N-ary tree is the general term describing a tree data structure containing/organizing a list of numbers.

A B-tree is an N-ary tree opimized for block/disk access. Each leaves contain ranges of elements.

An R-tree is an N-ary tree but the order imposed on the list of elements is no longer the "greater than" order on a list of numbers but a"close to" metric on points in 2D and more. The "close to" metric is approximated by bounding boxes. An R-tree can be implemented over a B-tree, technically speaking.

Furthermore, any data set in n-dimensions has representations in 1D. Therefore, given some metric, all these tree topologies are isomorphic...


---

### Answer by username_6 on 2012-03-05. Score: -3

Any data structure can be serialised to any data structure, provided that they can hold the same information.

**Insertion** works by locating the place to insert nodes through searching and insert.
If a node is full, then a split needs to be done.

**Splits** need to check every possible partition, giving optimal solution of `O(2^{M+1})`


---

