재조정 알고리즘은 다음과 같은 방식으로 수행할 수 있습니다. -
데이-스타우트-워렌 알고리즘
Day-Stout-Warren 알고리즘을 사용하여 실제로 재조정 방법을 구현할 수 있습니다. 노드 수에서 선형입니다.
다음은 기본 DSW 알고리즘을 의사 코드로 표현한 것입니다.
- "의사 루트"라고 하는 노드가 할당되고 트리의 실제 루트를 가상 루트의 오른쪽 자식으로 만듭니다.
- 트리를 인수로 의사 루트를 사용하여 정렬된 연결 목록으로 트리를 변환하기 위해 트리 대 덩굴 함수를 호출합니다.
- 의사 루트와 트리의 크기(요소 수)를 인수로 사용하여 정렬된 연결 목록을 다시 트리로 변환하는 vine-to-tree 함수를 호출합니다.
- 가상 루트의 오른쪽 자식과 동일한 트리의 실제 루트가 빌드되어야 합니다.
- 마침내 의사 루트를 삭제해야 합니다.
"쓰기 시 복사" 트리
선형화 가능성의 부족을 견딜 수 있다면(즉, 값을 작성하지만 발견되지 않은 직후에 검색할 때, 결국 발견되지만 100ms-10초 후에) "쓰기 시 복사" 트리를 적용할 수 있습니다. 모든 쓰기는 하나의 스레드(재조정 포함)에서 수행되며 동시성 제어 없이 스레드를 읽어 구현할 수 있는 읽기 전용 복사본으로 트리를 주기적으로 복사하므로 원자적으로 게시해야 합니다.
동시 건너뛰기 목록
또 다른 옵션은 동시 건너뛰기 목록을 구현하는 것입니다. 대수 평균 케이스 검색/삭제/삽입 시간을 제공하고 더 쉽게 병렬화할 수 있습니다. 구현하는 경우 Java에 대한 표준 잠금 없는 구현이 있습니다. 여기에서 동시 건너뛰기 목록과 균형 검색 트리에 대한 자세한 정보를 얻을 수 있습니다. 특히, 동시 재조정에 최적화된 이진 검색 트리로 표시되는 크로매틱 트리에 대한 언급을 얻을 수 있습니다.