木の回転
上の図にある右回転 (Right Rotation) 操作は、根ノードが Q の木構造に対して行う。すると、木構造が時計回りの方向に回転することになる。対称的操作は左回転 (Left Rotation) であり、反時計回りに木構造を回転させる(上の図では根ノードが P の木構造に対して行う)。
先述したとおり2分探索木を対象としているので、ノードにある要素はアルファベット文字ではなく変数を表していると解釈されたい。