Comment construire efficacement un arbre à partir d'une structure plane?

Question

J'ai un tas d'objets dans une structure plate. Ces objets ont une propriété ID et une propriété ParentID afin qu'ils puissent être disposés dans des arbres. Ils ne sont pas dans un ordre particulier. Chaque propriété ParentID ne correspond pas nécessairement à ID dans la structure. Par conséquent, leur pourrait être plusieurs arbres émergeant de ces objets.

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

Je ne suis pas loin d'être une solution, mais je suis sûr qu'il est loin d'être optimale ...

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

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

Answer 1

Stocke les ID des objets dans un mappage de table de hachage à l'objet spécifique. Énumérer tous les objets et trouver leur parent s'il existe et mettre à 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<Node> Children = new List<Node>(); 
    public Node Parent { get; set; } 
    public MyObject AssociatedObject { get; set; } 
} 

IEnumerable<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects) 
{ 
    Dictionary<int, Node> lookup = new Dictionary<int, Node>(); 
    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); 
} 

Answer 2

Vague comme la question me semble, je créerais probablement une carte de l'ID à l'objet réel. Dans pseudo-java (je n'ai pas vérifié si cela fonctionne/compiles), il pourrait être quelque chose comme:

Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>(); 

for (FlatObject object: flatStructure) { 
    flatObjectMap.put(object.ID, object); 
} 

Et pour regarder chaque parent:

private FlatObject getParent(FlatObject object) { 
    getRealObject(object.ParentID); 
} 

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

En réutilisant getRealObject(ID) et de faire un map de l'objet à une collection d'objets (ou leurs ID), vous obtenez également une carte parent-> enfants.

Answer 3

Êtes-vous bloqué en utilisant uniquement ces attributs? Si ce n'est pas le cas, il peut être intéressant de créer un tableau de nœuds enfants, dans lequel vous pouvez faire défiler tous ces objets une fois pour créer de tels attributs. De là, sélectionnez le nœud avec les enfants mais pas de parents et itérativement construire votre arbre de haut en bas.

Answer 4

Je peux le faire dans 4 lignes de code et dans l'heure O (n log n), en supposant que Dictionary soit quelque chose comme une 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 parentIDs sont faux, alors oubliez ce qui précède, et le font:

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. 

Answer 5

La plupart des réponses supposent que vous cherchez à faire ceci en dehors de la base de données. Si vos arbres sont de nature relativement statique et que vous avez juste besoin de mapper les arbres dans la base de données, vous pouvez envisager d'utiliser des représentations d'ensemble imbriquées du côté de la base de données. Consultez les livres de Joe Celko (ou here pour un aperçu par Celko).

Si lié à Oracle dbs de toute façon, consultez leur CONNECT BY pour les approches SQL directes.

Avec l'une ou l'autre approche, vous pouvez complètement ignorer la cartographie des arbres avant de charger les données dans la base de données. Je pensais que je proposerais cela comme une alternative, il peut être complètement inapproprié pour vos besoins spécifiques. La partie «ordre approprié» de la question initiale implique que vous avez besoin que l'ordre soit «correct» dans la base de données pour une raison quelconque?Cela pourrait me pousser à manipuler les arbres là aussi.

Answer 6

Voici un algorithme simple JavaScript pour analyser une table plate dans une structure d'arbre parent/enfant qui court dans le temps N:

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); 

Answer 7

Sur la base de la réponse de Mehrdad Afshari et le commentaire d'Andrew Hanlon pour un 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<Node> Children = new List<Node>(); 
    public Node Parent { get; set; } 
    public MyObject Source { get; set; } 
} 

List<Node> BuildTreeAndGetRoots(List<MyObject> actualObjects) 
{ 
    var lookup = new Dictionary<int, Node>(); 
    var rootNodes = new List<Node>(); 

    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; 
} 

Answer 8

j'ai écrit une solution générique en C# vaguement basé sur la réponse @Mehrdad Afshari:

void Example(List<MyObject> actualObjects) 
{ 
    List<TreeNode<MyObject>> treeRoots = actualObjects.BuildTree(obj => obj.ID, obj => obj.ParentID, -1); 
} 

public class TreeNode<T> 
{ 
    public TreeNode(T value) 
    { 
    Value = value; 
    Children = new List<TreeNode<T>>(); 
    } 

    public T Value { get; private set; } 
    public List<TreeNode<T>> Children { get; private set; } 
} 

public static class TreeExtensions 
{ 
    public static List<TreeNode<TValue>> BuildTree<TKey, TValue>(this IEnumerable<TValue> objects, Func<TValue, TKey> keySelector, Func<TValue, TKey> parentKeySelector, TKey defaultKey = default(TKey)) 
    { 
    var roots = new List<TreeNode<TValue>>(); 
    var allNodes = objects.Select(overrideValue => new TreeNode<TValue>(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; 
    } 
} 

Answer 9

Ce n'est pas exactement la même chose que ce que le demandeur a cherché, mais j'avais du mal envelopper ma tête les réponses ambiguës formulées ici, et je pense toujours que cette réponse s'inscrit sous le titre.

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

var rootNodes = new List<DTIntranetMenuItem>(); 
var dictIntranetMenuItems = new Dictionary<long, DTIntranetMenuItem>(); 

//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<tblIntranetMenuItem> 
{ 
    //Automapper (nuget) 
    DTIntranetMenuItem intranetMenuItem = 
            Mapper.Map<DTIntranetMenuItem>(efIntranetMenuItem); 
    intranetMenuItem.Children = new List<DTIntranetMenuItem>(); 
    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; 

Answer 10

la version JS qui retourne une racine ou un tableau de racines dont chacune aura une propriété de tableau enfants contenant les associés enfants. Ne dépend pas d'une entrée ordonnée, compacte décemment, et n'utilise pas de 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 Strings', 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) 

Answer 11

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": {} 
      } 
     } 
    } 
} 

Answer 12

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

Gardez à l'esprit que cette solution ne fonctionne que si la table est trié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<int, Node>{ 
    { 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 noeud est défini comme suit.

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