Các đặc tính của Cây Tìm kiếm Nhị phân

Có ba đặc tính quan trọng của Cây Tìm kiếm Nhị phân (BST) mà bạn nên nắm vững:

• 1. Duyệt trung thứ tự (In-order traversal) tạo ra một dãy số đã sắp xếp. Thứ tự duyệt: `Con trái -> Nút gốc -> Con phải`.

public LinkedList<Integer> duyetTrungThuTu(TreeNode node, LinkedList<Integer> danhSach) {
  if (node == null) return danhSach;
  duyetTrungThuTu(node.conTrai, danhSach);
  danhSach.add(node.giaTri);
  duyetTrungThuTu(node.conPhai, danhSach);
  return danhSach;
}

• 2. Hậu nhiệm (Successor) là nút tiếp theo trong dãy duyệt trung thứ tự. Nói cách khác, đó là nút có giá trị nhỏ nhất nhưng lớn hơn nút hiện tại.

Thuật toán: Bắt đầu từ nút con phải, sau đó đi liên tục đến nút con trái cho đến khi không còn nút con trái nào. Nút cuối cùng này chính là hậu nhiệm.

public int timHauNghiem(TreeNode node) {
  node = node.conPhai;
  while (node.conTrai != null) node = node.conTrai;
  return node.giaTri;
}

• 3. Tiền nhiệm (Predecessor) là nút trước đó trong dãy duyệt trung thứ tự. Nói cách khác, đó là nút có giá trị lớn nhất nhưng nhỏ hơn nút hiện tại.

Thuật toán: Bắt đầu từ nút con trái, sau đó đi liên tục đến nút con phải cho đến khi không còn nút con phải nào. Nút cuối cùng này chính là tiền nhiệm.

public int timTienNghiem(TreeNode node) {
  node = node.conTrai;
  while (node.conPhai != null) node = node.conPhai;
  return node.giaTri;
}

Phương pháp: Đệ quy

Có ba trường hợp cần xem xét khi xóa một nút:

• Trường hợp 1: Nút cần xóa là nút lá (không có nút con). Ta có thể xóa trực tiếp.
• Trường hợp 2: Nút cần xóa không phải là nút lá và có nút con phải. Nút này có thể được thay thế bằng hậu nhiệm của nó, vốn nằm ở một vị trí thấp hơn trong cây con phải. Sau đó, ta có thể xóa hậu nhiệm đó một cách đệ quy.
• Trường hợp 3: Nút cần xóa không phải là nút lá, không có nút con phải nhưng có nút con trái. Điều này có nghĩa là hậu nhiệm của nó ở trên, nhưng chúng ta không muốn di chuyển lên trên. Thay vào đó, ta có thể sử dụng tiền nhiệm của nó để thay thế, sau đó xóa tiền nhiệm đó một cách đệ quy.

Thuật toán xóa nút

• Nếu `giaTri > node.giaTri`, nút cần xóa nằm ở cây con phải, `node.conPhai = xoaNode(node.conPhai, giaTri)`.
• Nếu `giaTri < node.giaTri`, nút cần xóa nằm ở cây con trái, `node.conTrai = xoaNode(node.conTrai, giaTri)`.
• Nếu `giaTri == node.giaTri`, đây chính là nút cần xóa:
  • Nếu nút là nút lá, xóa nó trực tiếp: `node = null`.
  • Nếu nút không phải là nút lá và có nút con phải, thay thế giá trị của nó bằng giá trị của hậu nhiệm: `node.giaTri = timHauNghiem(node)`, sau đó xóa hậu nhiệm.
  • Nếu nút không phải là nút lá, không có nút con phải nhưng có nút con trái, thay thế giá trị của nó bằng giá trị của tiền nhiệm: `node.giaTri = timTienNghiem(node)`, sau đó xóa tiền nhiệm.
• Trả về `node`.

class GiaiPhap {
  /*
  Một bước sang phải rồi liên tục sang trái
  */
  public int timHauNghiem(TreeNode node) {
    node = node.conPhai;
    while (node.conTrai != null) node = node.conTrai;
    return node.giaTri;
  }

  /*
  Một bước sang trái rồi liên tục sang phải
  */
  public int timTienNghiem(TreeNode node) {
    node = node.conTrai;
    while (node.conPhai != null) node = node.conPhai;
    return node.giaTri;
  }

  public TreeNode xoaNode(TreeNode node, int giaTri) {
    if (node == null) return null;

    // Xóa từ cây con phải
    if (giaTri > node.giaTri) node.conPhai = xoaNode(node.conPhai, giaTri);
    // Xóa từ cây con trái
    else if (giaTri < node.giaTri) node.conTrai = xoaNode(node.conTrai, giaTri);
    // Xóa nút hiện tại
    else {
      // Nút là nút lá
      if (node.conTrai == null && node.conPhai == null) node = null;
      // Nút không phải là nút lá và có nút con phải
      else if (node.conPhai != null) {
        node.giaTri = timHauNghiem(node);
        node.conPhai = xoaNode(node.conPhai, node.giaTri);
      }
      // Nút không phải là nút lá, không có nút con phải nhưng có nút con trái
      else {
        node.giaTri = timTienNghiem(node);
        node.conTrai = xoaNode(node.conTrai, node.giaTri);
      }
    }
    return node;
  }
}

Phân tích độ phức tạp

• Độ phức tạp thời gian: O(logN). Trong quá trình thực thi thuật toán, chúng ta luôn di chuyển sang trái hoặc sang phải trên cây. Ban đầu, chúng ta mất O(H1) thời gian để tìm nút cần xóa, với H1 là chiều cao từ nút gốc đến nút cần xóa. Sau đó, việc xóa nút mất O(H2) thời gian, với H2 là chiều cao từ nút cần xóa đến nút thay thế. Vì O(H1 + H2) = O(H), và H là chiều cao của cây, nếu cây cân bằng thì H = logN.
• Độ phức tạp không gian: O(H), không gian được sử dụng bởi ngăn xếp trong quá trình đệ quy, với H là chiều cao của cây.