समस्या
मान लीजिए, हमारे पास निम्न कोड है जो बाइनरी सर्च ट्री DS बनाता है और हमें नोड डालने की कार्यक्षमता प्रदान करता है:
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 की जड़ को पहली आर्ग्युमेंट और एक संख्यात्मक मान को दूसरी आर्ग्युमेंट के रूप में लेता है।
और यदि दूसरी आर्ग्युमेंट द्वारा निर्दिष्ट मान ट्री में मौजूद है, तो हमारे फ़ंक्शन को उस नोड को हटाना चाहिए जो मान रखता है अन्यथा हमारा फ़ंक्शन कुछ नहीं करना चाहिए। दोनों मामलों में, हमारा फ़ंक्शन 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 आसान हैं, हमें बस null या जो भी हमारे पास है (बायां या दायां) वापस करना होगा;
और अंतिम स्थिति के लिए, हमें यह जानना होगा कि लक्ष्य नोड को हटाने के बाद, क्या इसे बदलने जा रहा है। यदि हम बस इसके बाएं या दाएं को ऊपर खींचते हैं, तो BST अमान्य हो जाएगा। इसलिए हमें या तो दाएं सबट्री से सबसे छोटा या बाएं सबट्री से सबसे बड़ा ढूंढना होगा।
आउटपुट
कंसोल में आउटपुट होगा:
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7
