Loading article…
離散数学および理論計算機科学において、ノード数が同じ2つの二分木間の回転距離とは、一方の木をもう一方の木に再構成するために必要な最小の木回転回数のことである。二分木と凸多角形の三角形分割の間には組み合わせ論的な等価性があるため、回転距離は凸多角形の三角形分割における反転距離と等価である。
回転距離は、 1982 年にKarel Čulík II とDerick Woodによって初めて定義されました。[ 1 ]すべてのn ≥ 11に対して、任意の2 つのnノード二分木の回転距離は最大で2n − 6であり、いくつかの木のペアはまさにこの距離になります。回転距離を計算する計算複雑度は不明です。[ 2 ]
二分木は、ノードの集合からなる構造であり、そのうちの1つがルートノードとして指定され、残りの各ノードは、他のノード（親ノード）の左の子または右の子のいずれかであり、どのノードから親ノードへのリンクをたどっても最終的にルートノードにたどり着きます。（一部の資料では、ここで説明するノードは「内部ノード」と呼ばれ、別のノードの集合である「外部ノード」も存在します。各内部ノードは正確に2つの子を持ち、各外部ノードは子を持たなければなりません。[ 1 ]ここで説明するバージョンは、このような木からすべての外部ノードを削除することによって得られます。）
ツリー内の任意のノードxに対して、 xを根とし、親リンクをたどってxに到達できるすべてのノードからなる、同じ形式のサブツリーが存在します。各二分木には、左から右へのノードの順序、すなわち中順走査があり、これは左サブツリー（根の左の子のサブツリー、そのような子が存在する場合）を再帰的に走査し、次に根自体を列挙し、次に右サブツリーを再帰的に走査することによって得られます。二分探索木では、各ノードは検索キーに関連付けられており、左から右への順序はキーの順序と一致する必要があります。[ 2 ]
ツリー回転は、二分木の左から右への順序を変更せずに構造を変更する操作です。いくつかの自己平衡二分探索木データ構造は、再平衡化アルゴリズムの基本操作としてこれらの回転を使用します。回転は、x が y の親である 2 つのノード x と y に対して実行され、yをxの親にしてツリー内のxの場所に配置することでツリーを再構築します。yの子リンクの 1 つを解放してx をyの子としてリンクするスペースを作るために、この操作では、 yの子の 1 つをxの子に移動する必要がある場合もあります。この操作には 2 つのバリエーションがあります。右回転では、 y はxの左の子として始まり、xはyの右の子として終わります。左回転では、 yはxの右の子として始まり、x はyの左の子として終わります。[ 2 ]
左から右へのノードの順序が同じである任意の 2 つの木は、一連の回転によって互いに変換できます。2 つの木間の回転距離は、この変換を実行する最短の回転シーケンスの回転数です。これは、回転グラフにおける最短経路距離として記述することもできます。回転グラフとは、与えられた左から右へのノードの順序上の各二分木に対応する頂点と、2 つの木間の各回転に対応する辺を持つグラフです。[ 2 ]この回転グラフは、まさにアソシアヘドロンの頂点と辺のグラフです。[ 3 ]
ある幾何学的オブジェクトの三角形分割の族が与えられたとき、フリップとは、2 つの三角形間の辺を削除し、結果として得られる四角形に反対の対角線を追加することによって、ある三角形分割を別の三角形分割に変換する操作です。2 つの三角形分割間のフリップ距離は、ある三角形分割を別の三角形分割に変換するために必要な最小のフリップ回数です。これは、各三角形分割に対応する頂点と、2 つの三角形分割間の各フリップに対応する辺を持つグラフであるフリップグラフにおける最短経路距離として記述することもできます。フリップとフリップ距離は、ユークリッド平面上の点の集合の三角形分割、多角形の三角形分割、抽象多様体の三角形分割など、いくつかの異なる種類の三角形分割に対して、このように定義できます。
指定されたルート辺を持つ凸多角形の三角形分割と、n辺多角形の三角形分割をn − 2 個のノードを持つ二分木に変換する二分木の間には、1 対 1 の対応関係があります。この対応関係では、三角形分割の各三角形が二分木のノードに対応します。ルートノードは、指定されたルート辺を辺の 1 つとして持つ三角形であり、対応する三角形が三角形分割で対角線を共有する場合、2 つのノードは木の中で親と子としてリンクされます。この対応関係の下では、二分木の回転は、対応する三角形分割の反転と完全に一致します。したがって、( n − 2)個のノードを持つ木における回転距離は、 n辺凸多角形の三角形分割における反転距離と完全に一致します。
Čulík & Wood (1982)は、二分木の「右スパイン」を、根から始めて右子リンクをたどり、右子を持たないノードに到達するまでたどったパスと定義しています。木がすべてのノードが右スパインに属さないという性質を持つ場合、右スパインの長さを増やす右回転が必ず存在します。なぜなら、この場合、右スパイン上には、右スパイン上にない左子yを持つノードxが少なくとも 1 つ存在するからです。xとyに対して右回転を実行すると、 y が右スパインに追加され、他のノードは削除されません。右スパインの長さを繰り返し増やすことで、任意のnノード木を、すべてのノードが右スパインに属する同じノード順序を持つ唯一の木に、最大n − 1回のステップで変換できます。ノード順序が同じ任意の 2 つの木が与えられた場合、一方の木をすべてのノードが右側の脊柱にある木に変換し、次に 2 番目の木に対して同じ変換を逆に行うことで、最大で2 n − 2ステップで他方の木に変換できます。したがって、ČulíkとWood (1982)が証明したように、任意の 2 つの木間の回転距離は最大で2 n − 2です。[ 1 ]
木の回転ではなく凸多角形の反転という観点から問題を検討することで、Sleator、Tarjan 、 Thurston (1988) は回転距離が最大で2 n − 6であることを示すことができました。凸多角形の三角形分割の観点から、右スパインとはルートエッジの右端点に接続する三角形のシーケンスであり、すべての頂点がスパイン上にある木は、この頂点の扇形三角形分割に対応します。彼らの改良の主なアイデアは、ルートエッジの右端点の三角形分割だけでなく、任意の頂点の扇形三角形分割の両方を反転させることです。これらの選択肢すべてが同時に各開始三角形分割から最悪の場合の距離n − 1を与えることは不可能であり、改善をもたらします。[ 2 ]
Sleator、Tarjan、およびThurston (1988)も幾何学的議論を用いて、 nの値が無限に存在する場合、最大回転距離が正確に2 n − 6であることを示した。彼らは再び、凸多角形の三角形分割の反転という観点からこの問題を解釈し、開始三角形分割と終了三角形分割を凸多面体の上面と底面として解釈し、凸多角形自体をこの多面体内のハミルトン回路として解釈した。この解釈の下では、ある三角形分割から別の三角形分割への反転のシーケンスを、与えられた 3 次元多面体を三角形分割する四面体の集合に変換することができる。彼らは、(3 次元双曲幾何学において) 多面体は大きな体積を持つが、その内部のすべての四面体ははるかに小さな体積を持つという性質を持つ多面体の族を発見した。これは、どの三角形分割においても多くの四面体が必要であることを示唆している。これらの多面体の上面と下面のセットを木に再変換して得られる二分木は、少なくとも2 n − 6という高い回転距離を持つ。[ 2 ]
その後、Pournin (2014) は、すべてのn ≥ 11に対して、最大回転距離がちょうど2 n − 6であることを証明した。Pournin の証明は組み合わせ論的であり、双曲幾何学の使用を避けている。[ 3 ]
Čulík & Wood (1982)は回転距離を定義するだけでなく、与えられた 2 つの木の間の回転距離を計算する計算複雑性についても問いかけました。任意の 2 つの木の間に短い回転シーケンスが存在するということは、回転距離がk以下であるかどうかをテストすることが複雑性クラスNPに属することを意味しますが、 NP 完全であるとは知られておらず、多項式時間で解けることも知られていません。
2 つの木間の回転距離は、多角形の三角形分割の等価な観点では、一方の三角形分割から削除して別の対角線に置き換えてもう一方の三角形分割を生成する必要がある対角線の数によって下限が定められます。また、この問題を両方の三角形分割で共有される任意の対角線に沿って部分問題に分割し、各部分問題にČulík & Wood (1982)の方法を適用することで、この数の 2 倍で上限が定められます。この方法は、近似比が2 の問題に対する近似アルゴリズムを提供します。[ 4 ]共有対角線に沿って部分問題に分割するという同様のアプローチにより、回転距離を正確に計算するための固定パラメータの扱いやすいアルゴリズムが得られます。[ 5 ] [ 6 ]
パラメータ化なしで回転距離を正確に計算する複雑さを決定することは未解決のままであり、この問題に対して現在知られている最良のアルゴリズムは指数時間で実行されます。[ 7 ]
回転距離の計算の複雑さは不明であるが、回転距離を多項式時間で解くことができるいくつかの変種が存在する。
抽象代数学では、トンプソン群 Fの各要素は2 つの生成元を用いた表現を持ちます。このような表現の最小長を求めることは、ルートノードとその右の子のみを回転できる 2 つの二分木間の回転距離を求めることと同等です。フォーダムのアルゴリズムは、この制約の下で回転距離を線形時間で計算します。このアルゴリズムは、木のノードを 7 つのタイプに分類し、ルックアップ テーブルを使用して、あるタイプのノードを別のタイプのノードに変換するために必要な回転の数を求めます。すべての変換のコストの合計が回転距離です。[ 8 ]
さらに2つのバリアントがあり、1つは回転のピボットがルートの非葉子であり、ルートのもう一方の子が葉である場合のみ回転を許可し、もう1つは右腕ノード（ルートから最も右の葉までのパス上にあるノード）でのみ回転を許可します。どちらのバリアントもミート半格子を生成し、その構造を利用して、アルゴリズム。[ 9 ] [ 10 ]
