CODEWITHSUNDEEP
algorithmdata-structurestreegobinary-tree
bsr
bsr

Reputation: 58662

Suitable tree data structure

Which is the most suitable tree data structure to model a hierarchical (containment relationship) content. My language is bit informal as I don't have much theoretical background on these

  1. Parent node can have multiple children.
  2. Unique parent
  3. Tree structure is rarely changed, os it is ok to recreate than add/rearrange nodes.
  4. Two way traversal
  5. mainly interested in, find parent, find children, find a node with a unique id
  6. Every node has a unique id
  7. There might be only hundreds of nodes in total, so performance may not be big influence
  8. Persistence may be good to have, but not necessary as I plan to use it in memory after reading the data from DB.

My language of choice is go (golang), so available libraries are limited. Please give a recommendation without considering the language which best fit the above requirement.

http://godashboard.appspot.com/ lists some of the available tree libraries. Not sure about the quality and how active they are. I read god about

  1. https://github.com/petar/GoLLRB
  2. http://www.stathat.com/src/treap

Please let know any additional information required.

Upvotes: 1

Views: 2210

Answers (2)

nhahtdh
nhahtdh

Reputation: 56809

Since there are only hundreds of nodes, just make the structure the same as you have described.

  • Each node has a unique reference to parent node.
  • Each node has a list of child node.
  • Each node has an id
  • There is a (external) map from id --> node. May not even necessary.

2 way traversal is possible, since parent and child nodes are know. Same for find parent and find child.
Find id can be done by traverse the whole tree, if no map. Or you can use the map to quickly find the node.

Add node is easy, since there is a list in each node. Rearrange is also easy, since you can just freely add/remove from list of child nodes and reassign the parent node.

I'm answering this question from a language-agnostic aspect. This is a tree structure without any limit, so implementation is not that popular.

Upvotes: 3

Pranalee
Pranalee

Reputation: 3409

I think B-Tree is way to go for your requirements. http://en.wikipedia.org/wiki/B-tree

Point 1,2,3: B-Tree inherently support this. (multiple children, unique parent, allows insertion/deletion of elements

Point 4,5: each node will have pointers for its child by default implementation . Additionally you can maintain pointer of parent for each node. you can implement your search/travers operations with BFS/DFS with help of these pointers

Pomit 6: depends on implementation of your insert method if you dont allow duplicate records

Pont 7,8: not a issue as for you have mentioned that you have only hundreds of records. Though B-Trees are quite good data structure for external disk storage also.

Upvotes: 0

Related Questions