algorithm - 添加 TreeView 分支的最有效算法

Question

我必须将分支(节点)添加到 TreeView 中。我正在努力确定最低 O(n) 技术是什么。

我的数据呈现如下:

Id  ParentId    Value

0   null        Bob
1   0           Amy
2   1           Susan
3   1           Matt
4   2           Keith
5   4           Craig
6   4           Derrick

所以这棵树看起来像:

我所能想出的只是一个 n^2 算法，该算法对每个条目扫描每个其他条目以查看它们是否属于子节点。 我还从数组中删除条目以在添加时进行扫描。因此，如果有内存(可能不会)，它会比 n^2 少一点。

有没有更好的技术？

Answer 1

假设您的语言有某种列表/向量/可调整大小的数组类型，这很容易。

为每个 ID 创建一个空列表。遍历每一行，如果 ParentId 不为空，则将 Id 添加到 ParentId 的列表中。

您现在在 O(n) 时间内拥有每个条目的 child 。