離散数学および理論計算機科学において、同じノード数を持つ2つの二分木間の回転距離とは、一方の木を別の木に再構成するために必要な最小の回転回数である。二分木と凸多角形の三角形分割の間には組み合わせ論的同値性があるため、回転距離は凸多角形の三角形分割における反転距離と等価である。
回転距離は、 1982年にカレル・チュリク2世とデリック・ウッドによって初めて定義されました。[1] nノードを持つ2つの二分木の回転距離は、 n ≥ 11のいずれの場合も最大で2 n − 6であり、この回転距離を持つ木の組み合わせもあります。回転距離を計算するための計算量は未知数です。[2]
意味
二分木は、ノードの集合から構成される構造であり、そのうちの 1 つがルートノードとして指定され、残りの各ノードは他のノード（その親）の左の子または右の子のいずれかであり、どのノードからでも親リンクをたどると最終的にルートノードに到達します。（一部の資料では、ここで説明するノードは「内部ノード」と呼ばれ、「外部ノード」と呼ばれる別のノード集合も存在します。各内部ノードは正確に 2 個の子を持つ必要があり、各外部ノードは 0 個の子を持つ必要があります。[1]ここで説明するバージョンは、このようなツリーからすべての外部ノードを削除することによって取得できます。）
木内の任意のノードxに対して、 xをルートとし、親リンクを辿ってxに到達できるすべてのノードからなる、同じ形式の部分木が存在する。各二分木には、そのノードの左から右への順序、すなわちそのインオーダー・トラバーサル（inorder traversal）が存在する。これは、左部分木（ルートの左の子が存在する場合はその子のサブツリー）を再帰的にトラバースし、次にルート自体をリストし、次に右部分木を再帰的にトラバースすることで得られる。二分探索木では、各ノードは検索キーに関連付けられており、左から右への順序はキーの順序と一致している必要がある。[2]
木の回転は、二分木の左から右への順序を変えずにその構造を変える操作である。いくつかの自己バランス型二分探索木 データ構造は、再バランス化アルゴリズムの基本操作としてこの回転を使用する。回転は 2 つのノードxとy （ 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]この回転グラフは、まさに連想面体（associahedron）の頂点と辺のグラフです。[3]
フリップ距離と同等
ある幾何学的オブジェクトの三角形分割の族が与えられたとき、フリップとは、2 つの三角形間の辺を削除し、結果として得られる四辺形に反対の対角線を追加することによって、1 つの三角形分割を別の三角形分割に変換する操作です。2 つの三角形分割間のフリップ距離とは、1 つの三角形分割を別の三角形分割に変換するのに必要な最小のフリップ回数です。これは、フリップ グラフ(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であることを示した。彼らはここでも、凸多角形の三角形分割の反転という観点から問題の解釈を用い、開始および終了の三角形分割を凸多面体の上面と底面として解釈し、凸多角形自体はこの多面体のハミルトン閉路として解釈した。この解釈によれば、1 つの三角形分割から別の三角形分割への反転のシーケンスは、与えられた 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つの子がリーフであるような回転のみを許可し、もう1つは右腕ノード（ルートから右端のリーフへのパス上にあるノード）のみの回転を許可します。どちらの変種もmeet semi-latticeを生成し、その構造を利用してアルゴリズムを導出します。[9] [10]
参考文献
- ^ abc Čulík, Karel II; Wood, Derick (1982)、「いくつかのツリー類似度測定に関する注記」、Information Processing Letters、15 (1): 39– 42、doi :10.1016/0020-0190(82)90083-7、MR 0678031
- ^ abcdef スリーター、ダニエル・D. ;タージャン、ロバート・E. ;サーストン、ウィリアム・P. (1988)、「回転距離、三角測量、双曲幾何学」、アメリカ数学会誌、1 (3): 647– 681、doi : 10.1090/S0894-0347-1988-0928904-4、JSTOR 1990951、MR 0928904
- ^ ab Pournin, Lionel (2014)、「連想面体の直径」、Advances in Mathematics、259 : 13– 42、arXiv : 1207.6296、doi : 10.1016/j.aim.2014.02.035、MR 3197650
- ^ Cleary, Sean; St. John, Katherine (2010)、「回転距離の線形時間近似」、Journal of Graph Algorithms and Applications、14 (2): 385– 390、arXiv : 0903.0199、doi : 10.7155/jgaa.00212、MR 2740180
- ^ Cleary, Sean; St. John, Katherine (2009)、「回転距離は固定パラメータで制御可能」、Information Processing Letters、109 (16): 918– 922、arXiv : 0903.0197、doi :10.1016/j.ipl.2009.04.023、MR 2541971、S2CID 125834
- ^ Lucas, Joan M. (2010)、「二分木の回転距離のための改良カーネルサイズ」、Information Processing Letters、110 ( 12– 13): 481– 484、doi :10.1016/j.ipl.2010.04.022、MR 2667389
- ^ Li, Haohong; Xia, Ge (2023-11-05)、「凸型フリップ距離のための𝒪(3.82^k)時間FPTアルゴリズム」、Discrete & Computational Geometry、Springer Science and Business Media LLC: 44:1–44:14、doi :10.1007/s00454-023-00596-9、ISSN 0179-5376
- ^ フォーダム、ブレイク（2003）、「トンプソン群Fの最小長要素」、Geometriae Dedicata、99（1）、Springer Science and Business Media LLC：179-220、doi：10.1023/a：1024971818319、ISSN 0046-5755
- ^ ボニン, アンドレ; パロ, ジャン=マルセル (1992), 「ラベルなし二分木における最短経路メトリック」,パターン認識レターズ, 13 (6), Elsevier BV: 411– 415, Bibcode :1992PaReL..13..411B, doi :10.1016/0167-8655(92)90047-4, ISSN 0167-8655
- ^ Pallo, Jean Marcel (2003)、「二分木間の右腕回転距離」、Information Processing Letters、87 (4)、Elsevier BV: 173– 177、doi :10.1016/s0020-0190(03)00283-7、ISSN 0020-0190
