タンゴの木

タンゴツリーは、 2004年にErik D. Demaine、Dion Harmon、John Iacono、Mihai Pătrașcuによって提案された二分探索木の一種です。^[1]タンゴが象徴的なブエノスアイレスにちなんで名付けられました。

これは、オフラインの最適二分探索木と比較して、ノードあたりの追加メモリ ビットのみを使用して の競争率 を達成するオンライン二分探索木です。これは、 であった以前の最も優れた競争率 よりも改善されました。 ${\displaystyle O(\log \log n)}$ ${\displaystyle O(\log \log n)}$${\displaystyle O(\log n)}$

Tango ツリーは、バイナリ検索ツリーを一連の優先パスに分割することによって機能します。優先パス自体は補助ツリーに格納されます (そのため、Tango ツリーはツリーのツリーとして表されます)。

タンゴ ツリーを構築するには、参照ツリーと呼ばれる完全な二分探索ツリーをシミュレートします。これは、すべての要素を含む従来の二分探索ツリーにすぎません。このツリーは実際の実装には現れませんが、タンゴ ツリーの次の部分の概念的な基礎となります。

特に、参照ツリーの高さは ⌈log ₂ ( n +1)⌉ です。これは最長パスの長さに等しく、したがって最大の補助ツリーのサイズに等しくなります。補助ツリーを適度にバランスよく保つことで、補助ツリーの高さをO (log log n )に制限できます。 これがアルゴリズムのパフォーマンス保証の源です。

まず、各ノードの優先子を定義します。これは、非公式には、従来の二分探索木検索によって最後にアクセスされた子です。より正式には、pをルートとし、子l (左) とr (右) を持つサブツリー Tを考えます。Tで最後にアクセスされたノードがr をルートとするサブツリー内にある場合はr をpの優先子として設定し、それ以外の場合はl を優先子として設定します。 Tで最後にアクセスされたノードがp自体である場合、定義によりl が優先子となること に注意してください。

優先パスは、ルートから開始し、優先される子ノードをたどってリーフ ノードに到達するまで定義されます。このパス上のノードを削除すると、ツリーの残りの部分が複数のサブツリーに分割され、各サブツリーを再帰的に処理します (ルートからの優先パスが形成され、サブツリーがさらに多くのサブツリーに分割されます)。

優先パスを表すために、そのノードをバランスのとれた二分探索木、具体的には赤黒木に格納します。優先パスP内の各非リーフノードnには、新しい補助木のルートとなる非優先の子cがあります。この別の補助木のルート ( c ) をP内のnに接続して、補助木を互いにリンクします。また、各ノードに、そのノードの下のサブツリー内のノードの最小および最大の深さ (つまり、参照ツリー内の深さ) を格納することで、補助木を拡張します。

タンゴ ツリー内の要素を検索するには、参照ツリーの検索をシミュレートするだけです。ルートに接続された優先パスの検索から開始します。これは、その優先パスに対応する補助ツリーの検索によってシミュレートされます。補助ツリーに目的の要素が含まれていない場合、検索は目的の要素を含むサブツリーのルートの親 (別の優先パスの始まり) で終了するため、補助ツリーでその優先パスを検索して続行します。

タンゴ ツリーの構造 (補助ツリーは優先パスに対応) を維持するために、検索の結果として優先子が変わるたびに更新作業を行う必要があります。優先子が変わると、優先パスの上部が下部から切り離され (下部は独自の優先パスになります)、別の優先パスに再接続されます (新しい下部になります)。これを効率的に行うために、補助ツリーでカット操作と結合操作を定義します。

join操作では、一方の最上位ノード (参照ツリー内) がもう一方の最下位ノードの子であるという特性 (基本的に、対応する優先パスを連結できる) を持つ 2 つの補助ツリーを結合します。これは、一方のツリーのすべての要素がもう一方のツリーのすべての要素より小さいという特性を持つ 2 つのツリーを結合する赤黒ツリーの連結操作と、その逆を行うsplit操作に基づいて機能します。参照ツリーでは、最上位パスに 2 つのノードが存在し、そのキー値がそれらのノードの間にある場合にのみ、ノードが最下位パスに存在することに注意してください。ここで、最下位パスを最上位パスに結合するには、最上位パスをそれらの 2 つのノードの間で分割し、結果として得られる 2 つの補助ツリーを最下位パスの補助ツリーの両側に連結します。これで、結合された最終的な補助ツリーが得られます。

cut操作は、優先パスを特定のノードで上部と下部の 2 つの部分に分割します。より正式には、補助ツリーを 2 つの補助ツリーに分割し、1 つには参照ツリーの特定の深さ以上のすべてのノードが含まれ、もう 1 つにはその深さ以下のすべてのノードが含まれます。joinと同様に、上部には下部を囲む 2 つのノードがあることに注意してください。したがって、これらの 2 つのノードのそれぞれでsplit してパスを 3 つの部分に分割し、外側の 2 つのノードを連結して、必要に応じて上部と下部の 2 つの部分を作成できます。

Tango ツリーの競争比率を制限するには、ベンチマークとして使用する最適なオフライン ツリーのパフォーマンスの下限を見つける必要があります。Tango ツリーのパフォーマンスの上限がわかったら、それらを分割して競争比率を制限することができます。

最適なオフライン二分探索木によって行われる作業の下限を見つけるために、ここでも優先子の概念を使用します。アクセスシーケンス（検索のシーケンス）を考慮すると、参照ツリーノードの優先子が何回切り替わるかを追跡します。スイッチの合計数（すべてのノードの合計）は、特定のアクセスシーケンスで任意の二分探索木アルゴリズムによって行われる作業の漸近的な下限を与えます。これはインターリーブ下限と呼ばれます。^[1]

これをタンゴ ツリーに関連付けるには、特定のアクセス シーケンスに対してタンゴ ツリーによって実行される作業の上限を見つけます。上限は となり、ここでkはインターリーブの数です。 ${\displaystyle (k+1)O(\log \log n)}$

総コストは、要素の検索と、適切な不変量を維持するためのタンゴ ツリーの構造の更新 (優先される子の切り替えと優先パスの再配置) の 2 つの部分に分かれています。

検索（更新ではない）がこの境界内に収まることを確認するには、補助ツリー検索が失敗して次の補助ツリーに移動する必要があるたびに、優先される子の切り替えが発生することに注目するだけです（親の優先パスが方向を変えて子の優先パスに結合するため）。補助ツリー検索は最後の検索を除いてすべて失敗するため（当然、検索が成功すると停止します）、補助ツリーを検索します。各検索には かかります。補助ツリーのサイズは参照ツリーの高さ によって制限されるためです。${\displaystyle k+1}$${\displaystyle O(\log \log n)}$${\displaystyle \log n}$

更新コストもこの範囲内に収まります。これは、訪問した補助ツリーごとに1 回のカットと 1 回の結合を実行するだけでよいためです。1 回のカットまたは結合操作には、定数回の検索、分割、および連結のみが必要であり、それぞれに補助ツリーのサイズの対数時間がかかるため、更新コストは です。 ${\displaystyle (k+1)O(\log \log n)}$

タンゴ ツリーは-競合的です。最適なオフライン バイナリ検索ツリーによって行われる作業は、少なくともk (優先される子スイッチの合計数) に線形であり、タンゴ ツリーによって行われる作業は最大で であるためです。 ${\displaystyle O(\log \log n)}$${\displaystyle (k+1)O(\log \log n)}$

• スプレイツリー
• 最適二分探索木
• 赤黒木
• ツリー（データ構造）