Create a recursive structure from smoothing a DFS structure
Problem
I have the following tree:
2
/ \
3 5
/ / \
6 4 1
which is presented as follows and order :
id parent
------------
2 null
3 2
6 3
5 2
4 5
1 5
Purpose:
Store this smoothing tree in a recursive structure in O (n) (O (n * log (n)) is acceptable, but not very good) (I know how to solve it in O (n ^ 2) , but I stored the data in this DFS order to be able to "parse" it in a more efficient way). For example:.
class R {
int id;
List<R> children;
}
which looks like this in JSON form:
{
id: 2,
children: [
{
id: 3,
children: { ... }
},
{
id: 5,
children: { ... }
}
]
}
How can I do this? The programming language is not important because I can translate it to Java.
Java code:
R r = new R();
Map<Long, Line> map = createMap2();
List<Line> vals = new ArrayList<Line>(map.values());
r.id = vals.get(0).id;
vals.remove(0);
r.children = createResource(vals, r.id);
...
private static List<R> createResource(List<Line> l, Long pid) {
List<R> lr = new ArrayList<R>();
if ( l.size() > 0 ) {
Long id = l.get(0).id;
Long p = l.get(0).pid;
l.remove(0);
if ( pid.equals(p) ) {
R r = new R();
r.id = id;
r.children = createResource(l, id);
lr.add(r);
}
else {
return createResource(l, pid); // of course, this is not ok
}
}
return lr;
}
The problem in the above code is that in the recursive structure (R class) only 2
, 3
and are stored 6
. I want to store the whole structure of the anti-aliasing tree (many Line objects) in this recursive structure (R object), not just some of the nodes.
PS: The problem is simplified. I am not interested in specific solutions because there are many areas and thousands of records. I am also interested in solutions that are great for worst case scenarios (different types of trees) because it is a user guarantee.
source to share
I found a simple solution based on this "DFS" order.
This approach works even if I use a Line feature list or map.
private static List<R> createResource(List<Line> l, Long pid) {
List<R> lr = new ArrayList<R>();
for ( Line line : l ) {
if ( line is a children ) {
R r = new R();
r.id = id;
l.remove(0);
r.children = createResource(l, line.id);
lr.add(r);
}
}
return lr;
}
It seems to be in O (n ^ 2) because there is a loop for
+ recursion for all elements , but it is in O (n) . Due to the DFS ordering, the next element to be called createResource
is in the first position (0 -> O (1) ). Since recursion takes each element => complexity is O (n) .
But if the order is not DFS ordering (possibly in use Map
, which is not LinkedHashMap
), I recommend a solution that contains arrays for parents. (according to גלעד ברקן)
source to share
How about something like this? On the first pass, the parents are hashed as arrays of their children and the root is identified; in the second, starting at the root and for each of its children, insert a new object with its children, and so on:
To take your example, the first pass generated
parent_hash = {2:[3,5], 3:[6], 5:[4,1]}
root = 2
The second pass will look something like this:
object 2 -> object 3 -> object 6
-> object 5 -> object 4
-> object 1
done
source to share
The problem with your code is that after a record fails the condition p == pid
, it is lost forever. Instead of playing the recordings, you should break the loop and return immediately. The offending record must also be returned and processed by an appropriate R
upstream instance .
source to share
, node . 2 * + 1 2 * + 2. . - , . ( , .)
If you want a memory efficient way for large, unbalanced trees, then it might be wise to use the standard Node tree view. To convert from your list, you can use a HashMap as suggested by גלעד בר. However, if the id of the nodes is mostly contiguous (for example, an example where they are from 1 to 6), you can also just use an array where each index of the array i is used to store the node with the id of i. This will allow you to easily find the parent node and assign child nodes to it as they are created.
(cf.my A Guide to Trees for storing trees as arrays.)
source to share