포인터 변경 추적

Question

정상적으로 작동하는 빨간색 검은 색 트리 알고리즘이 있습니다. 노드가 트리에 삽입되면 insert() 메서드는 호출자에게 삽입 된 노드에 대한 포인터를 반환합니다. 모든 포인터를 STL 벡터에 저장합니다.

문제는 RB 트리가 작동하는 동안 때때로 이러한 포인터가 무효화된다는 것입니다. 예를 들어 노드 A의 값을 현재 노드에 복사 한 다음 노드 A를 삭제하는 rotateleft/right 중에 호출되는 메서드가 있습니다. 이제 노드 A에 대한 포인터가 해당 벡터에서 유효하지 않습니다.

나는

1) 그 포인터를 보유하고있는 벡터 인덱스에 노드 포인터를 매핑 multimap은 유지, 다음과 같이 벡터의 포인터를 업데이트 할 수있는 방법을 생각.

2) 노드를 삭제하기 전에)

3

을 영향을받는 벡터의 모든 지점을 찾을 벡터를 반복하고 새로운 포인터

4 이전 포인터를 변경하려면이과 multimap을 확인) 새로운 포인터를 반영하기 위해 멀티 맵의 키 값을 업데이트하십시오.

문제는 명백한 이유로지도 컬렉션의 키 값을 업데이트 할 수 없다는 것입니다. 또한 이것은 복잡성과 구현상의 이유로 끔찍한 해결책처럼 보입니다. 포인터의 동적 업데이트를 어떻게 수행 할 수 있는지에 대한 아이디어가 있습니까?

Answer 1

노드에서 가리키는 불투명 한 데이터 구조로 데이터를 유지하고 노드 대신이 구조에 대한 외부 포인터를 유지하는 것이 더 합리적인 것처럼 보입니다.

기본적으로 이는 트리와 실제 데이터간에 간접 레벨을 추가하는 것을 의미합니다.

스토어 : 이것은 당신의 과거에 나를 위해 일했다 다음을 수행하기 위해 노력하고 있지만, 트리/힙 데이터 구조에 추가 된 항목을 추적 할 수 정확하게 경우

Answer 2

는 잘 모르겠어요 기본 트리 데이터 외에 두 개의 "인덱스"벡터 :

그래서

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 또는 일부 "빈"플래그를 설정합니다.

희망이 도움이됩니다.