我想问一下是否有人知道在插入新节点期间存储从根节点到多路树的新节点的路径的高效方法。例如，如果我有以下树：
对于每个节点，我目前在插入过程中存储一个从根节点到节点的路径数组，方法是通过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]
...
如果我现在从深度 3 的叶节点插入一个新节点1，我将必须为其创建一个新的路径数组，以存储父节点的所有节点1（即[1, 1, 3, 1]）加上新的子 ID，该 ID1用于第一个子节点：
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.
这种查找操作会很快，问题是随着树的深入而创建路径数组。
任何建议，将不胜感激。
感谢您的关注。