현재 응용 프로그램에 대한 최적화를 수행하기 위해 red-black 트리 데이터 구조를 구현 중입니다.빨강 - 검정 나무의 전체 하위 트리를 삭제하면 속성이 유지됩니까?
내 응용 프로그램에서 주어진 지점에서 주어진 값보다 작거나 같은 모든 요소를 제거해야합니다 (요소가 정수라고 가정 할 수 있음).
요소를 하나씩 삭제할 수 있지만 더 빨리 처리하고 싶습니다. 따라서, 내 질문은 : 만약 내가 붉은 - 검정 나무의 전체 하위 트리를 삭제, 어떻게 높이와 색상 불변성을 복구하기 위해 나무를 해결할 수 있을까?
빨강 - 검정 트리에서 요소 하나를 삭제하면 O (log n) 시간이 걸립니다. 여기서 n은 현재 트리에있는 요소의 수입니다.
일부 요소 만 제거하는 경우 O (k log n) 연산 (k = 제거 된 요소, n = 제거하기 전에 트리의 요소)으로 끝내는 것이 가장 좋습니다.
그러나 많은 수의 노드 (예 : 트리의 50 % 이상)를 제거한다는 것을 알고 있다면 유지하려는 요소를 반복하는 것이 좋습니다 (O (k ') operation k '= 유지 될 요소), 메모리 관리 스키마에 따라 트리 (O (1) 또는 O (n))를 스크랩하고 트리 (O (k'log k ')) 작업을 다시 빌드하십시오. 전체 복잡도는 다음과 같다. O (k 'log k') = O 나무의 %).
어쨌든 요점은 요소의 대부분을 제거하려고 할 때 유지하려는 트리를 열거하고 트리를 다시 작성하는 것이 좋습니다.
블랙 - 블랙 불변량이 꽤 나쁘게 엉망이되기 때문에 레드 - 블랙 트리에서 벌크 삭제가 어렵습니다. 당신이 (소프트) 실시간으로하지 않는다고 가정 할 때, 나는 하나 하나씩 삭제할 것입니다. (하나씩 삽입해야하기 때문에 여기서는 더 작은 상수 요소에 대해 말하고 있습니다) 또는 스플레이 트리로 전환하십시오 .
편집 : 아래는 일반적인 하위 트리 삭제를위한 것입니다. 필요한 것은 실제 질문 내용에 기초한 단일 Split 작업입니다.
최악의 경우 O(log n) 시간에 레드 - 블랙 트리의 전체 하위 트리를 삭제할 수 있습니다.
적갈색 트리에서 Split 및 Join 작업이 O(log n) 시간에 수행 될 수 있음이 알려져 있습니다.
분할 : 값 (K) 및 레드 - 블랙 트리 개의 레드 - 블랙 나무 T1으로 T 분할 T 및 T2되도록 T2에서 T1 < K의 모든 값 및 모든 값> = K 주어. T1에서 T2 (또는 T1 < 짧은 = T2)에서 < = 분 단일 레드 - 블랙 트리 T를 T1으로 두 레드 - 블랙 나무 T1 및 T2를 결합 T2가 최대 :
가입.
필요한 것은 두 개가 Splits이고 한 개가 Join입니다.
삭제해야 할 하위 트리가 L <= v <= U의 값 범위에 해당합니다.
먼저 Split을 L로 설정하면 T1이 T1 및 T2가 T1 < = T2가됩니다. Split T3에서 T3 및 T4를 얻으려면 T2에 대해 T2 < = T4. 이제 Join 나무 T1과 T4. 의사에서
, 코드는 다음과 같이 표시됩니다 https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree
:Tree DeleteSubTree(Tree tree, Tree subTree) {
Key L = subTree.Min();
Key U = subTree.Max();
Pair <Tree> splitOnL = tree.Split(L);
Pair <Tree> splitOnU = splitOnL.Right.Split(U);
Tree newTree = splitOnL.Left.Join(splitOnU.Right);
return newTree;
}
자세한 내용은이 참조