木の回転
木の回転において、2分木の間順 (inorder) の走査は不変である。つまり、木の回転によって木のどの部分についても要素の順序に影響を与えない。上の木の場合、間順の走査は次のようになる。
一方からもう一方を計算するのは非常に簡単である。以下に Python で書いたその計算を行うコードを示す。
ノード P が根ノードのときの左回転は次の通り。
ノード Q が根ノードのときの右回転は次の通り。
他のノードのつながりは全てそのままでよい。
二重回転 (double rotations) という操作も右と左が存在する。二重左回転をXというノードで行う場合、まずXの右のノードを根とする部分木について右回転を行い、次いでXについて左回転を行う。同様に二重右回転はXの左の子ノードを根とする部分木について左回転を行い、次いでXについて右回転を行う。
木の回転は、AVL木、赤黒木、スプレー木、treapといった様々な木構造のデータ構造で使われている。これは局所的な変形であるため、定数時間しか要しない。すなわち、回転の最中にさわるのは5個のノードだけで、木構造の他の部分は無関係である。