두 AVL 트리 연결/병합/접합

두 AVL 트리 연결/병합/접합

두 개의 AVL 트리가 있고 첫 번째 트리의 각 요소가 두 번째 트리의 각 요소보다 작다고 가정합니다.단일 AVL 트리로 연결하는 가장 효율적인 방법은 무엇입니까?여기저기 찾아봤지만 유용한 것을 찾지 못했습니다.

입력 트리를 파괴할 수 있다고 가정하면 다음과 같습니다.

1. 왼쪽 트리에 대해 가장 오른쪽에 있는 요소를 제거하고 이를 사용하여 왼쪽 하위가 왼쪽 트리이고 오른쪽 하위가 오른쪽 트리인 새 루트 노드를 구성합니다. O(log n)
2. 노드의 균형 계수를 결정하고 설정합니다. O(log n).(일시적으로) 불변성을 위반하는 경우 균형 계수가 {-1, 0, 1} 범위를 벗어날 수 있습니다.
3. 회전하여 균형 계수를 범위로 되돌립니다. O(log n) 회전: O(log n)

따라서 O(log n)에서 전체 연산을 수행할 수 있습니다.

편집: 다시 생각해보면 다음 알고리즘에서 회전에 대한 추론이 더 쉽습니다.또한 속도가 더 빠를 가능성이 높습니다.

1. 두 트리의 높이를 결정합니다. O(log n).
   오른쪽 트리가 더 크다는 가정(다른 경우는 대칭):
2. 가장 오른쪽에 있는 요소를 제거합니다.left나무(필요한 경우 회전 및 계산 높이 조정). Letn그 요소입니다.O(로그n)
3. 오른쪽 트리에서 하위 트리가 최대 1보다 큰 노드에 도달할 때까지 왼쪽으로 탐색합니다.left.허락하다r그 노드가 됩니다.O(로그n)

4. 해당 노드를 값 n과 하위 트리를 가진 새 노드로 바꿉니다.left그리고.r. O(1)
   구성에 따라, 새로운 노드는 AVL 균형을 이루었고, 하위 트리는 다음보다 1개 더 높았습니다.r.

5. 그에 따라 부모의 균형을 증가시킵니다. O(1)

6. 삽입한 후에 다시 균형을 잡는 것처럼 말이죠.O(로그n)

(나무 사이의 관계에서 아무런 가정 없이 작동하는) 아주 간단한 해결책은 다음과 같습니다.

1. 두 트리를 병합된 하나의 배열로 병합 정렬합니다(두 트리를 동시에 반복).
2. 배열에서 AVL 트리를 작성합니다. 중간 요소를 루트로 하고 왼쪽 및 오른쪽 반에 재귀적으로 적용합니다.

두 단계 모두 O(n)입니다.가장 큰 문제는 O(n)개의 여유 공간이 필요하다는 것입니다.

이 문제에 대해 제가 읽은 가장 좋은 해결책은 여기서 찾을 수 있습니다.이 문제를 수정하면 메리트론의 답변에 매우 가깝습니다.

알고리즘의 세 번째 단계에서 하위 트리의 높이가 왼쪽 트리와 같은 노드에 도달할 때까지 왼쪽을 탐색합니다.이것이 항상 가능한 것은 아닙니다(반례 이미지 참조).이 단계를 수행하는 올바른 방법은 높이가 있는 하위 트리에 대한 두 가지 찾기입니다.h아니면h+1어디에h왼쪽 나무의 높이입니다.

제 생각에 여러분은 단지 한 나무를 걷고 (바라건대 작은 나무를) 그 나무의 각각의 요소를 다른 나무에 개별적으로 추가하기만 하면 될 것 같습니다.AVL 삽입/삭제 작업은 한 번에 전체 하위 트리 추가를 처리하도록 설계되지 않았습니다.

언급URL : https://stackoverflow.com/questions/2037212/concatenating-merging-joining-two-avl-trees