时间戳

首页 > 解决方案 > 从 n 叉树中有效地删除节点列表

c++ - 从 n 叉树中有效地删除节点列表

问题描述

我有游戏对象的 n 叉树。用户随机选择树中的一些对象并想要删除。问题是某些对象是另一个对象的子对象。事实证明，每次删除层次结构中的节点后，我都必须遍历所有选定的节点并将其删除。该算法是否比 O (n^2) 更快？

更新：为了更清楚我需要什么，我编写了伪代码：

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);
}

标签： c++algorithmtree

解决方案

为了搜索该节点，它将花费您 O(n^d)，其中 d 是树的深度。因此，如果 d < 2 会更快，我认为对于大型游戏树来说几乎不会出现这种情况。你确定 n 中的 n 和 O(n^2) 是同一个符号吗？

推荐阅读