木の回転

離散数学において、ツリー回転とは、要素の順序を妨げずに構造を変更するバイナリ ツリーの操作です。ツリー回転では、ツリー内の 1 つのノードが上に移動し、1 つのノードが下に移動します。ツリーの形状を変更するために使用され、特に、小さいサブツリーを下に移動し、大きいサブツリーを上に移動することでツリーの高さを低くすることで、多くのツリー操作のパフォーマンスが向上します。

回転の方向の定義については、さまざまな説明で矛盾が存在します。回転の方向は、回転時にノードが移動する方向を反映している (左の子が親の場所に回転する場合は右回転) という説明もあれば、回転の方向はどのサブツリーが回転しているかを反映している (左のサブツリーが親の場所に回転する場合は左回転で、前者の逆) という説明もあります。この記事では、回転するノードの方向移動のアプローチを取り上げます。

隣の画像に示されている右回転操作は、Q をルートとして実行されるため、 Q 上の、つまりQ をルートとする右回転です。この操作により、ツリーは時計回りに回転します。逆の操作は左回転で、反時計回りに移動します (上記の左回転はPをルートとしています)。回転の機能を理解する鍵は、その制約を理解することです。特に、ツリーのリーフの順序 (たとえば、左から右に読む場合) は変更できません (別の考え方としては、リーフが順序どおりに走査される順序は、操作後も操作前と同じである必要があります)。もう 1 つの制約は、バイナリ検索ツリーの主な特性、つまり、右サブツリーのすべてのノードが親よりも大きく、左サブツリーのすべてのノードが親よりも小さいことです。サブツリーのルートの左の子の右の子(たとえば、Q をルートとするツリーの図のノード B) は、ルートの左の子になることができ、それ自体が回転したサブツリーの「新しい」ルートの右の子になり、どちらの制約にも違反しないことに注意してください。図に示されているように、葉の順序は変わりません。逆の操作でも順序は保持され、2 番目の種類の回転になります。

これがバイナリ検索ツリーであると仮定すると、前述のように、要素は互いに比較できる変数として解釈される必要があります。左側のアルファベット文字は、これらの変数のプレースホルダーとして使用されます。右側のアニメーションでは、大文字のアルファベット文字が変数のプレースホルダーとして使用され、小文字のギリシャ文字は変数セット全体のプレースホルダーとして使用されます。円は個々のノードを表し、三角形はサブツリーを表します。各サブツリーは空の場合もあれば、1 つのノードで構成される場合もあれば、任意の数のノードで構成される場合もあります。

サブツリーを回転すると、回転する側のサブツリーの高さが 1 ノード分増加し、もう一方のサブツリーの高さが減少します。このため、ツリーの回転はツリーのバランス調整に役立ちます。

回転するサブツリーの親ノードを表すRoot 、新しい親ノードになるノードを表すPivot 、回転する側を表すRS 、回転の反対側を表すOSという用語について考えてみましょう。上の図のルート Q の場合、 RSは C、OS はP です。これらの用語を使用すると、回転の擬似コードは次のようになります。

Pivot = Root.OS とします。
ルート.OS = ピボット.RS
Pivot.RS = ルート
ルート = ピボット

これは一定時間の操作です。

プログラマーは、回転後にルートの親がピボットを指していることを確認する必要があります。また、この操作によってツリー全体のルートが新しくなる可能性があることに注意し、それに応じてポインターを更新するように注意する必要があります。

ツリーの回転により、バイナリ ツリーのinorder トラバーサルが不変になります。つまり、ツリーのどの部分で回転を実行しても、要素の順序は影響を受けません。上に示したツリーの inorder トラバーサルは次のとおりです。

左のツリー: ((A, P, B), Q, C) 右のツリー: (A, P, (B, Q, C))

一方から他方を計算するのは非常に簡単です。以下はその計算を実行するPythonコードの例です。

def  right_rotation ( treenode ): 
"""指定されたツリーを右に回転します。""" left , Q , C = treenode A , P , B = left return ( A , P , ( B , Q , C ))    
        
        
         

別の見方をすると次のようになります。

ノードQの右回転:

PをQの左の子とします。
Q の左の子を P の右の子に設定します。
[Pの右の子の親をQに設定する]
P の右の子を Q に設定します。
[Qの親をPに設定]

ノードPの左回転:

QをPの右の子とします。
P の右の子を Q の左の子に設定します。
[Qの左の子の親をPに設定する]
Q の左の子を P に設定します。
[Pの親をQに設定]

その他の接続はすべてそのまま残されます。

左回転と右回転を組み合わせた二重回転もあります。X での二重左回転は、X の右の子での右回転の後に X での左回転が続くものとして定義できます。同様に、 X での二重右回転は、X の左の子での左回転の後に X での右回転が続くものとして定義できます。

ツリー回転は、 AVL ツリー、赤黒ツリー、WAVL ツリー、スプレイ ツリー、トリップなどの多くのツリーデータ構造で使用されます。これらはローカル変換であるため、一定の時間しかかかりません。つまり、5 つのノードのみで動作し、ツリーの残りの部分を調べる必要はありません。

回転を使用してツリーのバランスを再調整できます。回転後、回転側の高さは 1 増加し、回転の反対側の高さは同様に減少します。したがって、左の子と右の子の高さが 1 以上異なるノードに戦略的に回転を適用できます。自己バランス型バイナリ サーチ ツリーは、この操作を自動的に適用します。このバランス調整手法を使用するツリーの種類は、AVL ツリーです。

同じ数のノードを持つ 2 つのバイナリ ツリー間の回転距離は、一方を他方に変換するために必要な最小の回転数です。この距離により、nノードのバイナリ ツリーの集合は距離空間になります。距離は対称で、2 つの異なるツリーが与えられた場合は正であり、三角不等式を満たします。

回転距離を計算するための多項式時間アルゴリズムが存在するかどうかは未解決の問題であるが、回転距離問題のいくつかの変種では多項式時間アルゴリズムが認められている。^{[1] [2] [3]}

ダニエル・スレイター、ロバート・タージャン、ウィリアム・サーストンは、任意の2つのnノードツリー（n ≥ 11）間の回転距離は最大でも2 n − 6であり、 nが十分に大きくなる とすぐにいくつかのツリーペアがこの距離だけ離れることを示した。^[4]ライオネル・ポーニンは、実際にn ≥ 11のときはいつでもそのようなペアが存在することを示した^。[5]

• AVL ツリー、赤黒ツリー、およびスプレー ツリーは、回転を使用してバランスを維持するバイナリ検索ツリーデータ構造の一種です。
• バイナリ演算の結合性とは、バイナリ演算に対してツリーの回転を実行しても最終結果が変わらないことを意味します。
• Day -Stout-Warren アルゴリズムは、不均衡な BST を均衡化します。
• タマリ格子は、要素を二分木として定義でき、要素間の順序が木の回転によって定義される、部分的に順序付けられた集合です。

• AVL ツリー回転チュートリアル (RTF) (John Hargrove 著)