Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조에서 두 개의 최대 HBLT 병합


혼합 전략은 재귀를 사용하여 쉽게 수행됩니다. A와 B가 융합될 두 개의 HBLT라고 가정합니다. 그 중 하나가 비어 있으면 최종 결과로 다른 하나를 만드십시오. 빈 HBLT가 없으면 두 루트의 요소를 비교해야 합니다. 요소가 더 큰 루트가 혼합된 HBLT의 루트가 됩니다.

A에 더 큰 근이 있다고 가정합니다. 그리고 그것은 왼쪽 서브트리가 L입니다. C가 A와 HBLT B의 오른쪽 서브트리를 결합한 결과인 최대 HBLT라고 가정합니다. 최종 HBLT는 A를 루트로, L과 C를 서브트리로 가질 것입니다. L의 s 값이 C의 값보다 작으면 C는 기본적으로 왼쪽 하위 트리입니다. 그렇지 않으면 L은 하위 트리로 남습니다.

와 같은 두 개의 요소가 있다고 가정합니다.

데이터 구조에서 두 개의 최대 HBLT 병합

우리는 그것들을 융합하고 싶습니다. (노드가 값을 가지고 있고, 노드 외부의 숫자는 해당 노드의 s 값입니다.)

이제 합치는 방법을 알아보겠습니다. 7이 9의 오른쪽 자식으로 추가되었지만 여기에서 9의 s(L)은 0이고 9의 s(R)은 1이므로 스왑되고 7이 오른쪽 자식이 됩니다.

데이터 구조에서 두 개의 최대 HBLT 병합

또 다른 예 -

데이터 구조에서 두 개의 최대 HBLT 병합

큰 것의 오른쪽에 작은 HBLT를 임시로 추가합니다.

데이터 구조에서 두 개의 최대 HBLT 병합

이것은 HBLT의 자산을 유지하는 것이 아닙니다.

데이터 구조에서 두 개의 최대 HBLT 병합