Java - tree data structure with multiple nodes - how to search efficiently

Question

I am searching for a implementation/data structure for some categories and child categories that i have. I am thinking to use a search tree but not sure how to begin implementation.

Let me show you what the data looks like. its acutally coming to me as a json structure from back end but it looks like this:

  [
    {
      "id": 94,
      "category_name": "New In", //this is the category category_name
      "description": "",
      "children": [ //this is the category children which can also be a sub-category
        {
          "id": 322,
          "category_name": "New Studio",
          "description": "Chic, sophisticated and polished with a classic edge."
        },
        {
          "id": 365,
          "category_name": "New Soho",
          "description": "Fresh, eclectic, and trendy. Oozes effortless cool."
        },
        {
          "id": 809,
          "category_name": "Summer Collection",
          "description": "Your ultimate summer look"
        }
      ]
    },
    {
      "id": 12,
      "category_name": "Clothes",
      "description": "",
      "children": [
        {
          "id": 22,
          "category_name": "All Clothes",
          "description": ""
        },
        {
          "id": 63,
          "category_name": "Tops",
          "description": "",
          "children": [
            {
              "id": 5,
              "category_name": "All Tops",
              "description": ""
            }

          ]
        },
        {
          "id": 641,
          "category_name": "Accessories",
          "description": "",
          "children": [
            {
              "id": 61,
              "category_name": "All Accessories",
              "description": ""
            },
            {
              "id": 622,
              "category_name": "Jewelry",
              "description": "",
              "children": [ // here is an example of a child that is a sub-category also
                {
                  "id": 52,
                  "category_name": "All Jewelry",
                  "description": ""
                },
                {
                  "id": 68,
                  "name": "Necklaces",
                  "description": ""
                },
                {
                  "id": 69,
                  "name": "Bracelets",
                  "description": ""
                },

              ]
            },

  ]

so if i had to draw this out it would look something like this:

So i want to be able to get path to anything. So for example if i want to search for Necklaces, then i want as well as getting a necklace to get the path of : Categories/Accessories/Jewelry/Necklaces

Is there a built in data structure for this ? i am coding in java. I suppose i also need the nodes sorted in some kind of order maybe A-Z.

so far i have this:

class Node{
 String label;
 List<Node> children;
}

but then how to search ? and is there a better data structure ? I do not want to iterate over all the nodes during a search, is there a way to sort the tree so i dont have to do that ? How i have it now i'd have to iterate over all the children. is there a way to maybe sort alphaetically perhaps or some kind of sort that would make the lookup faster ?

Solution 1

You need two things for this:

In your Node object, have a reference to the parent node as well:

class Node{
    String label;
    List<Node> children;
    Node parent;
}

Create a HashMap that maps labels to the nodes:

HashMap<String, Node> labelsToNodes;

Then searching is done with the get() method in the HashMap. You get your category list by repeatedly getting the parent nodes. Let me know if you'd like the code for this and I'll add it (I'm short on time right now).

Solution 2

So far I do not know any Java built-in data structure that can handle what you are looking for. There are some tree implementations on github or this thread on stackoverflow will help you. But if I understood you right, you are also interested to have a well performing search on your tree. Sorting the tree does not completly solve this problem, because you still have to search every single subtree. Though it could significantly improve the search performance. But as far as I know there is no out of the box data structure in Java.

Another approach that came to my mind is to use a Map with your label and a reference to the according Node. However you would need a Tree where you can go from the leaves to the root node to get the full path and you have to take care of the duplicated information. E.g. if you delete a node, you also have to delete it in the map. If you also want to traversy the tree from the root you might build a bidirectional tree.

This is how my approach would look like:

class Node {
    String label;
    Node parent;
}

class Tree {
    HashMap<String, List<Node>> tree;
}

It is a List<Node> if you have multiple times the same label name. E.g. if you have necklaces at jewlery and summer collection

Solution 3

I had a project this semester for searching on trees. I used different kind of algorithms. For example, BFS or DFS it depends on what you want and how you want to move on nodes in your tree. But, I prefer IDS(Iterative deepening depth-first search). To use this algorithm you can access this links.

it is better to have father instead of children cause it works better and you will not run out of memory.
clip in Youtube to show IDS
complete teaching about IDS
There are other good algorithms if you want you can just ask me. You need to define a State class.

    class State{
    String name;
    State father;
    }