두 개의 이진 트리를 결합하는 알고리즘? 예를 들어

Question

:

두 그루의 나무 :

 8     9 
    5  7   4  20 
        30 

하나의 나무가?

Answer 1

자세한 내용/제약 조건이 없으면 가장 간단한 해결책은 두 트리의 리프 노드를 가져와 제거한 다음 새로 만든 세 노드의 루트로 사용하는 것입니다. 당신의 예에서

: 당신의 나무, 특정 순서에 따라 표시되지 않는 균형을 표시하지 않으며, 다른 제약 조건이 있기 때문에

   30 
    8     9 
5  7   4  20 

이 작동합니다.

모든 잎 노드가 할 것이기 때문에

,이에 아이 링크를 추가, 최악의 경우 (우리가 첫번째 잎이 발생할 때까지 제거, 임의의 순서로 나무 중 하나를 통과에 O ( N) 작업입니다 두 나무 뿌리).

Answer 2

기본 답변은 더 작은 트리의 모든 요소를 ​​큰 트리에 추가하는 것입니다.

또 다른 possiblity가은 (자기 균형 나무) B-나무를 조사하는 것입니다

Answer 3

왼쪽 자식이없는 노드에 도달 할 때까지 하나의 트리의 왼쪽 자식을 반복 수행하는 두 개의 이진 트리를 병합하는 가장 쉬운 방법 . 그런 다음 다른 트리의 루트를 왼쪽 자식으로 추가하십시오. 예를 들어 결과 트리는 다음과 같습니다.

  8 
     5  7 
    9 
    4 20 
30 

그러나이 예제에서 결과 트리가 어떻게 매우 불균형한지 확인하십시오. 이렇게하면 결과 트리가 비효율적으로 작동합니다. 더 나은 해결책은 두 번째 트리의 노드를 첫 번째 트리에 균등하게 분배하는 것입니다. 이를 달성하는 한 가지 방법은 두 번째 트리의 루트 및 왼쪽 하위 트리를 첫 번째 트리의 왼쪽 하위 트리에, 오른쪽 하위 트리를 오른쪽 하위 트리에 재귀 적으로 추가하는 것입니다. 조금 더 균등하게 분배하려면 각 단계에서 루트를 할당 할 쪽을 무작위로 선택하십시오.

여기서 이진 트리는 이 아니고 이진 검색 트리입니다. 결과 트리가 유효한 BST인지 확인해야하기 때문에 BST로 작업하는 것이 약간 재미 있습니다. 관심있는 사람들은 다음과 같은 문제에 대한 해결책입니다. 트리 1에서 트리 2의 근음 값을 찾습니다.이 값을 찾지 못해 막 다른 곳에 도달하면 트리 2를 값이있는 위치에 삽입하면됩니다. 그것이 나무에 있었습니까? 값을 찾으면 그 노드를 트리 2로 대체 할 수 있습니다. 그런 다음 옮겨진 노드를 루트로하는 서브 트리를 가져 와서 동일한 알고리즘을 사용하여 트리 2에 삽입하십시오.