Cây nhị phân tìm kiếm

Bài Sắp xếp & tìm kiếm kết lại với một nỗi phiền: tìm nhị phân rất nhanh, nhưng chỉ chạy trên mảng đã sắp - mà cứ thêm hay xoá một phần tử là dãy lại lệch, phải sắp lại. Có cách nào vừa giữ thứ tự, vừa cho thêm/xoá nhanh không?

Có: cây nhị phân tìm kiếm (Binary Search Tree, BST). Hãy coi nó là “tìm nhị phân được làm thành một cấu trúc sống”: mỗi node đặt ra một câu hỏi nhỏ hơn tôi thì rẽ trái, lớn hơn thì rẽ phải, và quy tắc đó đúng ở mọi node trong cây.

• ▸BST giữ dữ liệu có thứ tự mà vẫn cho tìm, chèn, xoá nhanh.
• ▸Mỗi node là một bước rẽ trái/phải - giống mỗi bước chia đôi của tìm nhị phân.
• ▸Nó được dựng từ node + con trỏ, đúng các viên gạch ở bài Mảng & danh sách liên kết.

Mỗi node có ba phần: value (giá trị), con left và con right. Điều làm nên BST là bất biến (invariant): với mọi node, toàn bộ cây con bên TRÁI nhỏ hơn nó, toàn bộ cây con bên PHẢI lớn hơn nó. Ví dụ chèn 5, 3, 8, 1, 4, 7, 9:

• ▸node = { value, left, right } - đúng kiểu node + con trỏ đã quen.
• ▸Bất biến: trái < node < phải, đúng ở MỌI node (không chỉ con trực tiếp).
• ▸Node trên cùng là gốc (root); node không có con là lá (leaf).

Tìm bắt đầu từ gốc: bằng thì xong; nhỏ hơn thì sang con trái; lớn hơn sang con phải - mỗi bước bỏ đi một nửa cây. Chèn đi y như tìm, tới chỗ trống thì gắn node mới vào. Và một món quà: duyệt in-order (trái → gốc → phải) cho ra đúng dãy đã sắp.

type Node = { value: number; left: Node | null; right: Node | null };

function insert(root: Node | null, value: number): Node {
  if (!root) return { value, left: null, right: null };
  if (value < root.value) return { ...root, left: insert(root.left, value) };
  if (value > root.value) return { ...root, right: insert(root.right, value) };
  return root; // trung thi bo qua
}

function inorder(root: Node | null, out: number[] = []): number[] {
  if (!root) return out;
  inorder(root.left, out); out.push(root.value); inorder(root.right, out);
  return out;
}

function timKiem(root: Node | null, x: number) {
  const path: number[] = [];
  let node = root;
  while (node) {
    path.push(node.value);
    if (x === node.value) return { found: true, path };
    node = x < node.value ? node.left : node.right; // re mot nua
  }
  return { found: false, path };
}

let cay: Node | null = null;
for (const v of [5, 3, 8, 1, 4, 7, 9]) cay = insert(cay, v);

console.log(inorder(cay).join(' ')); // in-order -> da sap
console.log(timKiem(cay, 7));        // tim 7
console.log(timKiem(cay, 6));        // tim 6 (khong co)

1 3 4 5 7 8 9
{ found: true, path: [ 5, 8, 7 ] }
{ found: false, path: [ 5, 8, 7 ] }

• ▸Tìm/chèn: đi từ gốc, mỗi bước so sánh rồi rẽ trái hoặc phải.
• ▸Số bước = chiều cao cây - cây càng thấp càng nhanh.
• ▸Duyệt in-order một BST luôn cho dãy đã sắp tăng dần.

Nhập một số rồi bấm Chèn để cây lớn dần; bấm Tìm để xem đường đi tô màu từ gốc xuống. Để ý ô Chiều cao so với lý tưởng:

• ▸Đường tìm luôn đi từ gốc xuống, mỗi tầng một bước.
• ▸Cây cân đối: chiều cao gần bằng “lý tưởng” log n.
• ▸Bấm “Ví dụ lệch” để thấy cây suy biến thành đường thẳng.

Mọi chi phí của BST đều bằng chiều cao cây. Cây cân đối có chiều cao quanh log n, nên tìm/ chèn/xoá đều O(log n): một triệu node chỉ cao chừng 20 tầng.

• ▸Chi phí tìm/chèn/xoá = chiều cao cây.
• ▸Cân đối: O(log n). Suy biến (chèn dãy đã sắp): O(n).
• ▸Cây tự cân bằng (AVL, Red-Black) giữ chiều cao ~log n sau mỗi thay đổi.

BST cho ta điều tìm nhị phân thiếu: một cấu trúc vừa có thứ tự, vừa thay đổi nhanh - miễn là giữ cây cân đối. Nó tuyệt khi bạn cần dữ liệu theo thứ tự (liệt kê tăng dần, tìm khoảng, lấy nhỏ nhất/lớn nhất).