주어진 숲에 대해 우리는 주어진 가장자리 중 일부를 "점선"으로 만들고 나머지는 단색으로 유지합니다. 리프가 아닌 각 노드는 자식 중 하나에 대한 단 하나의 "솔리드" 에지와 연결됩니다. 다른 모든 어린이는 점선의 도움으로 연결됩니다.
더 구체적으로 말하면, 주어진 트리에서 가장 오른쪽에 있는 링크(자식에 대한)는 견고하게 유지되어야 하고, 다른 자식에 대한 다른 모든 링크는 "점선"으로 생성됩니다.
결과적으로 트리는 솔리드 경로 모음으로 나뉩니다. 솔리드 경로의 루트는 점선으로 다른 솔리드 경로에 연결됩니다. "가상 트리"로 표시된 새로운 데이터 구조가 구성됩니다. 각 연결 및 절단 트리 T는 동일한 노드 세트를 포함하는 가상 트리 V로 표시됩니다. 그러나 원래 트리의 각 솔리드 경로는 가상 트리에서 수정되거나 이진 트리로 변환됩니다. 이진 트리는 가능한 한 균형을 이룹니다. 따라서 가상 트리는 (실선) 왼쪽 자식, (실선) 오른쪽 자식 및 0개 이상의 (점선) 중간 자식과 연결됩니다.
즉, 가상 트리는 점선으로 연결된 솔리드 이진 트리의 계층 구조로 구성됩니다. 각 노드는 부모와 왼쪽 및 오른쪽 자식에 대한 포인터와 연결됩니다.
우리는 각 경로가 이진 트리로 변환된다는 것을 알고 있습니다. 경로에 있는 노드(예:p)의 부모(예:q)는 솔리드 트리에서 해당 노드(p)의 순차(대칭 순서) 계승자입니다. 그러나 p가 솔리드 하위 트리의 마지막 노드(대칭 순서로)이면 해당 상위 경로는 이를 포함하는 솔리드 하위 트리 루트의 상위가 됩니다.
Formally, Parentpath(v) =Node(Inorder(v)+ 1).
임의의 노드 v에 대해 왼쪽 하위 트리의 모든 노드는 더 적은 중위 번호를 갖고 오른쪽 하위 트리의 노드는 더 높은 중위 번호를 갖습니다. 이렇게 하면 왼쪽 하위 트리의 모든 노드가 자손으로 표시되고 오른쪽 하위 트리의 모든 노드가 조상으로 표시됩니다. 따라서 왼쪽 자식의 부모(이진 트리에서)는 (원래 트리에서) 조상으로 취급됩니다. 그러나 오른쪽 자식의 부모(바이너리 트리에서)는 (원래 트리에서) 자손으로 취급됩니다. 이 주문은 비용 효율적으로 추가를 수행하는 데 도움이 됩니다.
계속 진행하려면 몇 가지 정의나 표기법이 필요합니다.
mincost(x)를 동일한 솔리드 하위 트리에서 x의 모든 자손 중에서 최소 키 값을 갖는 노드의 비용이라고 하자.
그런 다음 각 노드에 δcost(x) 및 δmin(x) 필드 두 개를 저장합니다. 우리는 정의합니다.
δmin(x) =cost(x)−mincost(x). And, δcost(x) =cost(x)− cost(parent(x)) if x is associated with a solid parent δcost(x) =cost(x) otherwise (x is treated as a solid tree root)