#algorithm #design-patterns #tree
#алгоритм #шаблоны проектирования #дерево
Вопрос:
У меня есть динамическое дерево — узлы могут быть добавлены / удалены в любое время. Каждый узел:
- может иметь N дочерних элементов;
- имеет массив
foo; - может добавлять / удалять
fooв / из своего собственногоfooмассива.
И мне всегда нужно знать, сколько всего foo в дереве. Существует ли какой-либо шаблон или алгоритм для такой проблемы, принимая во внимание, что всегда существует только один поток (без многопоточности)?
Комментарии:
1. Если вы можете сохранить это значение в большой переменной области видимости (область файла, глобальная область …), это можно было бы сделать за постоянное время. Поскольку многопоточности нет, это кажется разумным решением.
2. Сохраняйте запись числа и обновляйте значение при каждом удалении / вставке / изменении.
Ответ №1:
Дерево ссылок / разрезов может обеспечивать операции времени O (log n) независимо от глубины дерева. Однако известные мне реализации плохо распараллеливаются.