algorithm - que - organizaciones verticales
¿Cómo construir eficientemente un árbol desde una estructura plana? (13)
Tengo un montón de objetos en una estructura plana. Estos objetos tienen una ID y una propiedad ParentID para que puedan organizarse en árboles. No están en ningún orden particular. Cada propiedad ParentID no necesariamente coincide con una ID en la estructura. Por lo tanto, podrían ser varios árboles que emergen de estos objetos.
¿Cómo procesarías estos objetos para crear los árboles resultantes?
No estoy tan lejos de una solución, pero estoy seguro de que está lejos de ser óptima ...
Necesito crear estos árboles para luego insertar datos en una base de datos, en el orden correcto.
No hay referencias circulares Un nodo es un RootNode cuando ParentID == null o cuando ParentID no se puede encontrar en los otros objetos
¿Estás atrapado usando solo esos atributos? De lo contrario, sería bueno crear una matriz de nodos secundarios, donde pueda recorrer todos estos objetos una vez para crear dichos atributos. A partir de ahí, seleccione el nodo con hijos pero sin padres e iterativamente construya su árbol de arriba hacia abajo.
Almacene identificaciones de los objetos en una asignación de tabla hash al objeto específico. Enumere a través de todos los objetos y encuentre su padre si existe y actualice su puntero principal en consecuencia.
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);
}
Aquí hay un algoritmo de JavaScript simple para analizar una tabla plana en una estructura de árbol padre / hijo que se ejecuta en tiempo 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);
Basado en la respuesta de Mehrdad Afshari y el comentario de Andrew Hanlon para una aceleración, aquí está mi opinión.
Diferencia importante para la tarea original: un nodo raíz tiene 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;
}
Encontré una impresionante versión de JavaScript aquí: http://oskarhane.com/create-a-nested-array-recursively-in-javascript/
Digamos que tienes una matriz como esta:
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}
];
Y desea tener los objetos anidados así:
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}
]
}
];
Aquí hay una función recursiva que lo hace posible.
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);
Escribí una solución genérica en C # libremente basada en la respuesta de @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;
}
}
La mayoría de las respuestas asumen que está buscando hacer esto fuera de la base de datos. Si sus árboles son de naturaleza relativamente estática y solo necesita mapear de algún modo los árboles en la base de datos, es posible que desee considerar el uso de representaciones de conjuntos anidados en el lado de la base de datos. Echa un vistazo a los libros de Joe Celko (o here para una descripción general de Celko).
Si está ligado a Oracle dbs de todos modos, revisa su CONNECT BY para ver los métodos directos de SQL.
Con cualquiera de los enfoques, podría omitir completamente la asignación de los árboles antes de cargar los datos en la base de datos. Solo pensé en ofrecer esto como una alternativa, puede ser completamente inapropiado para sus necesidades específicas. Toda la parte del "orden correcto" de la pregunta original implica algo que usted necesita que la orden sea "correcta" en el DB por alguna razón. Esto también podría empujarme a manejar los árboles allí.
No es exactamente lo mismo que lo que buscó el solicitante, pero tuve dificultades para entender las respuestas formuladas ambiguamente aquí, y todavía creo que esta respuesta se ajusta al título.
Mi respuesta es para mapear una estructura plana a un árbol directamente sobre el objeto, donde todo lo que tienes es un ParentID en cada objeto. ParentID es null o 0 si es una raíz. Enfrente del asker, supongo que todos los ParentID válidos de ParentID apuntan a algo más en la lista:
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;
Para cualquier persona interesada en una versión de C # de la solución de Eugene, tenga en cuenta que se accede a node_list como un mapa, por lo tanto, utilice un diccionario en su lugar.
Tenga en cuenta que esta solución solo funciona si la tabla está ordenada por 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]);
}
El nodo se define de la siguiente manera.
class Node
{
public int id { get; set; }
public int parent_id { get; set; }
public List<Node> children = new List<Node>();
}
Puedo hacer esto en 4 líneas de código y tiempo O (n log n), suponiendo que Dictionary es algo así como 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.
EDITAR : Ok, y ahora leo que algunos parentIDs son falsos, así que olvídate de lo anterior, y haz esto:
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.
Solución de Python
def subtree(node, relationships):
return {
v: subtree(v, relationships)
for v in [x[0] for x in relationships if x[1] == node]
}
Por ejemplo:
# (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)
Produce:
{
"1": {
"4": {
"10": {},
"11": {
"16": {},
"17": {
"24": {},
"25": {}
}
}
},
"5": {
"8": {},
"9": {
"20": {},
"12": {
"22": {},
"23": {
"2": {},
"27": {},
"26": {}
}
},
"21": {},
"7": {}
}
}
}
}
Vago como me parece la pregunta, probablemente crearía un mapa desde el ID hasta el objeto real. En pseudo-java (no revisé si funciona / compila), podría ser algo así como:
Map<ID, FlatObject> flatObjectMap = new HashMap<ID, FlatObject>();
for (FlatObject object: flatStructure) {
flatObjectMap.put(object.ID, object);
}
Y para buscar a cada padre:
private FlatObject getParent(FlatObject object) {
getRealObject(object.ParentID);
}
private FlatObject getRealObject(ID objectID) {
flatObjectMap.get(objectID);
}
Al reutilizar getRealObject(ID) y al hacer un mapa de un objeto a una colección de objetos (o sus ID), también obtiene un mapa principal-> secundario.
Versión de JS que devuelve una raíz o una matriz de raíces, cada una de las cuales tendrá una propiedad de matriz Children que contiene los elementos secundarios relacionados. No depende de la entrada ordenada, decentemente compacta, y no usa recursividad. ¡Disfrutar!
// 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)