木の回転
木の回転（きのかいてん、英: tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。
なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある（前者の逆になる）。本項ではノードがずれる方向を回転の方向とする。
概要
編集
上の図にある右回転 (Right Rotation) 操作は、根ノードが Q の木構造に対して行う。すると、木構造が時計回りの方向に回転することになる。対称的操作は左回転 (Left Rotation) であり、反時計回りに木構造を回転させる（上の図では根ノードが P の木構造に対して行う）。
先述したとおり2分探索木を対象としているので、ノードにある要素はアルファベット文字ではなく変数を表していると解釈されたい。
詳細
編集木を回転させるとき、回転方向の部分木は高さが増え、反対方向の部分木は高さが減る。これを利用して木の平衡をとることができる。
回転させる（部分）木の根ノードを Root とし、新たな根ノードとなるノードを Pivot とする。各ノードの回転する方向の子ノードを指しているフィールドを RS、反対方向の子ノードを指しているフィールドを OS とする。たとえば、上の図の根ノード Q の RS は C、OS は P である。回転の擬似コードは次のようになる。
Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot
したがって、木の回転は定数時間の処理である。回転させたのが部分木なら、その親ノードが新たな根ノードを指すようにしなければならない。
順序不変性
編集木の回転において、2分木の間順 (inorder) の走査は不変である。つまり、木の回転によって木のどの部分についても要素の順序に影響を与えない。上の木の場合、間順の走査は次のようになる。
左の木: ((A, P, B), Q, C) 右の木: (A, P, (B, Q, C))
一方からもう一方を計算するのは非常に簡単である。以下に Python で書いたその計算を行うコードを示す。
def right_rotation(treenode): (A, P, B), Q, C = treenode return A, P, (B, Q, C)
ノード P が根ノードのときの左回転は次の通り。
Q が P の右の子ノードだとする。 Q が新たな根ノードになる。 Q の左の子ノードを P の右の子ノードとする。 P を Q の左の子ノードとする。
ノード Q が根ノードのときの右回転は次の通り。
P が Q の左の子ノードだとする。 P が新たな根ノードになる。 P の右の子ノードを Q の左の子ノードとする。 Q を P の右の子ノードとする。
他のノードのつながりは全てそのままでよい。
二重回転 (double rotations) という操作も右と左が存在する。二重左回転をXというノードで行う場合、まずXの右のノードを根とする部分木について右回転を行い、次いでXについて左回転を行う。同様に二重右回転はXの左の子ノードを根とする部分木について左回転を行い、次いでXについて右回転を行う。
木の回転は、AVL木、赤黒木、スプレー木、treapといった様々な木構造のデータ構造で使われている。これは局所的な変形であるため、定数時間しか要しない。すなわち、回転の最中にさわるのは5個のノードだけで、木構造の他の部分は無関係である。
平衡をとるための回転
編集
木の回転によって平衡をとることができる。そのような平衡をとる技法を採用している木としてAVL木がある。回転によって平衡がとれるのは、回転後に回転方向の部分木の高さ（深さ）が1大きくなり、反対方向の部分木の高さが1小さくなるためである。これにより、全体が平衡となるよう高さを調整できる。
回転距離
編集同じノード数の2つの2分木があるとき、回転距離 (rotation distance) とは、一方からもう一方へと変形するのにかかる回転の回数である。この距離に着目すると、nノードの2分木の集合は一種の距離空間を形成する。この距離は対称的で常に正であり、三角不等式が成り立つ。
回転距離を求める多項式時間のアルゴリズムが存在するかどうかは分かっていない。しかし、ダニエル・スレイター、ロバート・タージャン、ウィリアム・サーストンの3人は、任意の2つのnノードの木（n ≥ 11 の場合）の回転距離が最大で 2n − 6 であり、この距離の木の組合せが無数に存在することを示した[1]。
関連項目
編集脚注
編集- ^ Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), “Rotation distance, triangulations, and hyperbolic geometry”, Journal of the American Mathematical Society 1 (3): 647–681, doi:10.2307/1990951, MR928904.
外部リンク
編集- 木の回転をアニメーション表示するJavaアプレット
- 木の回転をデモンストレーションするJavaアプレット
- The AVL Tree Rotations Tutorial (RTF) by John Hargrove