リンク/カットツリー

表現されたツリー上でノードvへのアクセスが行われると、そのアクセス経路が優先経路となります。ノードの優先子は、アクセス経路上の最後の子ノードです。ただし、最後のアクセスがvに対して行われた場合、またはこの特定のツリーのブランチへのアクセスが行われなかった場合は null となります。優先エッジは、優先子とvを接続するエッジです。

別のバージョンでは、最も体重の重い子供によって優先経路が決定される。

ノードvへのアクセスを実行すると、v には優先子ノードがなくなり、パスの末尾になります。補助ツリーのノードは深さによってキー付けされているため、補助ツリー内のvの右側にあるノードはすべて切断する必要があります。スプレーツリーでは、これは比較的簡単な手順です。v でスプレーすると、vは補助ツリーのルートになります。次に、vの右サブツリー、つまり前の優先パスでvより下にあったすべてのノードを切断します。切断されたツリーのルートにはパス親ポインタがあり、これをvに向けます。

次に、表現されたツリーをルートRまでたどり、必要に応じて優先パスを切断およびリセットします。これを行うには、vからパス親ポインタをたどります( vがルートになったので、パス親ポインタに直接アクセスできます)。v があるパスに既にルート R が含まれている場合(ノードは深さでキー付けされているため、補助ツリーの左端のノードになります)、パス親ポインタは null になり、アクセスは完了です。そうでない場合は、ポインタをたどって別のパスw上のノードに移動します。wの古い優先パスを切断し、 vがあるパスに再接続します。これを行うには、 wでスプレッドし、その右サブツリーを切り離し、パス親ポインタをwに設定します。すべてのノードは深さでキー付けされており、vのパスのすべてのノードはwのパスのすべてのノードよりも深いため(表現されたツリーではwの子であるため)、 vのツリーをwの右の子として接続します。再びvでスプレッド操作を行うと、vはルートwの子であるため、 vは単純にルートに回転します。vのパス親ポインタがnullになるまでこのプロセス全体を繰り返します。この時点で、vは表現されたツリーRのルートと同じ優先パス上にあります。

FindRoot は、ノードvを含む表現されたツリーのルートを見つけることを指します。アクセスサブルーチンはv を優先パスに配置するため、まずアクセスを実行します。これで、ノードvはルートRと同じ優先パス、つまり同じ補助ツリー上にあります。補助ツリーは深さによってキー付けされているため、ルートRは補助ツリーの最も左のノードになります。したがって、vの左の子を再帰的に選択して、それ以上進めなくなるまで繰り返します。このノードがルートRです。ルートは線形深度になる可能性があるため (これはスプレッド ツリーの最悪のケースです)、次のアクセスが速くなるようにスプレッドします。

ここでは、表現されたツリーをノードvで切断します。まず、 vにアクセスします。これにより、表現されたツリーでvより下位にあるすべての要素が、補助ツリーでvの右の子になります。vの左サブツリーにあるすべての要素は、表現されたツリーでvより上位にあるノードです。したがって、 vの左の子を切断します（この左の子は、パス親ポインタを介して元の表現されたツリーへの接続を維持しています）。これで、vは表現されたツリーのルートになります。v にアクセスすると、vより下位の優先パスも切断されますが、そのサブツリーはパス親ポインタを介してvとの接続を維持します。

vが木のルートで、wが別の木の頂点である場合、 vとw を含む木を、エッジ (v, w) を追加してリンクし、w をvの親にします。これを行うには、それぞれの木でvとwにアクセスし、w をvの左の子にします。vはルートであり、補助木ではノードが深さでキー付けされているため、 vにアクセスすると、 v は補助木に左の子を持たないことになります(ルートであるため、深さが最小になります)。wを左の子として追加すると、表現された木で w がvの親になります。

この操作では、ルートRからノードvまでのパス上のすべてのノード (またはエッジ) に対して、何らかの集計関数(「合計」、「最小値」、「最大値」、「増加」など) を実行します。これを行うには、vにアクセスします。v は、ルートRからノードvまでのパス上のすべてのノードを含む補助ツリーを提供します。このデータ構造には、最小値や最大値、サブツリー内のコストの合計など、取得したいデータを追加できます。これらのデータは、指定されたパスから定数時間で取得できます。

この手法では、部分木内のノード数に応じて、エッジを「重い」または「軽い」と分類します。${\displaystyle Size(v)}$⁠ は、表現されたツリーにおけるvのサブツリー内のノード数を表します。エッジは、size(v) > 1 ⁄ 2 size(parent(v)) の場合、ヘビーエッジと呼ばれます。したがって、各ノードは最大で 1 つのヘビーエッジを持つことができます。ヘビーエッジではないエッジは、ライトエッジと呼ばれます。

ライトデプスとは、ルートから頂点vまでの特定のパス上のライトエッジの数を指します。ライトデプスは lg n以下です。これは、ライトエッジをたどるたびにノード数が少なくとも 2 分の 1 に減少するためです (親ノードの最大半分のノード数しか持つことができないため)。

したがって、表現されたツリー内の特定のエッジは、重度に優先される、重度に優先されない、軽度に優先される、軽度に優先されない、の4つの可能性のいずれかになります。

まず、${\displaystyle O(\log ^{2}n)}$上限値。