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?

Christophe
  • 74,672
  • 10
  • 115
  • 187
Daniel
  • 699
  • 4
  • 13
  • 5
    It's not bit like a trie, it is a trie. – vartec Mar 19 '12 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 '12 at 17:06
  • Does a trie require a common root? – Daniel Mar 19 '12 at 17:06
  • 1
    @Daniel: [Wikipedia says yes.](http://en.wikipedia.org/wiki/Trie) – Robert Harvey Mar 19 '12 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 '12 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 '12 at 17:19

3 Answers3

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

Sonia
  • 231
  • 1
  • 3
  • 1
    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. –  Mar 19 '12 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.

Izkata
  • 6,048
  • 6
  • 28
  • 43
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.

Robert Harvey
  • 198,589
  • 55
  • 464
  • 673
DeadMG
  • 36,794
  • 8
  • 70
  • 139