トップツリー

トップツリーは、ルートのない動的ツリーのための二分木に基づくデータ構造で、主にさまざまなパス関連の操作に使用されます。シンプルな分割統治アルゴリズムを可能にします。その後、直径、中心、中央値など、 ツリーのさまざまなプロパティを動的に維持するように拡張されました

トップツリーは、基底ツリーTと、外部境界頂点と呼ばれる最大2つの頂点の 集合に対して定義されます。${\displaystyle \Re}$ ${\displaystyle \partial {T}}$

基底ツリー（黒色のノード）上に構築されたトップツリーを示す画像。エッジクラスターに分割されたツリーと、それに対応する完全なトップツリー。トップツリー内の塗りつぶされたノードはパスクラスター、小さな円のノードはリーフクラスターです。大きな円のノードはルートです。大文字はクラスター、小文字はノードを表します。

用語集

境界ノード

境界頂点を参照

境界頂点

接続されたサブツリー内の頂点は、サブツリーの外側の頂点にエッジによって接続されている場合、 境界頂点になります。

外部境界頂点

最上位ツリーの最大2つの頂点は外部境界頂点と呼ばれ、最上位ツリー全体を表すクラスターの境界頂点と考えることができます ${\displaystyle \Re}$

クラスター

クラスターは、最大2つの境界頂点を持つ連結された部分木です。与えられたクラスターCの境界頂点の集合は次のように表されます。ユーザーは 各クラスターCにメタ情報を関連付け 、様々な内部操作においてそれを維持する方法を提供 できます${\displaystyle \partial {C}.}$ ${\displaystyle I({\mathcal {C}}),}$

パスクラスター

少なくとも1つの辺を含む場合、 Cはパスクラスターと 呼ばれます${\displaystyle \pi ({\mathcal {C}})}$

点クラスター

リーフクラスターを参照

リーフクラスター

エッジを含まない場合、つまりCに境界頂点が1つしかない場合、C はリーフクラスターと呼ばれます${\displaystyle \pi ({\mathcal {C}})}$

エッジクラスター

単一のエッジを含むクラスターは、エッジクラスターと呼ばれ ます

リーフエッジクラスター

元のクラスター内のリーフは、境界頂点を1つだけ持つクラスターで表され、リーフエッジクラスターと 呼ばれます

パスエッジクラスター

2つの境界ノードを持つエッジクラスターは、パス エッジクラスターと呼ばれます

内部ノード

内のノードは Cの内部ノードと呼ばれます${\displaystyle {\mathcal {C}}\setminus \partial {C}}$

クラスターパス

Cの境界頂点間のパスはCのクラスターパスと呼ばれ、次のように表されます${\displaystyle \pi ({\mathcal {C}}).}$

マージ可能なクラスター

2 つのクラスターAとB は、シングルトン セット (共通するノードが 1 つだけある) であり、クラスターである 場合はマージ可能です。${\displaystyle {\mathcal {A}}\cap {\mathcal {B}}}$ ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}$

はじめに

トップツリーは、リンクおよびカット操作下で動的フォレスト（ツリーの集合）を維持するために使用されます

基本的な考え方は、元のツリーT内のノードの数（つまり時間）に応じて対数的な高さのバランスの取れたバイナリ ツリーを維持することです。 最上位のツリーは、基本的に元のツリーTをクラスターに 再帰的に分割したものを表します。${\displaystyle \Re}$ ${\displaystyle {\mathcal {O}}(\log n)}$

一般に、木T のエッジには重みがかかっている場合があります。

元のツリーTのエッジと最上位ツリーのリーフ ノードには 1 対 1 の対応があり、各内部ノードは、その子であるクラスターの結合によって形成されるクラスターを表します。 ${\displaystyle \Re}$ ${\displaystyle \Re}$

トップツリーデータ構造は時間内に初期化できます。 ${\displaystyle {\mathcal {O}}(n)}$

したがって、上のトップツリーは、 ${\displaystyle \Re}$ ${\displaystyle ({\mathcal {T}},\partial {T})}$

• のノードはのクラスターです。${\displaystyle \Re}$ ${\displaystyle ({\mathcal {T}},\partial {T})}$
• の葉はTの端です。${\displaystyle \Re}$
• 兄弟クラスターは、単一の頂点で交差するという意味で隣接しており、その親クラスターはそれらの結合です。
• のルートは、最大 2 つの外部境界頂点のセットを持つツリーT自体です。${\displaystyle \Re}$

