One of the complex data-structure issues is accessing the multilevel tree that could have n number of children. We have faced a similar concern while designing the multilevel n children for the groups.
Approach:
To solve the problem we designed a depth-index map approach.
Problem:
At any point in time, we have the information for the current node selected in a tree and we want to perform a CRUD operation on it. It would be a really bad approach if we do fetch the server again to get the tree structure after performing the CRUD to get back the clean the structure of the tree.
Solution:
Now the problem was how to identify which node. This might be intensive if the operation is done on the last child of the last node or so on. The complexity of traversal to each node is number of nodes in the tree. Instead, we can leverage with space in this case and have an index-depth defined for each node in the tree.
Data-structure Used:
At each level, we are defining a map that will consist of what index it is. So if a node is at level 0, it will have an array that will just capture the index of what child it is to the root(i.e. its parent). [n]. Likewise, if the nth-child of level 0 is having m children the children will have a map like [n,m]. and lth child of m will have a map like [n,m,l]
Code Snippet for traversal:
var
traverseTree =
function
(tree,node){
var
i;
var
maplength = node.map.length;
level = tree;
for
(i = 0; i<maplength-1; i++){
level = level.nodes[node.map[i]];
}
return
level;
};
Complexity:
Going ahead with the approach complexity of accessing a node reduces to its level in the tree.
Other Approaches and Advantage over them
There are many other libraries available like DefiantJS, Underscore.js, lodash that deals with the data and claims to be finding the element in minimalist complexity. But the problem defined for these libraries were different. These libraries just act on finding the element and not on the CRUD operation done on these.
DefiantJS claims it could find the element in complex JSON in minimal Complexity. they have API defined only for search and not for CRUD operation. In the library, for searching the complex JSON is converted to XML and with provide XPATH, the element could be returned in minimal complexity. But if we want to perform CRUD converting the whole JSON to XML and XML to JSON back will be intensive operation. Thus we can’t extend DefiantJS as well.
The Underscore and lodash claim to address the CRUD operation for array and not the collection. where the data structure in the defined problem set was the collection that has nodes within the node.