左回転とは、次のことを指します
- 配列内のすべての項目を次の下位の位置に移動します。最初の項目は最後の位置に移動され、その位置は空になります。
- リストで先頭 を削除 し、末尾に 挿入 する こと。
- マシン コード(およびアセンブリ言語)では、レジスタ内のすべてのビットを左に移動し、左端 (最上位ビット) が右端になります。
木の回転
二分探索木において、左回転とは、ノード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章。
