JavascriptでのAVLローテーション

バランスを取るために、AVLツリーは次の4種類のローテーションを実行できます-

• 左回転
• 右回転
• 左-右回転
• 左右回転

最初の2回転は1回転で、次の2回転は2回転です。不均衡な木を作るには、少なくとも高さ2の木が必要です。この単純な木で、それらを1つずつ理解しましょう。

左回転

ツリーが不均衡になった場合、ノードが右側のサブツリーの右側のサブツリーに挿入されると、左に1回回転します-

この例では、ノード A ノードがAの右側のサブツリーの右側のサブツリーに挿入されると、バランスが崩れます。 Aを作成して左回転を行います Bの左側のサブツリー 。この回転はLL回転とも呼ばれます。それをどのように実装できるか見てみましょう-

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

右回転

左側のサブツリーの左側のサブツリーにノードが挿入されると、AVLツリーが不均衡になる可能性があります。次に、ツリーを右に回転させる必要があります。

示されているように、不均衡なノードは、右回転を実行することにより、左の子の右の子になります。これは、RRローテーションとも呼ばれます。コードでどのように見えるか見てみましょう-

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

左右回転

二重回転は、すでに説明したバージョンの回転の少し複雑なバージョンです。それらをよりよく理解するために、回転中に実行される各アクションに注意する必要があります。まず、左右の回転の仕方を確認しましょう。左右の回転は、左回転とそれに続く右回転の組み合わせです。

状態
	ノードが左側のサブツリーの右側のサブツリーに挿入されました。これにより、 C 不均衡なノード。これらのシナリオにより、AVLツリーは左右の回転を実行します。
	最初に、Cの左側のサブツリーで左回転を実行します。 これにより、 A 、 Bの左側のサブツリー 。
	ノードC まだ不均衡ですが、現在は、左サブツリーの左サブツリーが原因です。
	次に、ツリーを右回転させて、 Bを作成します。 このサブツリーの新しいルートノード。 C これで、独自の左側のサブツリーの右側のサブツリーになります。
	ツリーのバランスが取れました。

これは、最初に左回転を実行し、次に右回転を実行するため、LR回転とも呼ばれます。これは、前の2つの方法を使用して次のように実装できます-

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

左右回転

2番目のタイプの二重回転は左右回転です。これは、右回転とそれに続く左回転の組み合わせです。

状態
	ノードが右側のサブツリーの左側のサブツリーに挿入されました。これにより、 A、 バランス係数2の不均衡ノード。
	まず、 Cに沿って右回転を実行します ノード、 Cを作成 独自の左側のサブツリーの右側のサブツリーB 。さて、 B Aの正しいサブツリーになります 。
	ノードA 右のサブツリーの右のサブツリーのためにまだ不均衡であり、左の回転が必要です。
	左回転は Bを作成して実行されます サブツリーの新しいルートノード。 A 右側のサブツリーの左側のサブツリーになりますB 。
	ツリーのバランスが取れました。

これは、最初に右回転を実行し、次に左回転を実行するため、RL回転とも呼ばれます。これは、前の2つの方法を使用して次のように実装できます-

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