Есть ли шаблон / алгоритм, чтобы узнать номер какого-либо свойства в динамическом дереве?

Question

У меня динамическое дерево - узлы можно добавлять / удалять в любое время.Каждый узел:

• может иметь N дочерних элементов;
• имеет массив foo;
• может добавлять / удалять foo в / из своего собственного foo массив.

И мне всегда нужно знать, сколько всего foo в дереве.Существует ли какой-либо шаблон или алгоритм для такой задачи, учитывая, что всегда есть только один поток (без многопоточности)?

Answer 1

Дерево ссылок / вырезок может обеспечить O (log n) операций времени независимо от глубины дерева. Хотя реализации, о которых я знаю, плохо распараллеливаются.