Comment construire efficacement un arbre à partir d’une structure plate?

J’ai un tas d’objects dans une structure plate. Ces objects ont un ID et une propriété ParentID afin qu’ils puissent être organisés en arborescence. Ils ne sont pas en ordre particulier. Chaque propriété ParentID ne correspond pas nécessairement à un ID dans la structure. Par conséquent, ils pourraient être plusieurs arbres émergeant de ces objects.

Comment traiteriez-vous ces objects pour créer les arbres résultants?

Je ne suis pas si loin d’une solution mais je suis sûr que c’est loin d’être optimal …

Je dois créer ces arbres pour insérer des données dans une firebase database, dans le bon ordre.

Il n’y a pas de références circulaires. Un nœud est un nœud racine lorsque ParentID == null ou lorsque ParentID ne peut pas être trouvé dans les autres objects

Stocker les ID des objects dans un mappage de table de hachage vers l’object spécifique. Énumérez tous les objects et trouvez leur parent s’il existe et mettez à jour son pointeur parent en conséquence.

 class MyObject { // The actual object public int ParentID { get; set; } public int ID { get; set; } } class Node { public List Children = new List(); public Node Parent { get; set; } public MyObject AssociatedObject { get; set; } } IEnumerable BuildTreeAndGetRoots(List actualObjects) { Dictionary lookup = new Dictionary(); actualObjects.ForEach(x => lookup.Add(x.ID, new Node { AssociatedObject = x })); foreach (var item in lookup.Values) { Node proposedParent; if (lookup.TryGetValue(item.AssociatedObject.ParentID, out proposedParent)) { item.Parent = proposedParent; proposedParent.Children.Add(item); } } return lookup.Values.Where(x => x.Parent == null); } 

Sur la base de la réponse de Mehrdad Afshari et du commentaire d’Andrew Hanlon pour une accélération, voici ma prise.

Différence importante par rapport à la tâche d’origine: Un nœud racine a ID == parentID.

 class MyObject { // The actual object public int ParentID { get; set; } public int ID { get; set; } } class Node { public List Children = new List(); public Node Parent { get; set; } public MyObject Source { get; set; } } List BuildTreeAndGetRoots(List actualObjects) { var lookup = new Dictionary(); var rootNodes = new List(); foreach (var item in actualObjects) { // add us to lookup Node ourNode; if (lookup.TryGetValue(item.ID, out ourNode)) { // was already found as a parent - register the actual object ourNode.Source = item; } else { ourNode = new Node() { Source = item }; lookup.Add(item.ID, ourNode); } // hook into parent if (item.ParentID == item.ID) { // is a root node rootNodes.Add(ourNode); } else { // is a child row - so we have a parent Node parentNode; if (!lookup.TryGetValue(item.ParentID, out parentNode)) { // unknown parent, construct preliminary parent parentNode = new Node(); lookup.Add(item.ParentID, parentNode); } parentNode.Children.Add(ourNode); ourNode.Parent = parentNode; } } return rootNodes; } 

Voici un algorithme JavaScript simple pour parsingr une table plate dans une arborescence parent / enfant qui s’exécute en N temps:

 var table = [ {parent_id: 0, id: 1, children: []}, {parent_id: 0, id: 2, children: []}, {parent_id: 0, id: 3, children: []}, {parent_id: 1, id: 4, children: []}, {parent_id: 1, id: 5, children: []}, {parent_id: 1, id: 6, children: []}, {parent_id: 2, id: 7, children: []}, {parent_id: 7, id: 8, children: []}, {parent_id: 8, id: 9, children: []}, {parent_id: 3, id: 10, children: []} ]; var root = {id:0, parent_id: null, children: []}; var node_list = { 0 : root}; for (var i = 0; i < table.length; i++) { node_list[table[i].id] = table[i]; node_list[table[i].parent_id].children.push(node_list[table[i].id]); } console.log(root); 

Solution Python

 def subtree(node, relationships): return { v: subtree(v, relationships) for v in [x[0] for x in relationships if x[1] == node] } 

Par exemple:

 # (child, parent) pairs where -1 means no parent flat_tree = [ (1, -1), (4, 1), (10, 4), (11, 4), (16, 11), (17, 11), (24, 17), (25, 17), (5, 1), (8, 5), (9, 5), (7, 9), (12, 9), (22, 12), (23, 12), (2, 23), (26, 23), (27, 23), (20, 9), (21, 9) ] subtree(-1, flat_tree) 

Produit:

 { "1": { "4": { "10": {}, "11": { "16": {}, "17": { "24": {}, "25": {} } } }, "5": { "8": {}, "9": { "20": {}, "12": { "22": {}, "23": { "2": {}, "27": {}, "26": {} } }, "21": {}, "7": {} } } } } 

Version JS qui renvoie une racine ou un tableau de racines ayant chacun une propriété de tableau Children contenant les enfants associés. Ne dépend pas d’une entrée ordonnée, décemment compacte et n’utilise pas la récursivité. Prendre plaisir!

 // creates a tree from a flat set of hierarchically related data var MiracleGrow = function(treeData, key, parentKey) { var keys = []; treeData.map(function(x){ x.Children = []; keys.push(x[key]); }); var roots = treeData.filter(function(x){return keys.indexOf(x[parentKey])==-1}); var nodes = []; roots.map(function(x){nodes.push(x)}); while(nodes.length > 0) { var node = nodes.pop(); var children = treeData.filter(function(x){return x[parentKey] == node[key]}); children.map(function(x){ node.Children.push(x); nodes.push(x) }); } if (roots.length==1) return roots[0]; return roots; } // demo/test data var treeData = [ {id:9, name:'Led Zep', parent:null}, {id:10, name:'Jimmy', parent:9}, {id:11, name:'Robert', parent:9}, {id:12, name:'John', parent:9}, {id:8, name:'Elec Gtr Ssortingngs', parent:5}, {id:1, name:'Rush', parent:null}, {id:2, name:'Alex', parent:1}, {id:3, name:'Geddy', parent:1}, {id:4, name:'Neil', parent:1}, {id:5, name:'Gibson Les Paul', parent:2}, {id:6, name:'Pearl Kit', parent:4}, {id:7, name:'Rickenbacker', parent:3}, {id:100, name:'Santa', parent:99}, {id:101, name:'Elf', parent:100}, ]; var root = MiracleGrow(treeData, "id", "parent") console.log(root) 

J’ai trouvé une version JavaScript géniale ici: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

Disons que vous avez un tableau comme celui-ci:

 const models = [ {id: 1, title: 'hello', parent: 0}, {id: 2, title: 'hello', parent: 0}, {id: 3, title: 'hello', parent: 1}, {id: 4, title: 'hello', parent: 3}, {id: 5, title: 'hello', parent: 4}, {id: 6, title: 'hello', parent: 4}, {id: 7, title: 'hello', parent: 3}, {id: 8, title: 'hello', parent: 2} ]; 

Et vous voulez avoir les objects nesteds comme ceci:

 const nestedStructure = [ { id: 1, title: 'hello', parent: 0, children: [ { id: 3, title: 'hello', parent: 1, children: [ { id: 4, title: 'hello', parent: 3, children: [ {id: 5, title: 'hello', parent: 4}, {id: 6, title: 'hello', parent: 4} ] }, {id: 7, title: 'hello', parent: 3} ] } ] }, { id: 2, title: 'hello', parent: 0, children: [ {id: 8, title: 'hello', parent: 2} ] } ]; 

Voici une fonction récursive qui rend cela possible.

 function getNestedChildren(models, parentId) { const nestedTreeStructure = []; const length = models.length; for (let i = 0; i < length; i++) { // for-loop for perf reasons, huge difference in ie11 const model = models[i]; if (model.parent == parentId) { const children = getNestedChildren(models, model.id); if (children.length > 0) { model.children = children; } nestedTreeStructure.push(model); } } return nestedTreeStructure; } 

Usuage:

 const models = [ {id: 1, title: 'hello', parent: 0}, {id: 2, title: 'hello', parent: 0}, {id: 3, title: 'hello', parent: 1}, {id: 4, title: 'hello', parent: 3}, {id: 5, title: 'hello', parent: 4}, {id: 6, title: 'hello', parent: 4}, {id: 7, title: 'hello', parent: 3}, {id: 8, title: 'hello', parent: 2} ]; const nestedStructure = getNestedChildren(models, 0); 

Aussi vague que la question me semble, je créerais probablement une carte de l’ID à l’object réel. En pseudo-java (je n’ai pas vérifié si cela fonctionne / comstack), ça pourrait être quelque chose comme:

 Map flatObjectMap = new HashMap(); for (FlatObject object: flatStructure) { flatObjectMap.put(object.ID, object); } 

Et pour rechercher chaque parent:

 private FlatObject getParent(FlatObject object) { getRealObject(object.ParentID); } private FlatObject getRealObject(ID objectID) { flatObjectMap.get(objectID); } 

En réutilisant getRealObject(ID) et en effectuant un mappage entre un object et une collection d’objects (ou leurs identifiants), vous obtenez également une carte parent-> enfants.

J’ai écrit une solution générique en C # vaguement basée sur la réponse de @Mehrdad Afshari:

 void Example(List actualObjects) { List> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1); } public class TreeNode { public TreeNode(T value) { Value = value; Children = new List>(); } public T Value { get; private set; } public List> Children { get; private set; } } public static class TreeExtensions { public static List> BuildTree(this IEnumerable objects, Func keySelector, Func parentKeySelector, TKey defaultKey = default(TKey)) { var roots = new List>(); var allNodes = objects.Select(overrideValue => new TreeNode(overrideValue)).ToArray(); var nodesByRowId = allNodes.ToDictionary(node => keySelector(node.Value)); foreach (var currentNode in allNodes) { TKey parentKey = parentKeySelector(currentNode.Value); if (Equals(parentKey, defaultKey)) { roots.Add(currentNode); } else { nodesByRowId[parentKey].Children.Add(currentNode); } } return roots; } } 

Pour toute personne intéressée par une version C # de la solution d’Eugene, notez que node_list est accessible en tant que carte, utilisez donc plutôt un dictionnaire.

Gardez à l’esprit que cette solution ne fonctionne que si la table est sortingée par parent_id .

 var table = new[] { new Node { parent_id = 0, id = 1 }, new Node { parent_id = 0, id = 2 }, new Node { parent_id = 0, id = 3 }, new Node { parent_id = 1, id = 4 }, new Node { parent_id = 1, id = 5 }, new Node { parent_id = 1, id = 6 }, new Node { parent_id = 2, id = 7 }, new Node { parent_id = 7, id = 9 }, new Node { parent_id = 8, id = 9 }, new Node { parent_id = 3, id = 10 }, }; var root = new Node { id = 0 }; var node_list = new Dictionary{ { 0, root } }; foreach (var item in table) { node_list.Add(item.id, item); node_list[item.parent_id].children.Add(node_list[item.id]); } 

Le nœud est défini comme suit.

 class Node { public int id { get; set; } public int parent_id { get; set; } public List children = new List(); } 

Êtes-vous coincé en utilisant uniquement ces atsortingbuts? Sinon, il peut être intéressant de créer un tableau de nœuds enfants, dans lequel vous pouvez parcourir tous ces objects une fois pour créer de tels atsortingbuts. A partir de là, sélectionnez le nœud avec les enfants mais pas les parents et construisez de manière itérative votre arbre de haut en bas.

Je peux le faire en 4 lignes de code et en O (n log n), en supposant que ce Dictionnaire ressemble à un TreeMap.

 dict := Dictionary new. ary do: [:each | dict at: each id put: each]. ary do: [:each | (dict at: each parent) addChild: each]. root := dict at: nil. 

EDIT : Ok, et maintenant je lis que certains parents sont faux, alors oubliez ce qui précède, et faites ceci:

 dict := Dictionary new. dict at: nil put: OrderedCollection new. ary do: [:each | dict at: each id put: each]. ary do: [:each | (dict at: each parent ifAbsent: [dict at: nil]) add: each]. roots := dict at: nil. 

La plupart des réponses supposent que vous cherchiez à le faire en dehors de la firebase database. Si vos arborescences sont de nature relativement statique et qu’il vous suffit de les mapper dans la firebase database, vous pouvez envisager d’utiliser des représentations d’ensemble nestedes du côté de la firebase database. Découvrez les livres de Joe Celko (ou ici pour un aperçu de Celko).

Si vous êtes lié à Oracle dbs, consultez leur version de CONNECT BY pour des approches SQL simples.

Avec l’une ou l’autre approche, vous pouvez complètement ignorer le mappage des arborescences avant de charger les données dans la firebase database. Juste pensé que je proposerais cela comme une alternative, il peut être complètement inapproprié pour vos besoins spécifiques. Toute la partie “ordre correct” de la question initiale implique quelque peu que vous ayez besoin que l’ordre soit “correct” dans la firebase database pour une raison quelconque? Cela pourrait me pousser à manipuler les arbres là aussi.

Ce n’est pas exactement la même chose que ce que le demandeur recherchait, mais j’ai eu du mal à comprendre les réponses formulées avec ambiguïté fournies ici, et je pense toujours que cette réponse correspond au titre.

Ma réponse est de mapper une structure plate sur un arbre directement sur object où tout ce que vous avez est un ParentID sur chaque object. ParentID est null ou 0 s’il s’agit d’une racine. En face du demandeur, je suppose que tous les ParentID valides de ParentID sont ParentID à quelque chose d’autre dans la liste:

 var rootNodes = new List(); var dictIntranetMenuItems = new Dictionary(); //Convert the flat database items to the DTO's, //that has a list of children instead of a ParentID. foreach (var efIntranetMenuItem in flatIntranetMenuItems) //List { //Automapper (nuget) DTIntranetMenuItem intranetMenuItem = Mapper.Map(efIntranetMenuItem); intranetMenuItem.Children = new List(); dictIntranetMenuItems.Add(efIntranetMenuItem.ID, intranetMenuItem); } foreach (var efIntranetMenuItem in flatIntranetMenuItems) { //Getting the equivalent object of the converted ones DTIntranetMenuItem intranetMenuItem = dictIntranetMenuItems[efIntranetMenuItem.ID]; if (efIntranetMenuItem.ParentID == null || efIntranetMenuItem.ParentID <= 0) { rootNodes.Add(intranetMenuItem); } else { var parent = dictIntranetMenuItems[efIntranetMenuItem.ParentID.Value]; parent.Children.Add(intranetMenuItem); //intranetMenuItem.Parent = parent; } } return rootNodes; 

voici une mise en œuvre ruby:

Il va cataloguer par nom d’atsortingbut ou le résultat d’un appel de méthode.

 CatalogGenerator = ->(depth) do if depth != 0 ->(hash, key) do hash[key] = Hash.new(&CatalogGenerator[depth - 1]) end else ->(hash, key) do hash[key] = [] end end end def catalog(collection, root_name: :root, by:) method_names = [*by] log = Hash.new(&CatalogGenerator[method_names.length]) tree = collection.each_with_object(log) do |item, catalog| path = method_names.map { |method_name| item.public_send(method_name)}.unshift(root_name.to_sym) catalog.dig(*path) << item end tree.with_indifferent_access end students = [#, #, #, #, #] catalog students, by: [:tenant_id, :status] # this would out put the following {"root"=> {95=> {"on_hold"=> [#]}, 6=> {"on_hold"=> [#, #]}, 15=> {"ready_for_match"=> [#]}, 10=> {"in_partnership"=> [#]}}}