Bài 1: Xoay Cây AVL & Red-Black — Tự Cân Bằng Từng Bước

Chào mừng bạn đến với bài học đầu tiên trong series Cấu Trúc Dữ Liệu & Giải Thuật Trực Quan. Trước khi đi vào chi tiết phép xoay, chúng ta cần trả lời một câu hỏi cốt lõi: tại sao một cây nhị phân tìm kiếm (Binary Search Tree — BST) bình thường lại chưa đủ tốt, và cây tự cân bằng giải quyết vấn đề đó ra sao.

1. Vì sao BST thường cần phải tự cân bằng?

Một cây nhị phân tìm kiếm đảm bảo: mọi node ở nhánh trái nhỏ hơn node cha, mọi node ở nhánh phải lớn hơn. Tra cứu, chèn, xoá đều có độ phức tạp lý thuyết $O(\log n)$ — nhưng chỉ khi cây cân đối. Vấn đề là: nếu bạn chèn dữ liệu theo thứ tự đã sắp xếp sẵn (ví dụ 1, 2, 3, 4, 5…), BST suy biến thành một danh sách liên kết một chiều.

// Chèn tuần tự 1,2,3,4,5 vào BST thường
// KHÔNG có cơ chế tự cân bằng
insert(1); insert(2); insert(3); insert(4); insert(5);

// Kết quả: cây suy biến thành chuỗi lệch phải hoàn toàn
//   1
//    \
//     2
//      \
//       3
//        \
//         4
//          \
//           5
// Tìm kiếm giá trị 5 giờ tốn O(n) thay vì O(log n)!

Đây chính là lúc invariant phát huy tác dụng: nếu ta ép buộc cây luôn thoả một điều kiện cân bằng nhất định sau mỗi lần chèn/xoá, chiều cao cây sẽ luôn ở mức $O(\log n)$ bất kể thứ tự dữ liệu đầu vào.

2. Hệ số cân bằng & Bất biến của cây AVL

Cây AVL (đặt theo tên hai nhà phát minh Adelson-Velsky và Landis, 1962) định nghĩa hệ số cân bằng (Balance Factor — BF) của một node là:

Với quy ước $height(\text{null}) = 0$. Bất biến AVL yêu cầu: tại mọi node, $|BF(x)| \le 1$. Nếu sau một thao tác chèn/xoá mà $|BF(x)| = 2$ tại node nào đó, ta phải thực hiện phép xoay để đưa cây về lại bất biến.

function height(node) {
  return node ? node.height : 0;
}

function getBalance(node) {
  if (!node) return 0;
  return height(node.left) - height(node.right);
}

function updateHeight(node) {
  node.height = 1 + Math.max(height(node.left), height(node.right));
}

3. Bốn trường hợp mất cân bằng & phép xoay tương ứng

Khi $|BF(x)| = 2$ tại node $x$ vừa được cập nhật, chỉ có đúng 4 tình huống có thể xảy ra, phân loại theo "hướng" mất cân bằng của 2 cấp liên tiếp:

• LL (Left-Left): lệch trái tại x, lệch trái tại con trái → xoay phải đơn.
• RR (Right-Right): lệch phải tại x, lệch phải tại con phải → xoay trái đơn.
• LR (Left-Right): lệch trái tại x, lệch phải tại con trái → xoay trái tại con trái, rồi xoay phải tại x (xoay kép).
• RL (Right-Left): lệch phải tại x, lệch trái tại con phải → xoay phải tại con phải, rồi xoay trái tại x (xoay kép).

Cài đặt hai phép xoay đơn — nền tảng cho cả 4 trường hợp:

// Xoay phải quanh y — dùng khi mất cân bằng lệch trái (LL)
function rotateRight(y) {
  const x = y.left;
  const T2 = x.right;

  x.right = y;
  y.left = T2;

  updateHeight(y); // cập nhật node cũ TRƯỚC
  updateHeight(x); // rồi mới đến node gốc mới

  return x; // x trở thành gốc subtree mới
}

// Xoay trái quanh x — dùng khi mất cân bằng lệch phải (RR)
function rotateLeft(x) {
  const y = x.right;
  const T2 = y.left;

  y.left = x;
  x.right = T2;

  updateHeight(x);
  updateHeight(y);

  return y;
}

Với case xoay kép (LR/RL), ta chỉ cần ghép 2 xoay đơn lại — không cần logic mới:

function insert(node, value) {
  // 1. Chèn như BST thường
  if (!node) return { value, left: null, right: null, height: 1 };
  if (value < node.value) node.left = insert(node.left, value);
  else if (value > node.value) node.right = insert(node.right, value);
  else return node; // giá trị đã tồn tại

  // 2. Cập nhật height & tính hệ số cân bằng
  updateHeight(node);
  const balance = getBalance(node);

  // 3. Bốn trường hợp xoay
  if (balance > 1 && value < node.left.value) {
    return rotateRight(node); // LL
  }
  if (balance < -1 && value > node.right.value) {
    return rotateLeft(node); // RR
  }
  if (balance > 1 && value > node.left.value) {
    node.left = rotateLeft(node.left); // LR: xoay trái con trái trước
    return rotateRight(node); //     rồi xoay phải tại node
  }
  if (balance < -1 && value < node.right.value) {
    node.right = rotateRight(node.right); // RL: xoay phải con phải trước
    return rotateLeft(node); //     rồi xoay trái tại node
  }

  return node; // đã cân bằng, không cần xoay
}

4. Cây Red-Black: Luật tô màu thay cho height chính xác

AVL đảm bảo cân bằng "chặt" ($|BF| \le 1$), đổi lại phải xoay khá thường xuyên. Cây Red-Black (Rudolf Bayer, 1972) chấp nhận cân bằng "lỏng" hơn để đổi lấy ít thao tác xoay hơn khi ghi. Thay vì lưu height chính xác, mỗi node được tô đỏ hoặc đen, và phải thoả 5 luật:

1. Mỗi node là đỏ hoặc đen.
2. Node gốc (root) luôn là đen.
3. Mọi lá rỗng (NIL) được coi là đen.
4. Node đỏ không được có con đỏ (không 2 đỏ liên tiếp).
5. Mọi đường đi từ 1 node bất kỳ tới các lá NIL của nó phải chứa cùng số lượng node đen ("black-height" bằng nhau).

5 luật này đảm bảo đường đi dài nhất từ gốc không bao giờ dài quá 2 lần đường đi ngắn nhất — tức chiều cao cây vẫn bị chặn trong $O(\log n)$, dù không chặt bằng AVL.

Sân chơi tương tác: AVL Tree Sandbox

Nhập một giá trị và bấm Chèn hoặc Xoá để xem cây tự động cân bằng lại — mọi phép xoay xảy ra sẽ được ghi log chi tiết bên dưới, kèm hệ số cân bằng (BF) hiển thị cạnh mỗi node.