Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Data structures (trees)

  1. Apr 21, 2016 #1
    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) ??
     
  2. jcsd
  3. Apr 21, 2016 #2
    What circumstances would you use such a data structure? Sounds like a relational database.
     
  4. Apr 21, 2016 #3
    i am not planning now to use this but as a concept i want to know is this right or wrong
     
  5. Apr 21, 2016 #4
    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: Apr 21, 2016
  6. Apr 21, 2016 #5
    so what does an unrooted tree exactly mean ?
     
  7. Apr 21, 2016 #6
  8. Apr 22, 2016 #7

    Filip Larsen

    User Avatar
    Gold Member

    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.
     
  9. Apr 22, 2016 #8
    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.
     
  10. Apr 23, 2016 #9
    Supposing your current concern is about computational molecular biology, particularly algorithmic approaches available to building phylogenetic trees.
    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.
    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.
     
  11. May 5, 2016 #10

    harborsparrow

    User Avatar
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Data structures (trees)
Loading...