জাভাস্ক্রিপ্ট ট্রিতে নোড সরানো

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

ক্লাস মেথড

deleteNode(key) {
    // যদি একটি নোড সফলভাবে সরানো হয়, একটি রেফারেন্স পাওয়া যাবে।
    return !(deleteNodeHelper(this.root, key) === false);
}

হেল্পার মেথড

/**
 * রুট এবং কি নেয় এবং রিকারসিভলি কিটি খুঁজে বের করে।
 * যদি কিটি পাওয়া যায়, তবে ৩টি কেস হতে পারে:
 *
 * ১. এই নোডটি একটি লীফ নোড।
 *
 * উদাহরণ: F সরানো
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * সরাতে, আমরা সাদা এর প্যারেন্টের কানেকশন সরাতে পারি।
 *
 * A
 * / \
 * B C
 * / /
 * D E
 *
 * ২. এই নোডটি ট্রির মাঝপথে একটু চাইল্ডসহ।
 *
 * উদাহরণ: B সরানো
 * A
 * / \
 * B C
 * / / \
 * D E F
 *
 * সরাতে, আমরা চাইল্ড নোডকে উপরের কানেকশনে প্যারেন্ট নোডের স্থান দিতে পারি
 * A
 * / \
 * D C
 * / \
 * E F
 *
 * ৩. এই নোডের দুটি চাইল্ড আছে। এটি একটি ট্রিকি কেস।
 *
 * উদাহরণ: C সরানো
 *
 * A
 * / \
 * B C
 * / / \
 * D E F
 * / / \
 * G H I
 *
 * এই কেসে, আমাদের নোডের একটি সাকসেসর বা প্রিডিসেসর খুঁজে বের করতে হবে এবং এই নোডকে সেটি দিয়ে রিপ্লেস করতে হবে। উদাহরণস্বরূপ, যদি আমরা সাকসেসরের সাথে যাই, তবে এর সাকসেসর হবে এর চেয়ে ঠিক বড় এলিমেন্ট, অর্থাৎ ডান সাবট্রির মিন এলিমেন্ট। তাই ডিলিশনের পর ট্রি দেখাবে:
 *
 * A
 * / \
 * B H
 * / / \
 * D E F
 * / \
 * G I
 *
 * এই এলিমেন্ট সরাতে, আমাদের সাকসেসরের প্যারেন্ট খুঁজে বের করতে হবে, তাদের লিংক ভাঙতে হবে, সাকসেসরের লেফট এবং রাইট বর্তমান নোডের লেফট এবং রাইটে পয়েন্ট করাতে হবে। সহজ পথ হলো ডিলিট হওয়া নোডের ডেটাকে সাকসেসরের দিয়ে রিপ্লেস করুন এবং সাকসেসরটি ডিলিট করুন। */
function deleteNodeHelper(root, key) {
    if (root === null) {
        // খালি ট্রি 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 {
        // কোনো চাইল্ড নেই
        // কেস ১ - একটি লীফ নোড
        if (root.left === null && root.right === null) {
            root = null;
            return root;
        }
        // সিঙ্গল চাইল্ড কেস
        if (root.left === null) return root.right;
        if (root.right === null) return root.left;
        // দুটি চাইল্ড, সুতরাং সাকসেসর খুঁজতে হবে
        let currNode = root.right;
        while (currNode.left !== null) {
            currNode = currNode.left;
        }
        root.data = currNode.data;
        // ডান সাবট্রি থেকে ভ্যালু ডিলিট করুন।
        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