右回転とは、次のことを指します。
- 配列内のすべての項目を次の上位の位置に移動します。最後の項目は、空になった最初の位置に移動します。
- リストにおいて、末尾を削除して先頭に挿入します。
- マシン コード(およびアセンブリ言語)では、レジスタ内のすべてのビットを右に移動し、右端 (最下位ビット) が左端になります。
木の回転
二分探索木において、右回転とは、ノードXを右下に移動させることです。この回転は、Xに左子（またはサブツリー）があることを前提としています。Xの左子RはXの親ノードとなり、Rの右子はXの新しい左子になります。この回転は、ツリーのバランスをとるために行われます。具体的には、ノードXの左サブツリーの高さが（ツリーの種類によって異なりますが）右サブツリーの高さよりも大幅に高い場合に行われます。
右回転（および左回転）は二分探索木において順序保存性を持ちます。つまり、二分探索木の特性（木を順序通りに走査すると、ノードのキーが適切な順序で得られる）が保存されます。AVL木と赤黒木は、右回転を使用する二分探索木の例です。
単一の右回転はO(1)時間で実行されますが、二分探索木におけるノードの挿入と削除に統合されることがよくあります。この回転は、他の手法のコストと木の高さを最小限に抑えるために行われます。
参考文献
- Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein、2001年7月16日、『アルゴリズム入門』第2版、McGraw-Hill、ISBN 0-07-013151-1第13章。
