Các phép xoay AVL trong JavaScript

Để tự cân bằng, AVL tree có thể thực hiện 4 loại xoay sau:

• Xoay trái (Left rotation)
• Xoay phải (Right rotation)
• Xoay trái-phải (Left-Right rotation)
• Xoay phải-trái (Right-Left rotation)

Hai xoay đầu là xoay đơn, hai xoay sau là xoay kép. Để có cây mất cân bằng, ta cần cây chiều cao ít nhất 2. Với cây đơn giản này, hãy hiểu từng loại một.

Xoay Trái (Left Rotation)

Nếu cây mất cân bằng khi một nút được chèn vào cây con phải của cây con phải, ta thực hiện xoay trái đơn:

Trong ví dụ, nút A mất cân bằng vì nút được chèn vào cây con phải của cây con phải của A. Ta thực hiện xoay trái bằng cách làm A thành cây con trái của B. Xoay này cũng gọi là xoay LL. Hãy xem triển khai:

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

Xoay Phải (Right Rotation)

AVL tree có thể mất cân bằng nếu nút được chèn vào cây con trái của cây con trái. Cây lúc này cần xoay phải.

Như hình vẽ, nút mất cân bằng trở thành con phải của con trái của nó bằng cách xoay phải. Đây cũng gọi là xoay RR. Hãy xem code:

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

Xoay Trái-Phải (Left-Right Rotation)

Xoay kép là phiên bản phức tạp hơn của các xoay đã giải thích. Để hiểu rõ hơn, nên chú ý từng hành động khi xoay. Hãy xem cách thực hiện xoay Trái-Phải. Xoay trái-phải là kết hợp xoay trái theo sau bởi xoay phải.

Trạng thái	Hành động
	Một nút đã được chèn vào cây con phải của cây con trái. Điều này làm C thành nút mất cân bằng. Các tình huống này khiến AVL tree thực hiện xoay trái-phải.
	Trước tiên thực hiện xoay trái trên cây con trái của C. Điều này làm A thành cây con trái của B.
	Nút C vẫn mất cân bằng, tuy nhiên bây giờ là do cây con trái của cây con trái.
	Ta sẽ xoay phải cây, làm B thành gốc mới của cây con này. C giờ thành cây con phải của chính cây con trái của nó.
	Cây hiện đã cân bằng.

Đây cũng gọi là xoay LR vì ta xoay trái trước rồi xoay phải sau. Có thể triển khai dùng 2 phương thức trước như sau:

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

Xoay Phải-Trái (Right-Left Rotation)

Loại xoay kép thứ hai là Right-Left Rotation. Là kết hợp xoay phải theo sau bởi xoay trái.

Trạng thái	Hành động
	Một nút đã được chèn vào cây con trái của cây con phải. Điều này làm A, thành nút mất cân bằng với balance factor 2.
	Trước tiên, thực hiện xoay phải dọc theo nút C, làm C thành cây con phải của chính cây con trái của nó B. Bây giờ, B thành cây con phải của A.
	Nút A vẫn mất cân bằng do cây con phải của cây con phải và cần xoay trái.
	Xoay trái được thực hiện bằng cách làm B thành gốc mới của cây con. A thành cây con trái của cây con phải B.
	Cây hiện đã cân bằng.

Đây cũng gọi là xoay RL vì ta xoay phải trước rồi xoay trái sau. Có thể triển khai dùng 2 phương thức trước như sau:

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