頂点が 1 つのツリーには空のトップ ツリーがあり、エッジのみのツリーには単一のノードがあります。

これらのツリーは自由に拡張可能であり、データ構造の内部動作の詳細（ブラック ボックスとも呼ばれる）に立ち入ることなく、ユーザーは幅広い柔軟性と生産性を実現できます。

動的操作

以下の3つは、ユーザーが許可するフォレスト更新です。

• Link(v, w):ここで、vとwは異なる木T ₁とT ₂の頂点です。これは、以下を表す単一のトップツリーを返します${\displaystyle \Re _{v}\cup \Re _{w}\cup {(v,w)}}$
• Cut(v, w) :トップツリーを持つツリーTからエッジを削除し、2 つのツリーT _vとT _wに変換して、2 つのトップツリーとを返します。${\displaystyle {(v,w)}}$ ${\displaystyle \Re ,}$ ${\displaystyle \Re _{v}}$ ${\displaystyle \Re _{w}}$
• Expose(S) : 最上位ツリーに対するほとんどのクエリを実行するためのサブルーチンとして呼び出されます。Sには最大2つの頂点が含まれます。元の外部頂点を通常の頂点に変換し、Sの頂点を最上位ツリーの新しい外部境界頂点にします。S が空でない場合、新しいルートクラスタCを返します。頂点が異なるツリーに属している場合、Expose({v,w})は失敗します。${\displaystyle \partial {C}=S.}$

内部操作

フォレストの更新はすべて、最大で一連の内部操作によって実行され、そのシーケンスはさらに時間とともに計算されます。ツリーの更新中に、リーフクラスターがパスクラスターに変化したり、その逆が起こることがあります。トップツリーの更新は、これらの内部操作によってのみ行われます ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle {\mathcal {O}}(\log n)}$

は、各内部操作に関連付けられたユーザー定義関数を呼び出すことによって更新されます。 ${\displaystyle I({\mathcal {C}})}$

${\displaystyle \mathrm {マージ} ({\mathcal {A}},{\mathcal {B}})}$

