3

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:

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

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?

Improve this question
6
  • 5
    It's not bit like a trie, it is a trie.
    – vartec
    Mar 19, 2012 at 17:03
  • 2
    @vartec: I think it would be more accurate to say that a trie could be one possible implementation.
    – Robert Harvey
    Mar 19, 2012 at 17:06
  • 1
    @Daniel: Wikipedia says yes.
    – Robert Harvey
    Mar 19, 2012 at 17:08
  • 1
    @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, 2012 at 17:10
  • 2
    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, 2012 at 17:19

3 Answers 3

Reset to default
5

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

Improve this answer
4
  • 1
    So you would just call it a "tree"?
    – Daniel
    Mar 19, 2012 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, 2012 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, 2012 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.
    – user8709
    Mar 19, 2012 at 18:13
3

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:

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

Improve this answer
0

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

http://en.wikipedia.org/wiki/Rope_(computer_science)

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

Improve this answer
1
  • 1
    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, 2012 at 19:36

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