在插入过程中逐步存储从根节点到多路树的节点的路径，因此存储操作不会具有O（n）的复杂度

Question

我想问一问，在插入新节点期间，是否有人知道一种存储从根节点到多路树的新节点的路径的有效方法。例如，如果我有以下树：

对于每个节点，我目前通过以下方式存储从根节点到根节点的路径的数组，方法是通过int为每个深度相同的子代分配一个唯一的ID：

Root node -> [1]

Depth 1, child 1 of root -> [1, 1]
Depth 1, child 2 of root -> [1, 2]

Depth 2, child 1 of parent 1 -> [1, 1, 1]
Depth 2, child 2 of parent 1 -> [1, 1, 2]
Depth 2, child 3 of parent 1 -> [1, 1, 3]
Depth 2, child 1 of parent 2 -> [1, 2, 4]
Depth 2, child 2 of parent 2 -> [1, 2, 5]

Depth 3, child 1 of parent 3 -> [1, 1, 3, 1]

...

如果现在从1深度3 的叶节点插入一个新节点，则必须为其创建一个新的路径数组，以存储父节点1（即[1, 1, 3, 1]）的所有节点以及1用于第一个孩子的新子ID ：

Depth 4, child 1 of parent 1 -> [1, 1, 3, 1, 1]

当我的树长得很高时（每个深度的孩子数相对较少，但深度可能很高），该算法的较慢部分将是数组重新创建过程。试想一棵深度树1.000.000，如果我从深度节点插入一个新节点，则1.000.000必须为此新节点创建一个新数组，其中存储1.000.001父节点的所有ID并附加新节点的ID：

Depth 1.000.001, child 1 of parent x -> [...1 million and one IDs... , 1]

在插入节点期间，是否有更有效的方式将路径存储在每个节点上？

我基本上需要这样做来确定是否有任何给定的节点是树中可能的父节点的子节点，并且由于我在每个节点中都有存储的路径，因此可以通过检查子节点的路径数组轻松地做到这一点，如下所示：

// Ex. 1
Is node 4 of depth 2 the parent/ancestor of node 1 of depth 3?

node 1 of depth 3 has the following path array: pathArray = [1, 1, 3, 1]
Its ancestor ID on depth 2 is: pathArray[2] -> 3

3 != 4 and therefore I know that node 4 of depth 2
is not a parent of node 1 of depth 3.

// Ex. 2
Is node 1 of depth 1 the parent/ancestor of node 1 of depth 3?

node 1 of depth 3 has the following path array: pathArray = [1, 1, 3, 1]
Its ancestor ID on depth 1 is: pathArray[1] -> 1

1 == 1 and therefore I know that node 1 of depth 1
is a parent of node 1 of depth 3.

这种查找操作会很快，问题在于随着树的深入，将创建路径数组。

任何建议，将不胜感激。

谢谢您的关注。

Answer 1

数组将所有值连续存储在内存中。如果您想保留此属性，则必须使用它们。或者，如果您愿意希望通过多个内存位置，则可以在每个节点中仅存储其直接父节点，并跟踪到所需的级别以执行所需的检查。