Data structures (trees)

  • #1

Main Question or Discussion Point

i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??
 

Answers and Replies

  • #2
1,516
617
What circumstances would you use such a data structure? Sounds like a relational database.
 
  • #3
What circumstances would you use such a data structure? Sounds like a relational database.
i am not planning now to use this but as a concept i want to know is this right or wrong
 
  • #4
[...]
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??
That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).
 
Last edited:
  • #5
That would imply multiple roots and is not allowed (see definition section):
https://en.wikipedia.org/w/index.php?title=Tree_(data_structure)&oldid=712433755#Definition

In a tree a node has at most a single parent, which is also mentioned in the article linked above.

You can have multiple (read a collection of) trees though, but those aren't interconnected then and don't count as a (single) tree (see 5th graphic in definition section).
so what does an unrooted tree exactly mean ?
 
  • #6
  • #7
Filip Larsen
Gold Member
1,237
169
In graph terminology, any graph without cycles is a tree. As a data structure, the navigability between nodes, like parent and child relations, usually express some kind of hierarchy between nodes which comes "on top" of the tree graph in order to serve some purpose, like for instance expressing a search tree. In principle you could have tree data structures with many or no roots depending on what the relationship means.
 
  • #8
1,516
617
Usually the point of a tree is to know where you came from, which implies a single parent. If you're just wanting to conserve space, you could wrap all of your nodes in a reference counter.
 
  • #9
87
138
Supposing your current concern is about computational molecular biology, particularly algorithmic approaches available to building phylogenetic trees.
i know that a node cannot have more than one parent given that these parents have common ancestor (because this is undirected cycle and a tree must have no cycles).
Yes, that is partly true about the inadequacy of using phylogenetic trees alone to represent the histories of species in question. As a matter of fact, two daughter branches may have only one parent in a binary tree.
but can a node have more than one parent given that these parents don't have common ancestor (which will produce an unrooted tree i think) ??
There are actually several types of trees used to model species relationships in phylogenetic study. The most commonly mentioned ones are rooted and unrooted trees, either of which can't be used to fully model outcomes of such events of the so-called reticulate evolution as gene transfer, hybridization, recombination, reassortment etc. These are what your concern is exactly about that whether or not a child can have two parents at the same time. We therefore have to opt to choose a better modeling tool called a phylogenetic network instead, which is also a graph being again as either rooted (e.g split, median, quasi-median, etc.) or unrooted (e.g haplotype, reticulograms) one. You can google on these terms to learn more about their applications in practice.
 
  • #10
harborsparrow
Gold Member
533
108
I seem to recall that C++ allows multiple inheritance, which may be an example of what you are referring to. For example, a given object O can inherit properties from two different ancestors. It can also be the parent of multiple descendants. For a designer point of view, this turned out to be a prescription for disaster, which is why most OO languages do NOT support multiple inheritance. So we're not talking trees, per se, but once you start doing that, you no longer have a tree, as was pointed out above. You just have a graph. And you can try to avoid cycles in it, but it's not what is called a "tree" any longer in strict comp. sci. terminology.
 

Related Threads for: Data structures (trees)

  • Last Post
Replies
3
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
7
Views
4K
  • Last Post
Replies
5
Views
4K
Replies
4
Views
4K
  • Last Post
Replies
8
Views
2K
Replies
5
Views
2K
Replies
11
Views
1K
Top