একটি জাভাস্ক্রিপ্ট ট্রি একটি নোড অপসারণ

একটি গাছ থেকে একটি নোড অপসারণ করা বেশ জটিল যদি আপনি এটিকে দূর থেকে দেখেন৷ একটি নোড সরানোর সময় বিবেচনা করার জন্য 3টি ক্ষেত্রে রয়েছে। এগুলো নিচের ফাংশনের মন্তব্যে উল্লেখ করা হয়েছে। আমরা আগে যেমন করে আসছি, আমরা ক্লাসে একটি পদ্ধতি তৈরি করব এবং বারবার কল করার জন্য একটি সাহায্যকারী তৈরি করব৷

ক্লাস পদ্ধতি

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

সহায়ক পদ্ধতি

/**
   * 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;
   }
}

আপনি −

উদাহরণ

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

আউটপুট

এটি আউটপুট দেবে −

5
7
12
50