algorithm - 是否有任何模式/算法可以知道动态树中某些属性的数量？

Question

我有一个动态树 - 可以随时添加/删除节点。每个节点：

• 可以有N个孩子；
• 有数组foo；
• 可以添加/删除foo到/从他自己的foo阵列。

而且我总是需要知道树中有多少个总数foo。考虑到始终只有一个线程（没有多线程），是否有针对此类问题的任何模式或算法？

标签： algorithmdesign-patternstree

Answer 1

无论树的深度如何，链接/切割树都可以提供 O(log n) 时间操作。我知道的实现虽然不能很好地并行化。