সমস্যা
মনে করুন নিচের কোডটি একটি BST তৈরি করে এবং ইনসার্ট ফাংশনালিটি দিয়েছে:
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ 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(){ 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)); কোড ব্যাখ্যা:
টার্গেট নোড পাওয়ার পর তিনটি কেস হয়:
লিফ নোড (নো লেফ্ট, নো রাইট) -> null রিটার্ন।
এক taraf চাইল্ড আছে -> সেই চাইল্ড রিটার্ন।
দুই taraf চাইল্ড আছে -> ডান সাবট্রির সবচেয়ে ছোট নোড (inorder successor) বের করে সেটি রুট বানানো এবং সেটি ডিলিট করা।
আউটপুট
কনসোলে আউটপুট:
Before Deleting any node 2 3 4 5 6 7 After deleting node with data 4 2 3 5 6 7
