wake-up-neo.net

Wie baut man einen Baum effizient aus einer flachen Struktur?

Ich habe eine Reihe von Objekten in einer flachen Struktur. Diese Objekte haben eine ID- und eine ParentID-Eigenschaft, so dass sie in Bäumen angeordnet werden können. Sie befinden sich in keiner bestimmten Reihenfolge. Jede ParentID-Eigenschaft stimmt nicht unbedingt mit einer ID in der Struktur überein. Daher könnten mehrere Bäume aus diesen Objekten hervorgehen.

Wie würden Sie diese Objekte bearbeiten, um die resultierenden Bäume zu erstellen?  

Ich bin nicht weit von einer Lösung entfernt, aber ich bin mir sicher, dass dies alles andere als optimal ist ...

Ich muss diese Bäume erstellen, um dann Daten in der richtigen Reihenfolge in eine Datenbank einzufügen.

Es gibt keine Zirkelverweise. Ein Knoten ist ein RootNode, wenn ParentID == null ist oder wenn ParentID in den anderen Objekten nicht gefunden wird

algorithmtreelanguage-agnostic
118
Costo

Speichern Sie die IDs der Objekte in einer Hashtabelle, die dem bestimmten Objekt zugeordnet ist. Zählen Sie alle Objekte auf und suchen Sie nach ihrem übergeordneten Objekt, und aktualisieren Sie den übergeordneten Zeiger entsprechend.

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);
}
96
Mehrdad Afshari

Basierend auf der Antwort von Mehrdad Afshari und dem Kommentar von Andrew Hanlon zur Beschleunigung, hier ist mein Take.

Wichtiger Unterschied zur ursprünglichen Aufgabe: Ein Stammknoten hat eine 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;
}
27
Martin Schmidt

Hier ist ein einfacher JavaScript-Algorithmus zum Parsen einer flachen Tabelle in eine übergeordnete/untergeordnete Baumstruktur, die in N-Zeit ausgeführt wird:

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

Python-Lösung

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

Zum Beispiel:

# (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)

Produziert:

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

JS-Version, die einen Stamm oder ein Array von Wurzeln zurückgibt, von denen jeder über eine Children-Eigenschaft mit den zugehörigen untergeordneten Objekten verfügt Hängt nicht von der bestellten Eingabe ab, ist anständig kompakt und verwendet keine Rekursion. Genießen! 

// 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)
5
nu11ptr

Eine fantastische JavaScript-Version finden Sie hier: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/

Angenommen, Sie haben ein Array wie dieses:

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

Und Sie möchten die Objekte so verschachteln:

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

Hier ist eine rekursive Funktion, die es möglich macht.

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

Ich habe eine generische Lösung in C # geschrieben, die auf der Antwort von @Mehrdad Afshari basiert:

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

eine elegante Möglichkeit besteht darin, Elemente in der Liste als Zeichenfolge darzustellen, die eine durch Punkte getrennte Liste der übergeordneten Elemente und schließlich einen Wert enthält:

server.port=90
server.hostname=localhost
client.serverport=90
client.database.port=1234
client.database.Host=localhost

Wenn Sie einen Baum zusammenbauen, erhalten Sie am Ende Folgendes:

server:
  port: 90
  hostname: localhost
client:
  serverport=1234
  database:
    port: 1234
    Host: localhost

Ich habe eine Konfigurationsbibliothek , die diese Überschreibungskonfiguration (Baum) aus Befehlszeilenargumenten (Liste) implementiert. Der Algorithmus zum Hinzufügen eines einzelnen Elements zur Liste zu einem Baum ist hier .

1
Omry Yadan

Vage, wie mir die Frage scheint, würde ich wahrscheinlich eine Karte von der ID bis zum eigentlichen Objekt erstellen. In Pseudo-Java (ich habe nicht geprüft, ob es funktioniert/kompiliert), könnte es etwa so aussehen:

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

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

Und nach jedem Elternteil suchen:

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

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

Wenn Sie getRealObject(ID) wiederverwenden und eine Karte vom Objekt bis zu einer Sammlung von Objekten (oder deren IDs) erstellen, erhalten Sie auch eine übergeordnete> untergeordnete Zuordnung.

1
Henrik Paul

Wenn Sie an einer C # -Version von Eugene interessiert sind, beachten Sie, dass auf node_list als Map zugegriffen wird. Verwenden Sie stattdessen ein Dictionary.

Beachten Sie, dass diese Lösung nur funktioniert, wenn table nach parent_id sortiert ist.

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

Knoten ist wie folgt definiert.

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

Ich kann dies in 4 Zeilen Code und O (n log n) time tun, vorausgesetzt, das Dictionary ist so etwas wie eine 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, und jetzt habe ich gelesen, dass einige parentIDs gefälscht sind.

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.
0
nes1983

Die akzeptierte Antwort erscheint mir viel zu komplex, daher füge ich eine Ruby- und eine NodeJS-Version hinzu

Angenommen, die Liste der flachen Knoten hat die folgende Struktur:

nodes = [
  { id: 7, parent_id: 1 },
  ...
] # Ruby

nodes = [
  { id: 7, parentId: 1 },
  ...
] # nodeJS

Die Funktionen, die die flache Listenstruktur oben in einen Baum verwandeln, sehen folgendermaßen aus

für Ruby:

def to_tree(nodes)

  nodes.each do |node|

    parent = nodes.find { |another| another[:id] == node[:parent_id] }
    next unless parent

    node[:parent] = parent
    parent[:children] ||= []
    parent[:children] << node

  end

  nodes.select { |node| node[:parent].nil? }