ここでAとBはマージ可能なクラスタであり、 AとBの親クラスタとしてCが返され、境界頂点は境界頂点として計算されます。${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$ ${\displaystyle I({\mathcal {C}})}$ ${\displaystyle I({\mathcal {A}})}$ ${\displaystyle I({\mathcal {B}}).}$

${\displaystyle \mathrm {Split} ({\mathcal {C}})}$

ここで、Cはルート クラスターです。を更新して使用し、その後、からクラスターCを削除します。${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$ ${\displaystyle I({\mathcal {A}})}$ ${\displaystyle I({\mathcal {B}})}$ ${\displaystyle I({\mathcal {C}})}$ ${\displaystyle \Re}$

Split は通常、メソッドを使用して実装されます。メソッドは、更新のためにユーザーメソッドを呼び出し、メソッドと更新を使用して、子要素に保留中の更新がないことを確認します。その後、ユーザー定義関数を呼び出すことなく、 Cは破棄されます。Splitを必要としないクエリでは、多くの場合Cleanが必要です。Split が Clean サブルーチンを使用せず、Clean が必要な場合は、 MergeとSplit を組み合わせることで、オーバーヘッドを伴いますが、その効果を実現できます。 ${\displaystyle \mathrm {Clean} ({\mathcal {C}})}$ ${\displaystyle I({\mathcal {A}})}$ ${\displaystyle I({\mathcal {B}})}$ ${\displaystyle I({\mathcal {C}})}$ ${\displaystyle I({\mathcal {C}})}$

次の 2 つの関数は上記の 2 つの関数に類似しており、基本クラスターに使用されます。

${\displaystyle \mathrm {作成} (v,w)}$

エッジセットのクラスターCを最初から計算して作成します。${\displaystyle (v,w).}$ ${\displaystyle \partial {C}=\partial (v,w).}$ ${\displaystyle I({\mathcal {C}})}$

${\displaystyle \mathrm {根絶} ({\mathcal {C}})}$

Cはエッジ クラスターです。ユーザー定義関数が呼び出されて処理され、その後、クラスターC がトップ ツリーから削除されます。${\displaystyle (v,w).}$ ${\displaystyle I({\mathcal {C}})}$

非ローカル検索

ユーザーは、ルート (非リーフ) クラスターの子クラスターの 1 つを選択するChoose${\displaystyle ({\mathcal {C}}){:}}$ 操作を定義できます。トップ ツリー ブラックボックスには、選択されたすべてのクラスターの交差点で唯一のエッジを見つけるようにChooseクエリとトップ ツリーの再編成 (内部操作を使用) を構成するSearch${\displaystyle ({\mathcal {C}}){:}}$ ルーチンが用意されています。場合によっては、検索をパスに限定する必要があります。このような目的のために、非ローカル検索のバリエーションがあります。ルート クラスターCに 2 つの外部境界頂点がある場合、エッジはパス 上でのみ検索されます。次の変更を行うだけで十分です。ルート クラスターの子のうち 1 つだけがパス クラスターである場合は、Choose操作を呼び出さずにデフォルトでそのパス クラスターが選択されます。 ${\displaystyle \pi ({\mathcal {C}})}$

非ローカル検索の例

vからwへの長いパス上の i 番目のエッジを見つけるには、C =Expose({v,w})を実行し、適切なChooseを使ってSearch( C )を実行します。Choose を実装するには、vを表すグローバル変数とiを表すグローバル変数を使用します。Choose は、 の長さがi以上である場合に限り、クラスターAを選択します。この操作をサポートするには、 Iの長さを維持する必要があります。 ${\displaystyle v\in \partial {A}}$ ${\displaystyle \pi ({\mathcal {A}})}$

同様のタスクは、単位長ではない辺を持つグラフに対しても定式化できます。その場合、距離は2つの辺の間の1つの辺、または1つの頂点を指すことができます。後者の場合、頂点につながる辺を返すようにChooseを定義できます。パスに沿ったすべての辺の長さを定数分増やす更新を定義できます。このようなシナリオでは、これらの更新はルートクラスター内でのみ一定時間で実行されます。遅延更新を子ノードに分散させるには、 Cleanが必要です。CleanはChooseを呼び出す前に呼び出す必要があります。この場合、Iの長さを維持するには、 Iでも単位長を維持する必要があります。

頂点vを含む木の中心を見つけるには、双中心辺、または中心を一方の端点とする辺のいずれかを見つける必要があります。辺は、C =Expose({v})に続いて適切なChooseを用いてSearch( C )を実行することで見つけることができます。 Choose は、子AとBのうち、 maxdistance( a ) がより高い子を選択します。この操作をサポートするには、クラスターサブツリー内の境界頂点からの最大距離をIで維持する必要があります。そのためには、クラスターパスの長さも維持する必要があります。 ${\displaystyle a\in \partial {A}\cap \partial {B}}$

興味深い結果と応用

元々他の方法で実装されていた多くの興味深いアプリケーションが、トップツリーのインターフェースを使用することで簡単に実装できるようになりました。その一部を以下に示します。

• [SLEATOR AND TARJAN 1983] リンクとカットごとに重み付きツリーの動的なコレクションを時間的に維持することができ、任意の2つの頂点間の最大辺重みに関するクエリを時間的にサポートします。 ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle O(\log n)}$
  • 証明の概要：各ノードにおいて、そのクラスターパス上の最大重み（⁠ ⁠${\displaystyle {\max}_{wt}}$ ）を維持することを含み、それが点クラスターである場合は、次のように初期化される。クラスターが2つのクラスターの和集合である場合、それは2つの結合されたクラスターの最大値である。vとwの間の最大重みを見つける必要がある場合は、次のようにして報告する。${\displaystyle {\max}_{wt}({\mathcal {C}})}$ ${\displaystyle -\infty.}$ ${\displaystyle {\mathcal {C}}=\mathrm {Expose} (v,w),}$ ${\displaystyle {\max}_{wt}({\mathcal {C}}).}$
• [SLEATOR AND TARJAN 1983] 上記のアプリケーションのシナリオでは、与えられたパスv · · · w上のすべてのエッジに共通の重みxを時間的に追加することもできます。 ${\displaystyle {\mathcal {O}}(\log n)}$
  • 証明の概要：内のすべての辺に追加されるextra( C )という重みを導入します。これは適切に維持されます。 split( C ) では、 Cの各パスの子Aに対して、および を設定する必要があります。C  := join( A , B ) の場合、および を設定します。最後に、パスv · · · wの最大重みを見つけるために、 を設定し、 を返します。${\displaystyle \pi ({\mathcal {C}}).}$ ${\displaystyle {\max}_{wt}(A):={\max}_{wt}({\mathcal {A}})+\mathrm {extra} ({\mathcal {C}})}$ ${\displaystyle \mathrm {extra} ({\mathcal {A}}):=\mathrm {extra} ({\mathcal {A}})+\mathrm {extra} ({\mathcal {C}})}$ ${\displaystyle {\max}_{wt}({\mathcal{C}}):=\max\{{\max}_{wt}({\mathcal{A}}),{\max}_{wt}({\mathcal{B}})\}}$ ${\displaystyle \mathrm {extra} ({\mathcal {C}}):=0}$ ${\displaystyle {\mathcal {C}}:=\mathrm {Expose} (v,w)}$ ${\displaystyle {\max}_{wt}({\mathcal {C}})}$
• [GOLDBERG ET AL. 1991] 与えられた頂点vを含む基礎木における最大重みを時間 内に求めることができる。${\displaystyle {\mathcal {O}}(\log n)}$
  • 証明の概要: これには、マージ操作と分割操作中のクラスター内の最大重みの非クラスター パス エッジに関する追加情報を維持する必要があります。
• 2つの頂点vとwの間の距離は、時間的に次のように求められます。 ${\displaystyle {\mathcal {O}}(\log n)}$ ${\displaystyle \mathrm {長さ} (\mathrm {露出} (v,w))}$
  • 証明の概要：クラスタパスの長さ length( C ) を維持します。長さは最大重みとして維持されますが、 Cが join(Merge) によって作成された場合、length( C ) はそのパスの子に格納されている長さの合計となります。
• 木の直径とその後のメンテナンスに関する問い合わせには時間がかかります。${\displaystyle {\mathcal {O}}(\log n)}$
• 中心と中央値は、Link(Merge) および Cut(Split) 操作で維持され、時間内に非ローカル検索によって照会されます。${\displaystyle {\mathcal {O}}(\log n)}$

• トップツリーは、動的2辺連結性のための最先端のアルゴリズムで使用されています。この問題では、動的連結性と同様に、グラフは辺の削除と挿入、および頂点のペアが2辺連結されているか、またはそれらを隔てるブリッジがあるかを尋ねるクエリの対象となります。Holm、de Lichtenberg、およびThorup ^[1]は、償却更新時間、およびクエリ時間を伴う決定論的アルゴリズムを提示しています。Holm、de Lichtenberg、およびThorupによるその後の研究では、トップツリー^{[2] [3]}を使用することで、償却更新時間が に改善されました。${\displaystyle O(\log^{4}n)}$ ${\displaystyle O(\log n/\log \log n)}$ ${\displaystyle O(\log ^{2}n\log ^{2}\log n)}$

• グラフは、辺集合を更新し、頂点2連結性に関するクエリを実行できるように維持できる。更新の償却複雑度は である。クエリはさらに高速に実装できる。このアルゴリズムは単純ではなく、空間を消費する。^[4]${\displaystyle O(\log^{5}n)}$ ${\displaystyle I({\mathcal {C}})}$ ${\displaystyle \Theta (\log^{2}n)}$

• トップツリーは、 DAG圧縮より決して劣ることはありませんが、指数関数的に優れた方法でツリーを圧縮するために使用できます。^[5]

実装

トップツリーは様々な方法で実装されており、その中には、マルチレベルパーティションを用いた実装（トップツリーと動的グラフアルゴリズム、Jacob HolmとKristian de Lichtenberg。技術レポート）、さらにはSleator-Tarjan stツリー（通常は償却時間制限付き）、Fredericksonのトポロジツリー（最悪ケースの時間制限付き）（Alstrupら、トップツリーを用いた完全に動的ツリーの情報維持）などが あります

償却実装はより単純で、時間計算量の乗算係数も小さくなります。一方、最悪のケースでは、クエリ実行中に不要な情報更新を停止することでクエリを高速化できます（永続化技術によって実装）。クエリへの回答後、最上位ツリーの元の状態が使用され、クエリバージョンは破棄されます。

マルチレベルパーティションの使用

木Tのクラスターの任意の分割は、木T内の各クラスターを辺に置き換えることで、クラスター分割木（CPT）で表すことができます。Tを分割するための戦略Pを用いると、CPTはCPT _Pとなります。これは、辺が1つだけ残るまで再帰的に実行されます。 ${\displaystyle ({\mathcal {T}}),}$ ${\displaystyle {\mathcal {T}}.}$

対応するトップツリーのすべてのノードが、このマルチレベルパーティションのエッジに一意にマッピングされていることがわかります。マルチレベルパーティションには、トップツリーのどのノードにも対応しないエッジが存在する場合があります。これらは、その下のレベルの単一の子、つまり単純なクラスターのみを表すエッジです。複合クラスターに対応するエッジのみが、トップツリーのノードに対応します。${\displaystyle \Re}$ ${\displaystyle \Re.}$

ツリーTをクラスターに分割する際には、分割戦略が重要です。慎重な戦略を講じることでのみ、最終的に高さのあるマルチレベル分割（つまり最上位ツリー）を実現できます。 ${\displaystyle {\mathcal {O}}(\log n)}$

• 後続のレベルのエッジの数は、一定の係数で減少するはずです。
• 下位レベルが更新によって変更された場合、最大で一定数の挿入と削除を使用して、そのすぐ上のレベルを更新できるはずです。

上記のパーティショニング戦略により、最上位ツリーが 時間どおりに維持されることが保証されます。 ${\displaystyle {\mathcal {O}}(\log n)}$

参照

• リンク/カット木
• オイラーツアー木
• 動的アルゴリズム
• 動的接続性

参考文献

• Stephen Alstrup、Jacob Holm、Kristian De Lichtenberg、Mikkel Thorup、「トップツリーによる完全に動的なツリーの情報維持」、ACM Transactions on Algorithms (TALG)、Vol. 1 (2005)、243–264、doi :10.1145/1103963.1103966
• Stephen Alstrup、Jacob Holm、Kristian De Lichtenberg、Mikkel Thorup、「連結性、最小全域木、2辺、双連結性のための多対数決定論的完全動的アルゴリズム」、Journal of the ACM、Vol. 48 Issue 4（2001年7月）、723–760、doi :10.1145/502090.502095
• ドナルド・クヌース著『コンピュータプログラミングの技法：基礎アルゴリズム』第3版、アディソン・ウェズレー、1997年、ISBN 0-201-89683-4セクション2.3：木、308～423ページ
• トーマス・H・コーメン、チャールズ・E・ライザーソン、ロナルド・L・リベスト、クリフォード・スタイン著。アルゴリズム入門第2版。MITプレスおよびマグロウヒル、2001年。ISBN 0-262-03293-7セクション10.4：根付き木の表現、214～217ページ。第12章～14章（二分探索木、赤黒木、データ構造の拡張）、253～320ページ

1. Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). 「連結性、最小全域木、2辺、および双連結性のための多対数決定論的完全動的アルゴリズム」Journal of the ACM . 48 (4): 723. doi :10.1145/502090.502095. S2CID  7273552.
2. Thorup, Mikkel (2000)、「準最適完全動的グラフ接続性」、第32回ACM計算理論シンポジウム議事録
3. Holm, Jacob; Rotenberg, Eva; Thorup, Mikkel (2018)、「償却時間内での動的ブリッジ検出」、第29回離散アルゴリズムシンポジウム論文集、SODA 2018、doi : 10.1137/1.9781611975031.3、S2CID  33964042${\displaystyle {\tilde {O}}(\log ^{2}n)}$
4. Holm, J.; De Lichtenberg, K.; Thorup, M. (2001). 「連結性、最小全域木、2辺、および双連結性のための多対数決定論的完全動的アルゴリズム」Journal of the ACM . 48 (4): 723. doi :10.1145/502090.502095. S2CID  7273552.
5. Bille, Philip; Gørtz, Inge Li; Landau, Gad M.; Weimann, Oren (2015). 「トップツリーによるツリー圧縮」. Inf. Comput . 243 : 166–177 . arXiv : 1304.5702 . doi :10.1016/j.ic.2014.12.012.

外部リンク

• トップツリーを用いた完全に動的なツリーにおける情報の維持。Alstrup他
• 自己調整型トップツリー。Tarjan and Werneck, Proc. 16th SoDA, 2005