Как эффективно построить дерево из плоской конструкции?

Question

У меня есть куча объектов в плоской структуре. Эти объекты имеют свойства ID и ParentID, поэтому их можно размещать в деревьях. Они не в определенном порядке. Каждое свойство ParentID не обязательно совпадает с ID в структуре. Поэтому их может быть несколько деревьев, выходящих из этих объектов.

Как бы вы обработали эти объекты для создания результирующих деревьев?

Я не так далек от решения, но уверен, что оно далеко от оптимального ...

Мне нужно создать эти деревья, чтобы затем вставить данные в базу данных в правильном порядке.

Нет циркулярных ссылок. Узел является RootNode, когда ParentID == null или когда ParentID не может быть найден в других объектах

Answer 1

Принятый ответ выглядит слишком сложным для меня, поэтому я добавляю его версии для Ruby и NodeJS

Предположим, что список плоских узлов имеет следующую структуру:

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

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

Функции, которые превратят структуру плоского списка выше в дерево, выглядят следующим образом

для 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

для 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)

};

Answer 2

вот реализация ruby:

Он будет каталогизирован по имени атрибута или результату вызова метода.

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

Answer 3

Это не совсем то, что искал аскер, но мне было трудно обернуть голову вокруг неоднозначно сформулированных ответов, представленных здесь, и я все еще думаю, что этот ответ подходит под заголовком.

Мой ответ - для отображения плоской структуры в дереве непосредственно на объекте, где у вас есть ParentID для каждого объекта. ParentID - это null или 0, если это корень. Напротив спрашивающего, я предполагаю, что все действительные 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;

Answer 4

В большинстве ответов предполагается, что вы хотите сделать это вне базы данных. Если ваши деревья относительно статичны по своей природе и вам просто нужно каким-то образом отобразить деревья в базу данных, вы можете рассмотреть возможность использования представлений вложенных множеств на стороне базы данных. Посмотрите книги Джо Селко (или здесь для обзора Celko).

Если в любом случае вы привязаны к базе данных Oracle, проверьте их CONNECT BY для прямого подхода SQL.

При любом подходе вы можете полностью пропустить отображение деревьев, прежде чем загружать данные в базу данных. Просто подумал, что я предложу это в качестве альтернативы, это может быть совершенно не подходит для ваших конкретных потребностей. Вся часть «правильного порядка» исходного вопроса в некоторой степени подразумевает, что вам нужен порядок, чтобы быть «правильным» в БД по какой-то причине? Это может подтолкнуть меня и к тому, чтобы я там работал с деревьями.

Answer 5

Я могу сделать это за 4 строки кода и за O (n log n), предполагая, что Dictionary - это что-то вроде 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 : Хорошо, и теперь я прочитал, что некоторые parentIDs являются поддельными, так что забудьте об этом и сделайте следующее:

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 6

Вы застряли, используя только эти атрибуты? Если нет, то было бы неплохо создать массив дочерних узлов, где вы можете циклически пройтись по всем этим объектам один раз для создания таких атрибутов. Оттуда выберите узел с дочерними элементами, но без родителей, и итеративно постройте свое дерево сверху вниз.