我有一个运行良好的红黑树算法。当一个节点被插入到树中时， insert() 方法向调用者返回一个指向被插入节点的指针。我将所有此类指针存储在 STL 向量中。
问题是，在RB树的操作中，有时这些指针是无效的。例如，有一个在左/右旋转期间调用的方法，它将节点 A 的值复制到当前节点，然后删除节点 A。好吧，我在那个向量中有一个指向节点 A 的指针，现在它是无效的。
我考虑过一种方法来更新向量中的指针，如下所示，
1）保留一个multimap，它将节点指针映射到保存这些指针的向量索引。
2）在删除一个节点之前，检查这个多图来找到向量中所有会受到影响的点
3）遍历向量并将旧指针更改为新指针
4) 更新多重映射中的键值以反映新指针。
问题是，由于显而易见的原因，您无法更新地图集合的键值。此外，出于复杂性和实施原因，这似乎是一个可怕的解决方案。关于如何完成指针的这种动态更新的任何想法？
将数据保存在节点指向的一些不透明数据结构中，并保存指向该结构的外部指针而不是节点，似乎更合理。
基本上，这意味着在树和实际数据之间添加一个间接级别。
我不确定这是否正是您想要做的，但是为了跟踪添加到树/堆数据结构中的项目，以下内容过去对我有用：
除了基础树数据之外，还存储两个“索引”向量：
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，或一些“空”标志。
希望这可以帮助。