JavaScriptで学ぶAVL木の回転操作｜LL・RR・LR・RL回転を図解＆コード付きで解説

AVL木は、ノードの挿入や削除によってバランスが崩れた際に、自己平衡性を保つために以下の4種類の回転（ローテーション）操作を実行します。

• 左回転（Left Rotation）
• 右回転（Right Rotation）
• 左右回転（Left-Right Rotation）
• 右左回転（Right-Left Rotation）

最初の2つは「単回転」、後の2つは「二重回転」に分類されます。木が不平衡となるためには、少なくとも高さ2の木が必要です。ここではシンプルな木を例に、それぞれの回転操作を順番に解説していきます。

左回転（Left Rotation）

あるノードの「右部分木のさらに右部分木」にノードを挿入した結果、木のバランスが崩れた場合には、単一の左回転を実行します。

この例では、ノードAの右部分木の右側にノードが挿入されたため、Aが不平衡ノードになっています。AをBの左部分木とすることで左回転を行います。この回転は「LL回転」とも呼ばれます。実装コードは以下の通りです。

function rotationLL(node) {
  let tmp = node.left;
  node.left = tmp.right;
  tmp.right = node;
  return tmp;
}

右回転（Right Rotation）

反対に、「左部分木のさらに左部分木」にノードが挿入されると、AVL木はバランスを崩します。この場合に必要となるのが右回転です。

図のとおり、右回転を行うことで、不平衡ノードはその左の子ノードの右側の子として配置し直されます。この回転は「RR回転」とも呼ばれます。コードでは次のように記述できます。

function rotationRR(node) {
  let tmp = node.right;
  node.right = tmp.left;
  tmp.left = node;
  return tmp;
}

左右回転（Left-Right Rotation）

二重回転は、前述の単回転を組み合わせたやや複雑な操作です。正しく理解するには、回転の過程で行われる各ステップに注目しましょう。まずは左右回転から確認します。左右回転とは、「左回転」を実行した直後に「右回転」を行う操作の組み合わせです。

状態	操作内容
	ノードが「左部分木の右部分木」に挿入されました。これによりCが不平衡ノードとなり、AVL木は左右回転を実行する必要があります。
	まずCの左部分木に対して左回転を行います。これによりAがBの左部分木になります。
	ノードCは依然として不平衡ですが、原因は「左部分木の左部分木」にある状態へ変化しました。
	続いて木を右回転し、Bをこの部分木の新しい根ノードとします。その結果、Cは自身の左部分木の右部分木として配置されます。
	これで木は再びバランスが取れました。

左回転の後に右回転を行うことから、この操作は「LR回転」とも呼ばれます。先ほど定義した2つの関数を利用すれば、以下のように簡潔に実装できます。

function rotationLR(node) {
  node.left = rotationRR(node.left);
  return rotationLL(node);
}

右左回転（Right-Left Rotation）

もう一つの二重回転である右左回転は、「右回転」を実行した後に「左回転」を行う操作の組み合わせです。

状態	操作内容
	ノードが「右部分木の左部分木」に挿入されました。これによりAが平衡係数2の不平衡ノードになります。
	まずCノードに対して右回転を行い、Cを自身の左部分木Bの右部分木とします。この時点でBがAの右部分木になります。
	ノードAは依然として不平衡です。「右部分木の右部分木」に原因があるため、左回転が必要です。
	Bを部分木の新しい根ノードとして左回転を実行します。Aは自身の右部分木Bの左部分木となります。
	これで木は再びバランスが取れました。

右回転の後に左回転を行うことから、この操作は「RL回転」とも呼ばれます。こちらも既存の2つの関数を組み合わせて、以下のように実装できます。

function rotationRL(node) {
  node.right = rotationLL(node.right);
  return rotationRR(node);
}