솔리드 트리(Solid Tree)의 기본 개념
주어진 숲(forest)에서 일부 간선은 "점선(dashed)"으로 표시하고, 나머지 간선은 "실선(solid)"으로 유지합니다. 각 리프가 아닌 노드는 자식 중 단 하나만 "실선" 간선으로 연결하며, 나머지 모든 자식은 점선 간선을 통해 연결됩니다.
보다 구체적으로 설명하면, 임의의 트리에서 가장 오른쪽에 있는 링크(자식을 향한 링크)는 실선으로 유지하고, 다른 자식들을 향한 모든 링크는 "점선"으로 만듭니다.
실선 경로와 가상 트리(Virtual Tree)
그 결과 트리는 여러 개의 실선 경로(solid path) 집합으로 분해됩니다. 각 실선 경로의 루트는 점선 간선을 통해 다른 실선 경로와 연결됩니다. 이렇게 구성된 새로운 자료구조를 "가상 트리(virtual tree)"라고 합니다.
연결(linking)과 절단(cutting) 연산이 가능한 트리 T는 동일한 노드 집합을 포함하는 가상 트리 V로 표현됩니다. 원본 트리의 각 실선 경로는 가상 트리에서 이진 트리(binary tree)로 변환되며, 이때 이진 트리는 최대한 균형 잡힌 형태가 됩니다. 따라서 가상 트리의 각 노드는 (실선인) 왼쪽 자식, (실선인) 오른쪽 자식, 그리고 0개 이상의 (점선인) 가운데 자식과 연결됩니다.
다시 말해, 가상 트리는 점선 간선으로 연결된 실선 이진 트리들의 계층 구조로 이루어져 있습니다. 각 노드는 부모 노드와 왼쪽·오른쪽 자식 노드를 가리키는 포인터를 가지고 있습니다.
중위 순서(Inorder) 기반 부모 관계
각 경로는 하나의 이진 트리로 변환됩니다. 이때 경로 내 어떤 노드 p의 부모 q는 실선 트리에서 해당 노드 p의 중위 순서(inorder, 대칭 순서) 후계자가 됩니다. 다만 p가 실선 서브트리에서 대칭 순서상 마지막 노드라면, 그 부모 경로는 해당 노드가 속한 실선 서브트리 루트의 부모가 됩니다.
Parentpath(v) = Node(Inorder(v) + 1)
임의의 노드 v에 대해 왼쪽 서브트리의 모든 노드는 더 작은 중위 번호를, 오른쪽 서브트리의 노드들은 더 큰 중위 번호를 가집니다. 이러한 특성 덕분에 왼쪽 서브트리의 모든 노드는 자손(descendant)으로, 오른쪽 서브트리의 노드들은 조상(ancestor)으로 명확하게 구분할 수 있습니다. 즉, 이진 트리에서 왼쪽 자식의 부모는 원본 트리에서 조상으로 취급되고, 반대로 이진 트리에서 오른쪽 자식의 부모는 원본 트리에서 자손으로 취급됩니다. 이러한 순서 체계 덕분에 비용 추가(add cost) 연산을 효율적으로 수행할 수 있습니다.
비용 계산을 위한 필드 정의
설명을 진행하기 위해 몇 가지 정의와 표기법이 필요합니다.
mincost(x)를 동일한 실선 서브트리 내에서 x의 모든 자손 중 최소 키 값을 가진 노드의 비용이라고 정의합니다.
그리고 각 노드에는 δcost(x)와 δmin(x)라는 두 개의 필드를 저장합니다. 정의는 다음과 같습니다.
δmin(x) = cost(x) − mincost(x) δcost(x) = cost(x) − cost(parent(x)) (x가 실선 부모를 가질 경우) δcost(x) = cost(x) (그 외의 경우, x는 실선 트리의 루트로 취급)