Algorithm for finding objects with varying degrees of specificity

0
votes

I have a large number of objects arranged in a tree-like structure (each node on the tree has parents and children, starting with one master node, and ending in many child nodes). Each object has it's own ID in the form of a string, and there are many duplicate IDs, but no duplicates sunder the same parent. Example:

ParentA:

  • childA
  • childB
  • childD

ParentB:

  • childA
  • childC
  • childD

The tree is also many layers deep.

I need a method of finding objects that will work like this (example is based on the previous list):

Example 1:

  1. an ArrayList with the string {"childB"} is passed to the algorithm
  2. there are no duplicate nodes with an ID of "childB", so a refrence to childB is returned

Example 2:

  1. an ArrayList with the strings {"parentA", "childD"} is passed to the algorithm
  2. there are no duplicate nodes with an ID of "childD" AND a parent with an ID of "parentA", so a reference to the given node is returned

Example 3:

  1. an ArrayList with the string {"childD"} is passed to the algorithm
  2. there are duplicate nodes with an ID of "childD" so the algorithm requests for more information (the name of the parent(s))

Keep in mind that there may be many levels of specificity, like {"nodeA", "nodeD", "nodeX", "nodeD"} so some kind of loop, or maybe a recursive method would be needed.

So, any ideas?

Update: I created a depth-first-search algorithm to go through each node on the tree, and it works very well. The algorithm returns all nodes in the form of one ArrayList All I need now is a way to select one based on varying degrees of specificity. Can anyone help with that? The above three examples show what I need.

1
javasearch
"some kind of loop [...] would be needed." Absolutely. Have you tried writing the code for that loop? Do you encounter any specific issues? Unless you show the code you have tried so far, your question will likely get closed as too vague or too broad. – assylias
I have a loop that can look through each node on the tree and return a matched node, or give an error if the request was not specific enough, but I am having trouble on creating a loop that works with multiple request strings {"nodeA", "nodeB"}. Basicly, I don't know where to start. – Ben Cracknell
It's a bit vague to me what are you trying to accomplish. From your question, it looks like you are trying perform a search for an id in your tree. Also, in example 2, you are mentioning "a reference to the given node", which is also vague. Are you trying to build an algorthim to search family trees? – ioreskovic
Basically I need an algorithm that can search a tree of ID strings, but if I pass the algorithm multiple strings, it narrows down the search. – Ben Cracknell
And the ID's in a list are ordered and such order should appear when traversing through the tree depth-first? – ioreskovic

1 Answers

-1
votes

depth-first search algorithm may be helpful for you!!!