평평한 구조에서 효율적으로 나무를 만드는 법?

평평한 구조에서 효율적으로 나무를 만드는 법?

---

평평한 구조에 많은 물체가 있습니다. 이 객체에는 ID및 ParentID속성이 있으므로 트리로 정렬 할 수 있습니다. 그것들은 특별한 순서가 아닙니다. 각 ParentID속성이 ID구조에서 반드시 일치하는 것은 아닙니다 . 그러므로 그것들은이 물체들에서 나오는 여러 나무 일 수 있습니다.

결과 트리를 만들기 위해 이러한 객체를 어떻게 처리 하시겠습니까?

나는 해결책에서 멀지 않지만 최적의 것이 아니라고 확신합니다 ...

이 트리를 만든 다음 데이터베이스에 데이터를 올바른 순서로 삽입해야합니다.

순환 참조가 없습니다. NodeID == null이거나 다른 개체에서 ParentID를 찾을 수없는 경우 노드는 RootNode입니다.

---

특정 객체에 매핑되는 해시 테이블에 객체의 ID를 저장합니다. 모든 객체를 열거하고 존재하는 경우 부모를 찾고 그에 따라 부모 포인터를 업데이트하십시오.

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

---

Mehrdad Afshari의 답변과 Andrew Hanlon의 속도 향상에 대한 의견을 바탕으로 여기에 제 의견이 있습니다.

원래 작업과의 중요한 차이점 : 루트 노드에는 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;
}

---

다음은 플랫 테이블을 N 시간에 실행되는 부모 / 자식 트리 구조로 구문 분석하는 간단한 JavaScript 알고리즘입니다.

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

---

파이썬 솔루션

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

예를 들면 다음과 같습니다.

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

생산 :

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

---

하나의 루트 또는 루트의 배열을 리턴하는 JS 버전은 각각 관련 하위를 포함하는 하위 배열 특성을 갖습니다. 순서가 지정된 입력에 의존하지 않고 적당히 간결하며 재귀를 사용하지 않습니다. 즐겨!

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

---

http://oskarhane.com/create-a-nested-array-recursively-in-javascript/ 에서 멋진 JavaScript 버전을 찾았습니다.

다음과 같은 배열이 있다고 가정 해 봅시다.

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 = [
    {
        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}
        ]
    }
];

여기에 재귀 함수가 있습니다.

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

사용법 :

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

---

@ Mehrdad Afshari 답변을 기반으로 C #에서 일반적인 솔루션을 느슨하게 작성했습니다.

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

---

Eugene 솔루션의 C # 버전에 관심이있는 사람은 node_list 가 맵으로 액세스되므로 Dictionary를 대신 사용하십시오.

이 솔루션 은 테이블 이 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]);
}

노드는 다음과 같이 정의됩니다.

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

---

다음은 Mehrdad Afshari의 답변에 대한 Java 솔루션입니다.

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

---

질문이 나에게 보이지 않는 것처럼, 아마도 ID에서 실제 객체로의 맵을 만들 것입니다. pseudo-java에서 (작동 / 컴파일 여부를 확인하지 않았습니다) 다음과 같습니다.

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

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

그리고 각 부모를 찾아보십시오.

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

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

getRealObject(ID)오브젝트에서 오브젝트 콜렉션 (또는 해당 ID)으로의 맵을 재사용 하고 수행하면 부모-> 자식 맵도 얻을 수 있습니다.

---

Dictionary가 TreeMap과 같다고 가정하면 4 줄의 코드와 O (n log n) 시간 으로이 작업을 수행 할 수 있습니다.

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.

편집 : 좋아, 이제 일부 parentID가 가짜임을 읽었으므로 위의 내용을 잊어 버리고 이렇게하십시오.

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.

---

대부분의 답변은 데이터베이스 외부 에서이 작업을 수행한다고 가정합니다. 트리가 본질적으로 정적이며 트리를 데이터베이스에 매핑 해야하는 경우 데이터베이스 측에서 중첩 집합 표현을 사용하는 것이 좋습니다. (또는 조 셀코으로 책을 확인 여기 Celko하여 개요).

어쨌든 Oracle db에 묶여 있다면, CONNECT BY에서 SQL 접근 방법을 확인하십시오.

어느 방법을 사용하든 데이터베이스에 데이터를로드하기 전에 트리 매핑을 완전히 건너 뛸 수 있습니다. 내가 이것을 대안으로 제공하겠다고 생각한 것은 귀하의 특정 요구에 완전히 부적합 할 수 있습니다. 원래 질문의 전체 "적절한 순서"부분은 어떤 이유로 db에서 "정확한"순서가 필요하다는 것을 암시합니까? 이것은 나무를 다루는쪽으로 나를 밀어 넣을 수도 있습니다.

---

그것은 asker가 찾은 것과 정확히 같지는 않지만 여기에 제공된 모호한 문구로 머리를 감싸는 데 어려움을 겪었지만 여전히이 답변이 제목 아래에 적합하다고 생각합니다.

내 대답은 평평한 구조를 모든 객체에있는 모든 객체 트리에 직접 트리에 매핑하는 것입니다 ParentID. ParentID이다 null또는 0그것은 루트의 경우. asker와는 반대로, 나는 유효한 모든 ParentID것이 목록의 다른 것을 가리킨다 고 가정 합니다.

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;

---

다음은 루비 구현입니다.

속성 이름 또는 메소드 호출 결과별로 카탈로그 화합니다.

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

---

허용 된 답변이 너무 복잡해 보이므로 Ruby 및 NodeJS 버전을 추가하고 있습니다.

플랫 노드 목록의 구조는 다음과 같습니다.

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

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

위의 단순 목록 구조를 트리로 변환하는 기능은 다음과 같습니다.

루비의 경우 :

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

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)

};

---

이를 수행하는 한 가지 우아한 방법은 목록의 항목을 점으로 구분 된 부모 목록을 보유하는 문자열로 표시하고 마지막으로 값을 표시하는 것입니다.

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

나무를 조립할 때 다음과 같은 결과가 나타납니다.

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

명령 줄 인수 (목록) 에서이 재정의 구성 (트리)을 구현 하는 구성 라이브러리 가 있습니다. 목록에 단일 항목을 트리에 추가하는 알고리즘 은 다음과 같습니다 .

---

이러한 속성 만 사용하고 있습니까? 그렇지 않은 경우 이러한 모든 객체를 한 번 순환하여 해당 속성을 빌드 할 수있는 하위 노드 배열을 작성하는 것이 좋습니다. 여기에서 자식은 있지만 부모는없는 노드를 선택하고 위에서 아래로 반복적으로 나무를 만듭니다.

참고 URL : https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure