отслеживание смены указателей

Question

У меня есть алгоритм красного черного дерева, который работает нормально.Когда узел вставляется в дерево, метод insert () возвращает вызывающей стороне указатель на вставленный узел.Я храню все такие указатели в векторе STL.

Проблема заключается в том, что в работе дерева RB иногда эти указатели становятся недействительными.Например, есть метод, который вызывается во время rotateleft / right, который копирует значения узла A в текущий узел и затем удаляет узел A. Ну, у меня был указатель на узел A в этом векторе, который теперь недопустим.

Я думал о способе обновления указателей в векторе следующим образом:

1) сохранял мультикарту, которая отображает указатели узлов на индексы векторов, которые содержат эти указатели.

2) Перед удалением узла, проверьте эту мультикарту, чтобы найти все точки в векторе, на которые это повлияет

3) итерируйте по вектору и измените старый указатель на новый указатель

4) Обновите значение ключа в мультикарте, чтобы оно также отражало новый указатель.

Проблема в том, что вы не можете обновить значение ключа коллекции карт по очевидным причинам.Также это кажется ужасным решением как по сложности, так и по причинам реализации.Любые идеи о том, как я могу выполнить это динамическое обновление указателей?

Answer 1

Я не уверен, что это именно то, что вы пытаетесь сделать, но чтобы отслеживать элементы, добавленные в структуры данных дерева / кучи, в прошлом у меня работало:

Сохраните два «индексных» вектора в дополнение к базовым данным дерева:

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 или какой-то "пустой" флаг.

Надеюсь, это поможет.

Answer 2

Представляется более разумным хранить данные в некоторой непрозрачной структуре данных, на которую указывает узел, и сохранять внешние указатели на эти структуры вместо узлов.

В основном это означает добавление уровня косвенности между деревом и фактическими данными.