0
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • 1
    $\begingroup$ What is the motivation for converting to an R-tree? $\endgroup$
    – Joe
    Mar 5, 2012 at 3:43
  • $\begingroup$ 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. $\endgroup$
    – user2398029
    Mar 5, 2012 at 4:48
  • 4
    $\begingroup$ What exactly is a "feature"? What exactly does "search" mean? Exactly what operations do you want your data structure to support? $\endgroup$
    – Jeffε
    Mar 5, 2012 at 12:23
  • $\begingroup$ 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. $\endgroup$
    – user2398029
    Mar 5, 2012 at 12:56
  • 2
    $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Mar 5, 2012 at 17:16

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
-3
$\begingroup$

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})

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.