木の回転

木の回転（きのかいてん、tree rotation）は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある（前者の逆になる）。本項ではノードがずれる方向を回転の方向とする。