performance - 有效地找到树节点的深度标记子节点

Question

给定一个(m-way)树 T:

        A
       / \
      B   C
     / \   \
    D*  E*  F
   / \   \   \
  G   H*  I   J*

对于标记的节点 D*、E* H* 和 J*，除了遍历所有子树或存储所有标记的 child 之外，是否有一种快速的方法来检索给定节点下的所有标记的子节点对于每个节点？即:

B -> D*, E*, H*
C -> J*
A -> D*, E*, H*, J*

Answer 1

原则上，您需要在遍历树和存储标记值列表之间进行权衡。您提到了两个极端，我将在下面给您举一个介于这两个极端之间的示例。

我想到的一个想法是在每个标记节点处存储下一个标记子节点的“层”，这应该在存储和时间之间提供相当平衡的组合，因此在您的示例中它不会节省太多，但是例如如果你有

        A
       / \
      B*  C
     / \   \
    D*  E   F
   / \   \   \
  G   H*  I*  J*
 /   / \
K   L   M

您可以将 D,I 存储在 B 中，将 H 存储在 D 中，并将“空”标记存储在 H,I,J.

要获取一个节点的列表，您只需要遍历直到每个分支都碰到一个标记的节点，例如，要获取 A 的列表，您必须从 遍历A->B 和 A->C->F->J，然后 B 会给你 I,D， D 会给你 H。

您也可以将其视为仅将标记节点的树与原始树一起存储，在本例中为两棵树

  B        J
 / \
D   I
|
H

根据标记节点的分布，您可以针对您的应用程序优化此想法。