병합(meld) 전략은 재귀 호출을 활용하면 손쉽게 구현할 수 있습니다. 병합하고자 하는 두 개의 HBLT(Height-Biased Leftist Tree, 높이 편향 좌편향 트리)를 A와 B라고 가정해 봅시다. 만약 둘 중 하나가 비어 있다면, 나머지 하나를 그대로 최종 결과로 삼으면 됩니다. 두 HBLT 모두 비어 있지 않다면, 먼저 두 루트에 있는 원소를 비교해야 합니다. 이때 더 큰 원소를 가진 루트가 병합된 HBLT의 루트가 됩니다.
A의 루트가 더 크다고 가정해 보겠습니다. A의 왼쪽 서브트리를 L이라 하고, A의 오른쪽 서브트리와 B를 병합하여 얻어지는 최대 HBLT를 C라고 합시다. 그러면 최종 HBLT는 A를 루트로 하고, L과 C를 서브트리로 갖는 형태가 됩니다. 여기서 중요한 점은, L의 s값(s-value)이 C의 s값보다 작다면 C가 왼쪽 서브트리가 되고, 그렇지 않으면 L이 왼쪽 서브트리가 된다는 것입니다. 이러한 교환 과정을 통해 HBLT의 핵심 성질인 '왼쪽 자식의 s값이 오른쪽 자식의 s값보다 크거나 같다'는 조건이 항상 유지됩니다.
병합 예시 1
다음과 같은 두 개의 HBLT가 있다고 가정해 보겠습니다.
이 두 트리를 병합해 보겠습니다. 참고로 노드 안의 숫자는 원소 값을 의미하며, 노드 바깥의 숫자는 해당 노드의 s값을 나타냅니다.
먼저 7을 9의 오른쪽 자식으로 추가한다고 생각해 봅시다. 그런데 9의 왼쪽 자식 s값 s(L)는 0이고, 오른쪽 자식 s값 s(R)는 1입니다. HBLT의 성질을 만족하려면 왼쪽 자식의 s값이 오른쪽 자식보다 크거나 같아야 하므로, 두 자식의 위치를 서로 교환해야 합니다. 그 결과 7이 9의 오른쪽 자식으로 위치하게 됩니다.
병합 예시 2
이번에는 더 작은 HBLT를 더 큰 HBLT의 오른쪽에 임시로 붙여 보겠습니다.
그러나 이 상태에서는 왼쪽 자식의 s값 조건이 깨져 있으므로, HBLT의 성질이 올바르게 유지되지 않습니다. 따라서 s값 조건을 만족하도록 자식 노드들의 위치를 다시 조정해 주어야 최종적인 병합이 완성됩니다.
