右回転

右回転とは、次のことを指します。

• 配列内のすべての項目を次の上位の位置に移動します。最後の項目は、空になった最初の位置に移動されます。
• リスト内で末尾を削除し、先頭に挿入します。
• マシン コード(およびアセンブリ言語)では、レジスタ内のすべてのビットを右に移動し、右端 (最下位ビット) が左端になります。

二分探索木では、右回転はノード 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 章。