Преобразовать список в дерево

Question

У меня есть API, возвращающий список категорий, который действительно должен быть деревом. Каждый элемент в списке выглядит так:

struct ListCategory {
    let name: String
    let id: Int
    let parent: Int?
}

, и мне нужно, чтобы он был в дереве, что-то вроде этого:

struct TreeCategory {
    let name: String
    let id: Int
    let children: [TreeCategory]
}

Список не отсортирован, и, что более неприятно, не сортируется - то есть более низкий идентификатор категории не означает, что она будет выше в дереве (дерево было отредактировано после его создания).

Какой хороший алгоритм для этого? Я ожидаю, что список будет содержать около 50 элементов, поэтому ясность кода по крайней мере так же важна, как и производительность для меня.

У меня есть идея, но это похоже на проблему, для которой есть умное решение. :)

Опции, которые я рассмотрел:

• Изменить API. В идеале, конечно, но я не могу этого сделать.
• Просто используйте библиотеку. Это вариант, но мне кажется, что из-за одной операции во всем моем приложении это излишне.

Answer 1

Вот альтернативный API для этого, код для простоты прокомментирован. Структура Node имеет прямую ссылку на своего родителя вместо parentId. Это делает код более надежным, поскольку для id есть только один источник правды.

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

Я предоставил пример API для напрямую получите parentId правильным способом.

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

Есть два подхода Swift, которые мне действительно нравятся в этом:

• Использование KeyPath во время групповой обработки, что делает код ясным и кратким
• Рекурсивная функция, которая хорошо подходит для древовидных структур и самоочевидный

Вот код, который вы можете проверить и исследовать на игровой площадке Xcode:

// Your old struct
struct ListCategory {
    let name: String
    let id: Int
    let parentId: Int?
}

extension ListCategory {
    // Helper function to convert to new structure
    func toNode(parent: Node? = nil, children: [Node] = []) -> Node {
        Node(name: name, id: id, parent: parent, children: children)
    }
}

// New struct to store a category
class Node {
    var name: String
    var id: Int
    var children: [Node] = []  // You can make this [Node?]
    // if you are planning to remove nodes at some points

    // Weak var to avoid retain cycles
    weak var parent: Node?

    init(name: String, id: Int, parent: Node? = nil, children: [Node] = []) {
        self.name = name
        self.id = id
        self.parent = parent
        self.children = children
    }
}

// Exemple of API you can build
extension Node {
  var parentId: Int? { parent?.id }
}

class Tree {
    var root: Node?

    init(categories: [ListCategory]) {
        // Group categories by parent id
        let categoriesByParentId = Dictionary(grouping: categories, by: \.parentId)

        // Convert Categories to Nodes
        let nodesByParentId = categoriesByParentId.mapValues { categories in
            categories.map { $0.toNode() }
        }

        // Check if only 1 root node
        guard let rootNode = nodesByParentId[nil], rootNode.count == 1 else {
            // Handle error here...
            fatalError()
        }

        // Create and assign the root node
        root = rootNode.first

        // Recursive function to build the tree
        func buildTree(node: Node?) {
            // For the current node find its children
            // If no children its a leaf node (bottom of the tree), just return
            guard let children = nodesByParentId[node?.id] else { return }

            // Else, link the parent to their children
            node?.children = children

            // for each child
            for child in children {
                // Link the child to its parent
                child.parent = node

                // Continue building the tree from this node
                buildTree(node: child)
            }
        }

        // Start to build from the root node
        buildTree(node: root)
    }
}

// Main
let categories = [
    ListCategory(name: "hello", id: 0, parentId: nil),
    ListCategory(name: "world", id: 1, parentId: 0),
    ListCategory(name: "toto", id: 2, parentId: 0),
    ListCategory(name: "bob", id: 3, parentId: 1),
]

let tree = Tree(categories: categories)

Answer 2

Для этого алгоритма вам понадобятся ссылочные типы, поэтому сделайте ваш результирующий тип данных Node классом:

class Node {
    let name: String
    let id: Int
    let parentId: Int?

    var children: [Node] = []

    init(name: String, id: Int, parentId: Int?) {
        self.name = name
        self.id = id
        self.parentId = parentId
    }
}

Теперь при построении дерева мы создадим словарь, в котором все дети сгруппированы в соответствии с parentId. Если parentId равен nil, у нас есть узел root, поэтому давайте просто используем значение -1 в качестве ключа для root, чтобы мы могли сохранить его в словаре. Как только наш словарь создан, нам просто нужно связать каждый родительский узел с его дочерними элементами.

struct Tree {

    var root: Node?

    init(nodes: [Node]) {
        let groups = Dictionary(grouping: nodes) { node -> Int in
            return node.parentId ?? -1
        }
        groups.forEach { pair in
            guard pair.key != -1 else { return }
            let parent = nodes.first { $0.id == pair.key }
            parent?.children = pair.value
        }
        root = groups[-1]?.first
    }
}

Использование довольно простое:

let nodes = [
    Node(name: "a", id: 0, parentId: nil),
    Node(name: "b", id: 1, parentId: 0),
    Node(name: "c", id: 2, parentId: 0),
    Node(name: "d", id: 3, parentId: 1),
    Node(name: "e", id: 4, parentId: 1),
    Node(name: "f", id: 5, parentId: 2),
    Node(name: "g", id: 6, parentId: 2),
]

let tree = Tree(nodes: nodes)