0

我正在做一些个人研究，发现需要有效地修改（可能非常大）数据树中的数据。数据由简单数据组成，只是一个整数或可能是一个小对象。在解析树时，我需要修改所有类似的对象（但仅限于子树中的对象）。这有点难以解释，所以我添加了一个图像作为示例来提供帮助。

例子

在上图中，字母代表数据的值（相同的字母代表相同的数据），括号中的数字是唯一值，因此我可以参考它们。

所以假设我正在解析树，我目前在节点 2。我已经确定我需要修改 'a' 的值并将其更改为 'g'，但我只想修改当前节点和所有子节点. （所以 2 和 9 将变为“g”，而 1 和 7 仍为“a”）。我可以递归搜索所有孩子并手动更改它，但树可能非常大。如果我想更改 a 的所有值，我可以简单地将数据存储为双指针，然后更改指针指向的值。所以我的问题是，是否有任何已知的方法可以在可能恒定的时间内以我想要的方式修改数据？

4

1 回答 1

0

我会这样做的方式是插入树。

为节点创建一个类

class node
{
    node* dataParent;
    CustomType* value;
    // put regular tree pointers here
}

然后，当您在遍历时插入时， dataParent 指向具有相同数据的最后一个父级。如果没有相同的父母，它将为空，并且值不会为空。如果它有一个相同的父级，则 value 将为 null 并且某些内容将在 Custom parent 中。但是，您的检索不会是恒定的时间，您必须遍历直到值不为空。

这是我能想到的最好的方法。它至少是日志 ni 认为。有一阵子了。

一件事是插入将是昂贵的。

于 2012-09-27T03:24:48.910 回答