順序不変性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 07:14 UTC 版)
木の回転において、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個のノードだけで、木構造の他の部分は無関係である。
※この「順序不変性」の解説は、「木の回転」の解説の一部です。
「順序不変性」を含む「木の回転」の記事については、「木の回転」の概要を参照ください。
- 順序不変性のページへのリンク
