두 개의 AVL 나무를 연결/병합/합류합니다

Question

내가 두 개의 AVL 나무가 있고 첫 번째 나무의 각 요소가 두 번째 나무의 요소보다 작다고 가정합니다. 하나의 단일 AVL 트리에 연결하는 가장 효율적인 방법은 무엇입니까? 나는 어디에서나 검색했지만 유용한 것을 찾지 못했습니다.

Answer 1

입력 트리를 파괴 할 수 있다고 가정합니다.

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 트리 (필요한 경우 계산 된 높이 회전 및 조정). 허락하다 n 그 요소가 되십시오. O (로그 N)
3. 오른쪽 트리에서 하위 트리가 최대 1 개의 키가 큰 노드에 도달 할 때까지 왼쪽을 탐색 left. 허락하다 r 그 노드가 되십시오. O (로그 N)

4. 해당 노드를 새 노드로 값 n 및 하위 트리로 바꾸십시오. left 그리고 r. o (1)
   시공으로 새로운 노드는 AVL 균형을 잡고 하위 트리 1이 r.

5. 그에 따라 부모의 균형을 늘리십시오. o (1)

6. 그리고 삽입 한 후 당신처럼 재조정합니다. O (로그 N)

Answer 2

하나의 매우 간단한 솔루션 (나무 사이의 관계에 대한 가정없이 작동)은 다음과 같습니다.

1. 두 나무를 하나의 합병 어레이로 합병하십시오 (동시에 두 나무를 반복).
2. 배열에서 AVL 트리를 만들 - 중간 요소를 뿌리로 삼고 왼쪽과 오른쪽 반쪽에 재귀 적으로 바르십시오.

두 단계 모두 O (n)입니다. 주요 문제는 O (N) 추가 공간이 필요하다는 것입니다.

Answer 3

이 문제를 읽은 최상의 솔루션을 찾을 수 있습니다. 여기. 매우 가깝습니다 메리 톤이 문제를 해결하면 답변 :

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

Answer 4

나는 당신이 단지 하나의 나무를 걸어 가야한다고 생각합니다 (희망적으로 더 작은). 다른 나무에 각각의 요소를 개별적으로 추가해야합니다. AVL 삽입/삭제 작업은 한 번에 전체 하위 트리를 추가하도록 설계되지 않았습니다.