我有一个工作正常的红黑树算法。当一个节点插入到树中时，insert（）方法返回给调用者一个指向已插入节点的指针。我将所有这些指针存储在STL向量中。跟踪改变指针
问题是，在RB树的操作中，有时这些指针是无效的。例如，在rotateleft/right期间调用的方法会将节点A的值复制到当前节点中，然后删除节点A.那么我在那个向量中有一个指向节点A的指针，现在这个指针是无效的。
我考虑制作的方式来更新在所述载体中的指针如下，
1）保留哪个节点指针映射到保存这些指针的矢量索引多重映射。
2）删除一个节点之前，检查此多重映射找到将受影响
3载体的所有点）遍历向量和老指针更改为新指针
4 ）更新multimap中的键值以反映新指针。
问题是，出于显而易见的原因，您无法更新地图集合的键值。此外，这似乎是一个可怕的解决方案，无论是复杂性和实施的原因。关于如何完成指针动态更新的任何想法？
将数据保存在由节点指向的一些不透明数据结构中，并将外部指针保留到此结构而不是节点似乎更合理。
基本上，它意味着在树和实际数据之间添加一个间接级别。
我不确定你的意思。你能补充一点吗？你的措辞令人困惑，但这或多或少是我想到的。两者之间有一层间接的，我可以保持一致的变化。 – 2011-04-26 23:59:08
@ agent0range：我不明白为什么你需要保存指向节点的指针？无论如何，树木都是这样做的。 – ruslik 2011-04-27 00:03:29
我需要将它们全部存储为一项要求。这全部是在实施额外的信贷。我同意，如果在添加项目时不需要持久存储，则这不会成为问题。我最终使vector包含指向动态分配数据的指针，这些数据也指向节点。工程，但现在我有一些凌乱的堆清理......但这是另一个线程 – 2011-04-27 00:50:24
我不知道这是否是你想要什么做的，而是不断加入到树/堆数据结构项目的跟踪，下面已经在过去的工作对我来说：
商店两个“指数”的载体，除了基本的树数据：
std::vector<int> item_to_tree;
std::vector<int> tree_to_item;
所以，找到在第i个项目的树索引，使用item_to_tree[i]。要在特定的第j个树索引中查找该项目，请使用tree_to_item[j]。这与存储显式指针类似，正如您所做的那样，但通过使用索引，您基本上可以获得具有O（1）查找的双向映射。
显然，在树操作中，您必须确保映射保持一致。我没有为RB树考虑过这个问题，但是对于其他类似树的结构来说，这只是增加了每个操作的O（1）复杂度。
在第i个项目从树中“移除”的情况下，tree_to_item不再包含第i个项目索引，而且我通常设置item_to_tree [i] = -1或某个“空”标志。
希望这会有所帮助。
你可以使用指向下一个节点和前一个节点的指针吗？这样，如果更改指针，则可以按照其“prev”指针并在那里更正指针。 – schnaader 2011-04-26 23:50:21
您的场景听起来不必要的复杂。为什么你需要指向节点的向量？如果你想要所有节点的集合，你可以遍历树。 – Alan 2011-04-26 23:50:53
同意Alan。为什么首先要保持向量中的指针？通常，在不同地方保持原始指针是一个很大的麻烦。 – 2011-04-27 00:59:58