データ構造のソリッドツリー

指定されたフォレストに対して、指定されたエッジの一部を「破線」で作成し、残りのエッジはソリッドに保たれます。各非リーフノードは、その子の1つに対して1つの「ソリッド」エッジにのみ関連付けられます。他のすべての子供たちは、破線のエッジの助けを借りて接続されます。

より具体的には、どのツリーでも、（その子への）右端のリンクを固定し、他の子への他のすべてのリンクを「破線」で作成する必要があります。

その結果、ツリーはソリッドパスのコレクションに分割されます。ソリッドパスのルートは、破線のエッジによって他のソリッドパスに結合されます。 「仮想ツリー」と呼ばれる新しいデータ構造が構築されます。各リンクおよび切断ツリーTは、同じノードのセットを含む仮想ツリーVで表されます。ただし、元のツリーの各ソリッドパスは、仮想ツリーで変更またはバイナリツリーに変換されます。二分木は可能な限りバランスが取れています。したがって、仮想ツリーは、（実線の）左の子、（実線の）右の子、および0個以上の（破線の）中間の子に関連付けられます。

言い換えると、仮想ツリーは、破線のエッジで結合された実線の二分木の階層で構成されます。各ノードは、その親、およびその左右の子へのポインターに関連付けられています。

各パスが二分木に変換されることはわかっています。パス内のノード（たとえばp）の親（たとえばq）は、ソリッドツリー内のそのノード（p）の順序（対称順序）の後継です。ただし、pがソリッドサブツリーの最後のノード（対称的な順序）である場合、その親パスは、それを含むソリッドサブツリーのルートの親になります。

Formally, Parentpath(v) =Node(Inorder(v)+ 1).

どのノードvでも、左側のサブツリーのすべてのノードの順序番号が少なくなり、右側のサブツリーのノードの順序番号が高くなることに注意してください。これにより、左側のサブツリーのすべてのノードが子孫として示され、右側のサブツリーのすべてのノードが祖先として示されます。したがって、左の子の親（バイナリツリー内）は（元のツリー内の）祖先として扱われます。ただし、右の子の親（二分木）は（元のツリーの）子孫として扱われます。この注文は、追加費用を効果的に実行するのに役立ちます。

続行するには、いくつかの定義または表記法が必要です。

mincost（x）を、同じソリッドサブツリー内のxのすべての子孫の中で最小のキー値を持つノードのコストとします。

次に、各ノードに2つのフィールドδ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)