Algorithm for parsing a plane tree into a non-timber tree
I have the following flat tree:
id name parent_id is_directory
===========================================================
50 app 0 1
31 controllers 50 1
11 application_controller.rb 31 0
46 models 50 1
12 test_controller.rb 31 0
31 test.rb 46 0
and I'm trying to figure out an algorithm to get it into the following tree structure:
[{
id: 50,
name: app,
is_directory: true
children: [{
id: 31,
name: controllers,
is_directory: true,
children: [{
id: 11,
name: application_controller.rb
is_directory: false
},{
id: 12,
name: test_controller.rb,
is_directory: false
}],
},{
id: 46,
name: models,
is_directory: true,
children: [{
id: 31,
name: test.rb,
is_directory: false
}]
}]
}]
Can anyone point me in the right direction? I'm looking for steps (e.g. build an associative array, loop through an array looking for x, etc.).
I am using Ruby so I have object oriented language features.
a source to share
In ruby, you can easily do this in O (n) linear time using Hash.
# Put all your nodes into a Hash keyed by id This assumes your objects are already Hashes
object_hash = nodes.index_by {|node| node[:id]}
object_hash[0] = {:root => true}
# loop through each node, assigning them to their parents
object_hash.each_value {|node|
continue if node[:root]
children = object_hash[node[:parent_id]][:children] ||= []
children << node
}
#then your should have the structure you want and you can ignore 'object_hash' variable
tree = object_hash[0]
a source to share
I researched the problem with recursive and non-recursive. I put 2 options here:"parend_id" = "head_id" # for those examples
Recursivly:
require 'pp'
nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil},
{"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"},
{"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}]
def to_tree(nodes, head_id = nil)
with_head, without_head = nodes.partition { |n| n['head_id'] == head_id }
with_head.map do |node|
node.merge('children' => to_tree(without_head, node['id']))
end
end
pp to_tree(nodes)
Pros:
- how it should be
Minuses:
- Ruby will crash if we have > = 3000 nodes (this is because ruby has a stack limit for points (functions) when ruby returns must be repeated) If you have "pp" to output it will tolerate fail at = 200 nodes
Not recursively, with a loop:
require 'pp'
nodes = [{"id"=>"1", "name"=>"User №1 Pupkin1", "head_id"=>nil},
{"id"=>"2", "name"=>"User №2 Pupkin2", "head_id"=>"1"},
{"id"=>"3", "name"=>"User №3 Pupkin3", "head_id"=>"2"}]
def to_tree(data)
data.each do |item|
item['children'] = data.select { |_item| _item['head_id'] == item['id'] }
end
data.select { |item| item['head_id'] == nil }
end
pp to_tree(nodes)
Pros:
- more ruby style
Minuses:
- we are modifying the self object which is not good enough.
The result of both ways:
[{"id"=>"1",
"name"=>"User №1 Pupkin1",
"head_id"=>nil,
"children"=>
[{"id"=>"2",
"name"=>"User №2 Pupkin2",
"head_id"=>"1",
"children"=>
[{"id"=>"3",
"name"=>"User №3 Pupkin3",
"head_id"=>"2",
"children"=>[]}]}]}]
Summary
For production it is better to use the second method, perhaps there is a better way to implement it.
Hope it will be helpful
a source to share
- Create a stack and fill it with the root element.
- While (there are elements on the stack):
- Pop the item off the stack and add it where it belongs to the tree.
- Find all the children of this element in your array and push them onto the stack.
To add an element to the tree (step 3), you first need to find its parent. The tree data structure should allow you to do this fairly quickly, or you can use a dictionary containing the tree nodes indexed by an identifier.
If you indicate which language you are using a more specific solution can be suggested.
a source to share
Here are a few changes I had to make to @ daniel-beardsley's answer to get it working for me.
1) Since I started with an activeRecord relationship, I started by creating an as_json to convert to hash. Note that all keys were therefore strings and not characters.
2) in my case, non-parent elements had a parent value of nil, not 0.
3) I got a compile error in the "continue" statement so I changed it to "next" ( can someone explain this to me ), maybe it was @ daniel- beardsley's typo when converting to ruby?)
4) I was getting some crashes for items with deleted parents. I've added code to ignore them - you could also put in the root if you prefer
object_hash = myActiveRecordRelation.as_json.index_by {|node| node["id"]}
object_hash[nil] = {:root => true}
object_hash.each_value {|node|
next if node[:root]
next if node["parent_id"] && !object_hash[node["parent_id"]] # throw away orphans
children = object_hash[node["parent_id"]][:children] ||= []
children << node
}
tree = object_hash[nil]
a source to share