জাভাস্ক্রিপে একটি বাইনারি অনুসন্ধান গাছ থেকে পছন্দসই নোড মুছে ফেলা হচ্ছে

সমস্যা

ধরুন, আমাদের কাছে নিম্নলিখিত কোড রয়েছে যা একটি বাইনারি সার্চ ট্রি ডিএস তৈরি করে এবং আমাদেরকে নোড সন্নিবেশ করার কার্যকারিতা প্রদান করে -

এই কোডটি কার্যকর করার পরে, আমাদের BST দেখতে এইরকম কিছু দেখাবে -

5/ \3 6/ \ \2 4 7

আমাদের আরেকটি ফাংশন deleteNode() লিখতে হবে যা প্রথম আর্গুমেন্ট হিসেবে যেকোনো BST-এর রুটে নেয় এবং দ্বিতীয় আর্গুমেন্ট হিসেবে একটি সংখ্যাসূচক মান।

এবং যদি দ্বিতীয় আর্গুমেন্ট দ্বারা নির্দিষ্ট করা মানটি Tree-তে বিদ্যমান থাকে, তাহলে আমাদের ফাংশনটি সেই নোডটিকে মুছে ফেলতে হবে যা মানটি ধরে রাখে অন্যথায় আমাদের ফাংশন কিছুই করবে না। উভয় ক্ষেত্রেই, আমাদের ফাংশনটি BST-এর আপডেট করা রুট ফিরিয়ে দেবে।

উদাহরণ

এর জন্য কোড হবে −

<প্রি>ক্লাস নোড{ কনস্ট্রাক্টর(ডেটা) { this.data =ডেটা; this.left =null; this.right =null; };};ক্লাস 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 { if(node !==null) { printTree(node.left); console.log(node.data); printTree(node.right); };};const deleteNode =function(root, key) { if(!root){ রিটার্ন null; }; if(root.data> key){ if(!root.left){ রিটার্ন রুট; }else{ root.left =deleteNode(root.left, key); }; } else if(root.data

কোড ব্যাখ্যা:

টার্গেট নোড খুঁজে পাওয়ার পর আমাদের মোট তিনটি অবস্থার কথা ভাবতে হবে।

একটি পাতা (কোন বাম নয়, ডানে নেই);
বামে আছে, ডান নেই; কোন বাম নেই, ডান আছে;
বাম এবং ডান উভয়ই আছে৷

1 এবং 2 সহজ, আমাদের শুধু শূন্য বা আমাদের যা কিছু আছে (বাম বা ডানে) ফেরত দিতে হবে;

এবং শেষ শর্তের জন্য, আমাদের জানতে হবে যে আমরা টার্গেট নোড মুছে ফেলার পরে, এটি কী প্রতিস্থাপন করতে যাচ্ছে। যদি আমরা এটিকে বাম বা ডানদিকে টেনে আনে, তাহলে BST অকার্যকর হবে। তাই আমাদের হয় ডান সাবট্রি থেকে সবচেয়ে ছোট বা বাম সাবট্রি থেকে সবচেয়ে বড় খুঁজে বের করতে হবে।

আউটপুট

এবং কনসোলে আউটপুট হবে −

কোন নোড মুছে ফেলার আগে 234567 ডেটা 423567 সহ নোড মুছে ফেলার পরে