跟踪不断变化的指针
我有一个运行良好的红黑树算法。当一个节点被插入到树中时，insert() 方法会向调用者返回一个指向所插入节点的指针。我将所有此类指针存储在 STL 向量中。
问题是，在RB树的运行过程中，有时这些指针会失效。例如，在向左/向右旋转期间调用一个方法，该方法将节点 A 的值复制到当前节点，然后删除节点 A。好吧，我在该向量中有一个指向节点 A 的指针，但现在该指针无效。
我考虑了一种方法来更新向量中的指针，如下所示，
1）保留一个多重映射，它将节点指针映射到保存这些指针的向量索引。
2) 在删除节点之前，检查此多重映射以找到向量中将受到影响的所有点
3) 迭代向量并将旧指针更改为新指针
4) 更新多重映射中的键值以反映新指针指针也是如此。
问题是，由于显而易见的原因，您无法更新地图集合的键值。此外，出于复杂性和实现原因，这似乎是一个可怕的解决方案。关于如何完成指针的动态更新有什么想法吗？
I have a red black tree algorithm which is working fine. When a node is inserted into the tree, the insert() method returns to the caller a pointer to the node that was inserted. I store all such pointers in a STL vector.
The problem is, within the operation of the RB tree, sometimes these pointers are invalidated. For instance, there is a method that is called during a rotateleft/right that copies the values of node A into the current node and then deletes node A. Well I had a pointer to node A in that vector which is now invalid.
I thought about making a way to update the pointers in the vector as follows,
1) keep a multimap which maps node pointers to the vector indices that holds those pointers.
2) Before deleting a node, check this multimap to find all the spots in the vector that will be affected
3) iterate over the vector and change the old pointer to the new pointer
4) Update the key value in the multimap to reflect the new pointer as well.
Problem is, you can't update a key value of a map collection for obvious reasons. Also this seems like a horrible solution both for complexity and implementation reasons. Any ideas on how I can accomplish this dynamic updating of pointers?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
将数据保存在节点指向的某些不透明数据结构中，并保留指向该结构而不是节点的外部指针似乎更合理。
基本上，这意味着在树和实际数据之间添加一个间接级别。
It seems more reasonable to keep the data in some opaque data structure pointed by node, and to keep external pointers to this structures instead of nodes.
Basicly it means adding a level of indirection between the tree and actual data.
我不确定这是否正是您想要做的，但是为了跟踪添加到树/堆数据结构的项目，以下内容过去对我有用：
除了存储两个“索引”向量底层树数据：
因此，要在树中查找第 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 或一些“空”标志。
希望这有帮助。
I'm not sure if this is exactly what you're trying to do, but to keep track of items added to tree/heap data structures, the following has worked for me in the past:
Store two "index" vectors in addition to the underlying tree data:
So, to find the index in the tree of the ith item, use
item_to_tree[i]. To find the item at a particular jth tree index, usetree_to_item[j]. This is similar to storing explicit pointers, as you've done, but by making use of indices you can essentially get a bi-directional map with O(1) lookup.Obviously, within the tree operations, you have to make sure that the mappings stay consistent. I've not thought about this for an RB tree, but definitely for other tree-like structures this just adds some O(1) complexity to each operation.
In the case of the ith item "removed" from the tree,
tree_to_itemno longer contains the ith item index, and I usually set item_to_tree[i] = -1, or some "empty" flag.Hope this helps.