जावास्क्रिप्ट में बाइनरी सर्च ट्री से वांछित नोड को हटाना

समस्या

मान लीजिए, हमारे पास निम्न कोड है जो एक बाइनरी सर्च ट्री डीएस बनाता है और हमें नोड डालने की कार्यक्षमता प्रदान करता है -

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);

इसी कोड के निष्पादन के बाद, हमारा BST कुछ इस तरह दिखेगा -

5
/ \
3 6
/ \ \
2 4 7

हमें अभी तक एक और फ़ंक्शन deleteNode() लिखने की आवश्यकता है जो पहले तर्क के रूप में किसी भी बीएसटी की जड़ और दूसरे तर्क के रूप में एक संख्यात्मक मान लेता है।

और यदि दूसरे तर्क द्वारा निर्दिष्ट मान ट्री में मौजूद है, तो हमारे फ़ंक्शन को उस नोड को हटा देना चाहिए जो मान रखता है अन्यथा हमारे फ़ंक्शन को कुछ नहीं करना चाहिए। दोनों ही मामलों में, हमारे फ़ंक्शन को BST का अपडेटेड रूट लौटाना चाहिए।

उदाहरण

इसके लिए कोड होगा -

class Node{
   constructor(data) {
      this.data = data;
      this.left = null;
      this.right = null;
   };
};
class BinarySearchTree{
   constructor(){
      // root of a binary seach tree
      this.root = null;
   }
   insert(data){
      var newNode = new Node(data);
      if(this.root === null){
         this.root = newNode;
      }else{
         this.insertNode(this.root, newNode);
      };
   };
   insertNode(node, newNode){
      if(newNode.data < node.data){
         if(node.left === null){
            node.left = newNode;
         }else{
            this.insertNode(node.left, newNode);
         };
      } else {
         if(node.right === null){
            node.right = newNode;
         }else{
            this.insertNode(node.right,newNode);
         };
      };
   };
};
const BST = new BinarySearchTree();
BST.insert(5);
BST.insert(3);
BST.insert(6);
BST.insert(2);
BST.insert(4);
BST.insert(7);
const printTree = (node) => {
   if(node !== null) {
      printTree(node.left);
      console.log(node.data);
      printTree(node.right);
   };
};
const deleteNode = function(root, key) {
   if(!root){
      return null;
   };
   if(root.data > key){
      if(!root.left){
         return root;
      }else{
         root.left = deleteNode(root.left, key);
      };
   } else if(root.data < key){
      if(!root.right) return root;
      else root.right = deleteNode(root.right, key);
   } else {
      if(!root.left || !root.right){
         return root.left || root.right;
      } else {
         let nd = new TreeNode();
         let right = root.right;
         nd.left = root.left;
         while(right.left){
            right = right.left;
         }
         nd.data = right.data;
         nd.right = deleteNode(root.right, right.data);
         return nd;
      }
   }
   return root;
};
console.log('Before Deleting any node');
printTree(BST.root);
console.log('After deleting node with data 4');
printTree(deleteNode(BST.root, 4));

कोड स्पष्टीकरण:

लक्ष्य नोड खोजने के बाद हमें कुल तीन स्थितियों पर विचार करने की आवश्यकता है।

• एक पत्ता (न बाएँ, न दाएँ);

• छोड़ दिया है, कोई अधिकार नहीं; बाएं नहीं, दाएं है;

• बाएँ और दाएँ दोनों हैं।

1 और 2 आसान हैं, हमें बस शून्य या हमारे पास जो कुछ भी है (बाएं या दाएं) वापस करने की जरूरत है;

और आखिरी शर्त के लिए, हमें यह जानना होगा कि लक्ष्य नोड को हटाने के बाद, इसे बदलने के लिए क्या होगा। यदि हम इसे केवल बाएँ या दाएँ ऊपर खींचते हैं, तो BST अमान्य होगा। इसलिए हमें या तो दाएँ उप-वृक्ष से सबसे छोटा या बाएँ उप-वृक्ष से सबसे बड़ा ढूँढ़ना होगा।

आउटपुट

और कंसोल में आउटपुट होगा -

Before Deleting any node
2
3
4
5
6
7
After deleting node with data 4
2
3
5
6
7