end

für NodeJS:

const toTree = (nodes) => {

  nodes.forEach((node) => {

    const parent = nodes.find((another) => another.id == node.parentId)
    if(parent == null) return;

    node.parent = parent;
    parent.children = parent.children || [];
    parent.children = parent.children.concat(node);

  });

  return nodes.filter((node) => node.parent == null)

};
0
Hirurg103

Hier ist die Java-Lösung der Antwort von Mehrdad Afshari.

import Java.util.ArrayList;
import Java.util.HashMap;
import Java.util.Iterator;
import Java.util.List;
import Java.util.Map;

public class Tree {

    Iterator<Node> buildTreeAndGetRoots(List<MyObject> actualObjects) {
        Map<Integer, Node> lookup = new HashMap<>();
        actualObjects.forEach(x -> lookup.put(x.id, new Node(x)));
        //foreach (var item in lookup.Values)
        lookup.values().forEach(item ->
                {
                    Node proposedParent;
                    if (lookup.containsKey(item.associatedObject.parentId)) {
                        proposedParent = lookup.get(item.associatedObject.parentId);
                        item.parent = proposedParent;
                        proposedParent.children.add(item);
                    }
                }
        );
        //return lookup.values.Where(x =>x.Parent ==null);
        return lookup.values().stream().filter(x -> x.parent == null).iterator();
    }

}

class MyObject { // The actual object
    public int parentId;
    public int id;
}

class Node {
    public List<Node> children = new ArrayList<Node>();
    public Node parent;
    public MyObject associatedObject;

    public Node(MyObject associatedObject) {
        this.associatedObject = associatedObject;
    }
}
0
Vimal Bhatt

Bei den meisten Antworten wird davon ausgegangen, dass Sie dies außerhalb der Datenbank tun möchten. Wenn Ihre Bäume relativ statischer Natur sind und Sie die Bäume nur irgendwie in die Datenbank abbilden müssen, sollten Sie die Verwendung geschachtelter Satzdarstellungen auf der Datenbankseite in Betracht ziehen. Schauen Sie sich Bücher von Joe Celko an (oder hier Für eine Übersicht von Celko). 

Wenn Sie sowieso an Oracle dbs gebunden sind, sollten Sie deren CONNECT BY für direkte SQL-Ansätze überprüfen. 

Bei beiden Methoden können Sie die Zuordnung der Bäume vollständig überspringen, bevor Sie die Daten in die Datenbank laden. Nur gedacht, ich würde dies als Alternative anbieten, es könnte für Ihre speziellen Bedürfnisse völlig ungeeignet sein. Die gesamte "richtige Reihenfolge" der ursprünglichen Frage impliziert etwas aus einem Grund, dass Sie die Reihenfolge benötigen, um in der Datenbank "richtig" zu sein? Dies könnte mich dazu bringen, auch dort mit den Bäumen umzugehen.

0
SQLHack

Verwenden Sie nur diese Attribute? Wenn nicht, wäre es nett, ein Array von untergeordneten Knoten zu erstellen, in dem Sie alle diese Objekte einmal durchlaufen und solche Attribute erstellen können. Wählen Sie dort den Knoten mit Kindern, aber ohne Eltern aus, und erstellen Sie iterativ Ihren Baum von oben nach unten.

0
Robert Elwell

hier ist eine Ruby-Implementierung:

Es wird nach Attributnamen oder dem Ergebnis eines Methodenaufrufs katalogisiert.

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 = [#<Student:0x007f891d0b4818 id: 33999, status: "on_hold", tenant_id: 95>,
 #<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b42c8 id: 37220, status: "on_hold", tenant_id: 6>,
 #<Student:0x007f891d0b4020 id: 3444, status: "ready_for_match", tenant_id: 15>,
 #<Student:0x007f8931d5ab58 id: 25166, status: "in_partnership", tenant_id: 10>]

catalog students, by: [:tenant_id, :status]

# this would out put the following
{"root"=>
  {95=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4818
        id: 33999,
        status: "on_hold",
        tenant_id: 95>]},
   6=>
    {"on_hold"=>
      [#<Student:0x007f891d0b4570 id: 7635, status: "on_hold", tenant_id: 6>,
       #<Student:0x007f891d0b42c8
        id: 37220,
        status: "on_hold",
        tenant_id: 6>]},
   15=>
    {"ready_for_match"=>
      [#<Student:0x007f891d0b4020
        id: 3444,
        status: "ready_for_match",
        tenant_id: 15>]},
   10=>
    {"in_partnership"=>
      [#<Student:0x007f8931d5ab58
        id: 25166,
        status: "in_partnership",
        tenant_id: 10>]}}}
0
joegiralt

Es ist nicht genau dasselbe, wonach der Fragesteller gesucht hat, aber ich hatte Mühe, die mehrdeutigen, hier formulierten Antworten mit meinem Kopf zu umwickeln, und ich denke immer noch, dass diese Antwort unter den Titel passt.

Meine Antwort bezieht sich auf die Zuordnung einer flachen Struktur zu einer direkt auf dem Objektbaum befindlichen Struktur, in der Sie lediglich einen ParentID für jedes Objekt haben. ParentID ist null oder 0, wenn es sich um ein Stammverzeichnis handelt. Gegenüber dem Fragesteller gehe ich davon aus, dass alle gültigen ParentID auf etwas anderes in der Liste verweisen:

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;
0
Aske B.