Xóa một nút trong Cây Javascript

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

Phương thức lớp

deleteNode(key) {
   // If a node is successfully removed, a reference will be received.
   return !(deleteNodeHelper(this.root, key) === false);
}

Phương thức trợ giúp

/**
   * Takes root and key and recursively searches for the key.
   * If it finds the key, there could be 3 cases:
   *
   * 1. This node is a leaf node.
   *
   * Example: Removing F
   *     A
   *    / \
   *   B   C
   *  /   / \
   * D   E   F
   *
   * To remove it, we can simply remove its parent's connection to it.
   *
   *      A
   *     / \
   *    B   C
   *   /    /
   *  D    E
   *
   * 2. This node is in between the tree somewhere with one child.
   *
   * Example: Removing B
   *       A
   *      / \
   *     B   C
   *    /   / \
   *   D   E   F
   *
   * To remove it, we can simply make the child node replace the parent node in the above connection
   *       A
   *      / \
   *     D   C
   *        / \
   *       E   F
   *
   * 3. This node has both children. This is a tricky case.
   *
   * Example: Removing C
   *
   *        A
   *       / \
   *      B   C
   *     /   / \
   *    D   E   F
   *       /   / \
   *      G   H   I
   *
   * In this case, we need to find either a successor or a predecessor of the node and replace this node with
   * that. For example, If we go with the successor, its successor will be the element just greater than it,
   * ie, the min element in the right subtree. So after deletion, the tree would look like:
   *
   *        A
   *       / \
   *      B   H
   *     /   / \
   *    D   E   F
   *       /     \
   *      G       I
   *
   * To remove this element, we need to find the parent of the successor, break their link, make successor's left
   * and right point to current node's left and right. The easier way is to just replace the data from node to be
   * deleted with successor and delete the sucessor.
*/
function deleteNodeHelper(root, key) {
   if (root === null) {
      // Empty tree 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 {
      // No children
      //case 1 - a leaf node
      if (root.left === null && root.right === null) {
         root = null;
         return root;
      }
      // Single Child cases
      if (root.left === null) return root.right;
      if (root.right === null) return root.left;

      // Both children, so need to find successor
      let currNode = root.right;
      while (currNode.left !== null) {
         currNode = currNode.left;
      }
      root.data = currNode.data;
      // Delete the value from right subtree.
      root.right = deleteNodeHelper(root.right, currNode.data);
      return root;
   }
}

Bạn có thể kiểm tra điều này bằng cách sử dụng -

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();

Đầu ra

Điều này sẽ cung cấp đầu ra -

5
7
12
50