从列表构造树（非二进制，不平衡）的时间复杂度最低？

Question

假设我有一个 list/array 比如：

[
    { id: 1, parent: null },
    { id: 2, parent: 1 },
    { id: 4, parent: 2 },
    { id: 5, parent: 3 },
    { id: 6, parent: 2 },
    { id: 3, parent: 4 }
]

我想将它转换成这样的树：

{ 
    id: null,
    children: [
        { 
            id: 1,
            children: [
                { 
                    id: 2,
                    children: [
                        { 
                            id: 4,
                            children: [
                                {
                                    id: 3,
                                    children: [
                                        {
                                            id: 5,
                                            children: []
                                        }
                                    ]
                                }
                            ]
                        },
                        {
                            id: 6,
                            children: [
                                
                            ]
                        }
                    ]
                }
            ]
        }
    ]
}

我可以使用以下（伪代码）函数轻松完成此操作：

function GetChildren(rootNode, inputList) {
    for (item in inputList) {
        if (item.parent == rootNode.id) {
            childNode = {
                id: item.id,
                children: []
            }
            GetChildren(childNode, inputList)
            rootNode.children.append(childNode)
        }
    }
}

我相信这会运行时间复杂度为 O(n²)。有没有一种算法可以更快地做到这一点？我已经看到一些类似的 BST 问题，但这不是 BST。

注意以下几点：

一个节点可以无限children
树可以无限深
列表中的项目可以任意顺序出现（child 可能出现在 parent 之前）

我曾想过只传递列表中没有 parent 的部分，因此当您重复出现时，您会遍历一个逐渐变小的列表。我不知道这是否真的会节省时间：

function GetChildren(rootNode, inputList) {
    for (item in inputList) {
        listWithoutParent = inputList.remove(rootNode) // O(?)
        if (item.parent == rootNode.id) {
            childNode = {
                id: item.id,
                children: []
            }
            GetChildren(childNode, listWithoutParent)
            rootNode.children.append(childNode)
        }
    }
}

Answer 1

我们的想法是维护一个散列 table，以 id 为键，其中的值是要创建的树的对象。因此，例如，在该散列 table 中，您将拥有如下条目：

key: 1
value: { id: 1, children: [] }

在迭代输入数据时，查找当前 ID 和当前父级的值。如果其中任何一个尚未出现在散列 table 中，请立即将其插入。这为您提供了两个具有 id 和 children 属性的对象。然后将子节点对象附加到父对象的children数组中。

这是在 JavaScript 中的工作方式，其中对于哈希 table 我使用原生 Map:

function getOrCreateNode(map, id) {
    let node = map.get(id);
    if (node == undefined) { // Node not yet created
        node = { id, children: [] }; // Create a new node
        map.set(id, node); // Add that new node to the map by its id
    }
    return node;
}

function createTree(data) {
    let map = new Map; // Keys are id, values are nodes of the tree 
    for (let item of data) { // Iterate all objects in the input array
        // Get parent and child object, and add child object to parent's children array:
        getOrCreateNode(map, item.parent).children.push(getOrCreateNode(map, item.id));
    }
    return map.get(null); // Return the root node
}

// Sample input data:
let data = [
    { id: 1, parent: null },
    { id: 2, parent: 1 },
    { id: 4, parent: 2 },
    { id: 5, parent: 3 },
    { id: 6, parent: 2 },
    { id: 3, parent: 4 }
];

// Output the result
console.log(createTree(data));

由于哈希 tables 通常提供具有 average amortised constant time complexity 的插入和查找实现，此算法将运行具有线性时间复杂度（根据条目数在输入数组中）。

我们应该添加免责声明，即对哈希 table 的插入和查找操作具有理论上的最差时间复杂度，与其大小成线性关系。有时您可能对 id 值了解更多，这样您就可以使用完美的哈希算法。例如， id 值都可以是小的无符号整数（如您的示例）。在这种情况下，您可以使用数组作为散列 table，并将 id 值用作数组索引。那么插入或查找操作的最坏情况时间复杂度仍然是 O(1).

从列表构造树（非二进制，不平衡）的时间复杂度最低？

Lowest time complexity to construct tree (nonbinary, unbalanced) from a list?

algorithm

tree

big-o