트리 기반 탐색

G1. [1단계 시작.] 0 ≤ k ≤ n에 대해 W(k) ← w_k, L(k) ← R(k) ← Λ를 설정한다. 또한 A₀ ← 2n+1, W(A₀) ← ∞, A₁ ← 0, t ← 1, m ← n을 설정한다. 그런 다음 r = 1, 2, ..., n에 대해 단계 G2를 수행하고, G3으로 간다.

G2. [w_r 흡수.] (이 시점에서 기본 조건 W(A₀) > W(A₂) > W(A₄) > ...와 W(A₁) > W(A₃) > W(A₅) > ...를 갖는다. 다시 말해, 작업 배열의 가중치는 "2-감소"한다.) W(A_{t-1}) ≤ w_r이면, k ← t를 설정하고 아래의 서브루틴 C를 수행하고 단계 G2를 반복한다. 그렇지 않으면 t ← t + 1, A_t ← r을 설정한다.

G3. [1단계 완료.] t > 1인 동안, k ← t를 설정하고 서브루틴 C를 수행한다.

G3. [1단계 완료.] t > 1인 동안, k ← t를 설정하고 서브루틴 C를 수행한다.

G4. [2단계 수행.] (이제 A₁ = 2n이 이진 트리의 루트이고, W(A₁) = w₀ + ... + w_n이다.) 0 ≤ k ≤ n에 대해 l_k를 노드 k에서 노드 A₁까지의 거리로 설정한다. (연습문제 43 참조. 예가 그림 18에 나와 있으며, 레벨 번호가 각 노드의 오른쪽에 나타난다.)

G5. [3단계 수행.] n+1, ..., 2n의 링크를 변경하여 같은 레벨 번호 l_k를 갖지만 잎 노드가 대칭 순서 0, ..., n인 새 이진 트리를 구성한다. (연습문제 44 참조. 예가 그림 19에 나와 있다.)

G5. [3단계 수행.] n+1, ..., 2n의 링크를 변경하여 같은 레벨 번호 l_k를 갖지만 잎 노드가 대칭 순서 0, ..., n인 새 이진 트리를 구성한다. (연습문제 44 참조. 예가 그림 19에 나와 있다.)

서브루틴 C (결합). 이 재귀 서브루틴은 Garsia-Wachs 알고리즘의 핵심이다. 두 가중치를 결합하고, 적절히 왼쪽으로 이동하고, 2-감소 조건 (31)을 유지한다. 변수 j와 w는 지역적이지만, 변수 k, m, t는 전역적이다.

C1. [새 노드 생성.] (이 시점에서 k ≥ 2이다.) m ← m + 1, L(m) ← A_{k-1}, R(m) ← A_k, W(m) ← w ← W(A_{k-1}) + W(A_k)를 설정한다.