2

For the structure given in below data model, where each node is,

type Person {
       firstName,
       lastName,
       Pointer to list of his children,
       Pointer to next node
 }

enter image description here

This data model neither looks like tree nor graph.

what is the name of this data model?

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
overexchange
  • 15,768
  • 30
  • 152
  • 347

2 Answers2

7

This is a tree in the left-child right-sibling representation.

A multi-child tree basically needs a dynamic data structure within each node to represent the children. Sometimes, fixed-size nodes are preferred for various reasons. This representation allows doing so in a fixed amount of space per node - the first child only is recorded, and all the children form a linked list. Obviously, searching the children of a node in this representation, is linear in the number of children.

Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • 1) Can I call it as left-child right-sibling n-ary tree? I read wiki. What is the advantage in showing as "left-child right-sibling" representation instead of "n-ary" tree representation? Any advantage in terms of read/write performance? – overexchange Aug 27 '16 at 06:41
  • 1
    @overexchange No, not really. It is marginally useful when memory is extremely scarce and dynamic allocations are a problem. See [here](http://stackoverflow.com/questions/14015525/what-is-the-left-child-right-sibling-representation-of-a-tree-why-would-you-us) too. – Ami Tavory Aug 27 '16 at 06:43
0

Looks like a Directed acyclic graph to me.

https://en.wikipedia.org/wiki/Directed_acyclic_graph

cloudcal
  • 505
  • 1
  • 4
  • 9