Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It has a single root and each node has 0..N ordered sub-nodes . The keys represent a distinct set of paths. Two trees can only be merged if they share a common root. It needs to support, at minimum: insert, merge, enumerate paths.

For this tree:

 |        |                |
cat      cow              dog
 +        +--------+       +
 |        |        |       |
drinks   jumps    moos    barks

the paths would be:

  • The cat drinks milk
  • The cow jumps
  • The cow moos
  • The dog barks

It's a bit like a trie. What is it?

share|improve this question

closed as primarily opinion-based by MichaelT, Snowman, Bart van Ingen Schenau Dec 4 '15 at 19:42

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise.If this question can be reworded to fit the rules in the help center, please edit the question.

It's not bit like a trie, it is a trie. – vartec Mar 19 '12 at 17:03
@vartec: I think it would be more accurate to say that a trie could be one possible implementation. – Robert Harvey Mar 19 '12 at 17:06
@Daniel: Wikipedia says yes. – Robert Harvey Mar 19 '12 at 17:08
@RobertHarvey: It says the root is the empty string. Not so in my case. I see some other minor differences in the Wikipedia article, but it's probably similar enough to be--as you stated--a form of trie. – Daniel Mar 19 '12 at 17:10
The root.. well, you can add fake empty root, which wouldn't change much from logical point of view. Main difference is that in your example you deal with words instead of characters, but that also doesn't change much from logical point of view. – vartec Mar 19 '12 at 17:19

By Wikipedia, it looks like your tree is specified by the two properties arborescence and ordered tree (scroll down to find the definition "ordered tree or plane tree.")

share|improve this answer
So you would just call it a "tree"? – Daniel Mar 19 '12 at 17:52
Well, the second paragraph on the WP Tree page makes it sound like that, but no, "tree" is a more general term. A tree may or may not have these properties. The arborescence property is about having a single root and directed edges away from the root. The parent-child relationship forms these directed edges. The "ordered tree" property is about having an ordering among the children of a given node. – Sonia Mar 19 '12 at 18:02
One more clarification, note the two links under my answer are under (graph theory) and that the Tree page we're looking at now is under (data structure.) It probably is true that nearly all tree data structures have these two graph theory properties. If you're looking for the name of a data structure, this answer may not be the one you want. – Sonia Mar 19 '12 at 18:09
There are tree data structures where the arrows point towards the (multiple) roots. This happens in union-find, for example. I should have thought of that earlier. – Steve314 Mar 19 '12 at 18:13

This is very close to a Radix tree. The primary differences are that a normal radix tree wouldn't split on words, so the 'c' in both "cat" and "cow" would be the same node, and it only splits when necessary:

 |                         |
 c                        dog barks
 |               |                 
at drinks milk   ow               
                 |        |        
                jumps    moos         

I might describe what you have as a modified Radix tree, that is forced to use spaces as a delimiter. Regardless, it is some sort of "tree", so that should be sufficient to describe it if you have some extra explanation as to its structure.

share|improve this answer

This is called a "rope" when applied specifically to strings, I believe.

They offer vastly improved algorithmic complexity for many mutating operations over strings-as-arrays.

share|improve this answer
It's not a rope. A rope is just a "fat string;" it doesn't contain any logical relationships, per se. – Robert Harvey Mar 19 '12 at 19:36

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