A-sort는 어떻게 작동합니까?

Question

일부 정렬 된 시퀀스를 정렬하기 위해 (a, b) - 트리를 사용하는 A- 정렬 (asort())이 아닌 동작에 대해 설명해 줄 수 있습니까?

Answer 1

알고리즘 자체는 매우 간단합니다. 기본적으로 트리의 모든 요소를 ​​삽입 한 다음 트리를 따라 순서대로 요소를 읽습니다.

거의 이미 정렬 순서에 대한 더 나은 성능을 얻으려면, 다음과 같은 수정을 사용

1. 이 나무는 O(1) 상각 삽입 재조정 시간이 과 (A, B) 트리해야합니다.
2. 나무는 (전체 트리를 통해) 같은 레벨에있는 노드의 형제 자매에 대한 링크

이 순서를 가정, 그냥 빨리 다음 요소가 속한 장소를 찾을 필요는 O(1) 삽입 시간을 활용하기를 포함 거의 정렬되어 있으므로 (이전 요소가 삽입 된 곳과 멀리 떨어져 있지 않습니다). 다음과 같이 대략 수행됩니다

• 당신은
• 다음 요소는이 노드 또는이 노드의 하위 트리에 속하지 않는 경우 확인을 삽입 이전 요소에서 시작; 그렇지 않으면, 당신은 형제 자매 형제의 값이 여전히 너무 큰 경우, 당신이 한 단계 위로 이동하고 새로운 요소 경우
• 를 반복
• (가 왼쪽 형제 될 수 있도록의 새로운 요소가 작은 가정 해 봅시다)보고 형제의 하위 트리에 속하면 정상 검색을 수행합니다.
• 새 요소가 형제 노드와이 노드 사이에 속하면 가장 가까운 하위 노드로 이동하여 적절한 하위 트리를 찾을 때까지 검색을 반복하십시오.

이 방법을 사용하면 k 단계에있는 트리의 a^k 요소를 탐색 할 수 있으므로, O(log(distance(current, previous)) 새 요소의 적절한 위치를 찾을 시간. 상각 된 O(1)의 재조정을 감안할 때 O(n log n)을 최악의 상태로 유지하면서 거의 정렬 된 시퀀스의 경우 O(n log n) 시간보다 좋아집니다.