Эффективно удалить список узлов из n-арного дерева

Question

У меня есть n-арное дерево игровых объектов.Пользователь случайным образом выбирает некоторые объекты в дереве и хочет удалить.Проблема в том, что некоторые объекты являются детьми другого.Оказывается, после каждого удаления узла внутри иерархии я должен перебирать все выбранные узлы и удалять его.Алгоритм быстрее, чем O (n ^ 2)?

Upd: чтобы было понятнее, что мне нужно, я написал псевдокод:

struct TreeNode
{
    vector<TreeNode*> childs;
};

void removeNodeHierarchy(list<TreeNode*>& nodes, TreeNode *n)
{
    for(TreeNode *child : n->childs())
        removeNodeHierarchy(nodes, child);

    nodes.remove(n); // complexity nodes.size()
    delete n;
}

// The function I'm trying to write 
// Problem: Total complexity = nodes.size() * nodes.size()
void removeNodes(list<TreeNode*>& nodes, TreeNode *root)
{
    while (!nodes.empty()) // complexity nodes.size()
    {
        TreeNode *n = nodes.first();
        removeNodeHierarchy(nodes, n);
    }
}

void main()
{
    TreeNode *tree = ...
    list<TreeNode*> nodes = ...

    removeNodes(nodes, tree);
}

Answer 1

Чтобы найти этот узел, вам понадобится O (n ^ d), где d - глубина дерева. Так что будет быстрее, если d <2, что, я думаю, почти никогда не будет иметь место для дерева больших игр. Вы уверены, что n из n-ary и O (n ^ 2) - это один и тот же символ? </p>