Xóa nút trong Tree JavaScript

Xóa một Node khỏi cây khá phức tạp nếu nhìn từ xa. Có 3 trường hợp cần xem xét khi xóa nút. Chúng được đề cập trong comment của hàm sau. Như trước đây, ta sẽ tạo phương thức trong class và helper để gọi đệ quy.

Phương thức class

deleteNode(key) {
  // Nếu nút xóa thành công, tham chiếu sẽ được nhận.
  return !(deleteNodeHelper(this.root, key) === false);
}

Phương thức helper

/**
 * Nhận root và key, đệ quy tìm key.
 * Nếu tìm thấy key, có thể có 3 trường hợp:
 * 1. Nút này là nút lá.
 * 2. Nút này ở giữa cây với một con.
 * 3. Nút này có cả hai con (trường hợp phức tạp).
 */
function deleteNodeHelper(root, key) {
  if (root === null) {
    // Cây rỗng
    return false;
  }
  if (key < root.data) {
    root.left = deleteNodeHelper(root.left, key);
    return root;
  } else if (key > root.data) {
    root.right = deleteNodeHelper(root.right, key);
    return root;
  } else {
    // Không có con - trường hợp 1: nút lá
    if (root.left === null && root.right === null) {
      root = null;
      return root;
    }
    // Trường hợp một con
    if (root.left === null) return root.right;
    if (root.right === null) return root.left;
    // Cả hai con, cần tìm successor
    let currNode = root.right;
    while (currNode.left !== null) {
      currNode = currNode.left;
    }
    root.data = currNode.data;
    // Xóa giá trị từ cây con phải.
    root.right = deleteNodeHelper(root.right, currNode.data);
    return root;
  }
}

Bạn có thể kiểm tra bằng cách sau:

Ví dụ

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.inOrder();
BST.deleteNode(15);
BST.deleteNode(10);
BST.deleteNode(3);
BST.inOrder();

Kết quả

Điều này sẽ cho ra kết quả:

5 7 12 50