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

একটি নতুন তৈরি বাইনারি ট্রিতে প্রথম ইনসারশন রুটে একটি নোড তৈরি করে। পরবর্তী ইনসারশনগুলো বাইনারি সার্চ ট্রির প্রপার্টি অনুযায়ী ইনসার্ট হবে যেখানে বাম চাইল্ড প্যারেন্ট থেকে ছোট এবং ডান চাইল্ড প্যারেন্ট থেকে বড়।

আসুন দেখি কীভাবে এই অ্যালগরিদমটি কোডে বাস্তবায়ন করা যায়:

উদাহরণ

insertIter(data) {
    let node = new this.Node(data);
    // চেক করুন ট্রি খালি কিনা
    if (this.root === null) {
        // প্রথম উপাদান হিসেবে ইনসার্ট করুন
        this.root = node;
        return;
    }
    let currNode = this.root;
    while (true) {
        if (data < currNode.data) {
            // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
            if (currNode.left === null) {
                currNode.left = node;
                break;
            } else {
                currNode = currNode.left;
            }
        } else {
            // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
            if (currNode.right === null) {
                currNode.right = node;
                break;
            } else {
                currNode = currNode.right;
            }
        }
    }
}

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

আপনি নিচের কোড দিয়ে এই ফাংশনটি পরীক্ষা করতে পারেন:

উদাহরণ

let BST = new BinarySearchTree();
BST.insertIter(10);
BST.insertIter(15);
BST.insertIter(5);
BST.insertIter(50);
BST.insertIter(3);
BST.insertIter(7);
BST.insertIter(12);

আমরা এই ফাংশনটিকে রিকারসিভও করতে পারি। ট্রি собойস্বভাবে রিকারসিভ স্ট্রাকচার এবং আমরা এই রিকারসিভ প্রপার্টি ব্যবহার করতে পারি সহজে। আসুন ইনসার্টের একটি রিকারসিভ ভার্সন দেখি:

উদাহরণ

insertRec(data) {
    let node = new this.Node(data);
    // চেক করুন ট্রি খালি কিনা
    if (this.root === null) {
        // প্রথম উপাদান হিসেবে ইনসার্ট করুন
        this.root = node;
    } else {
        insertRecHelper(this.root, node);
    }
}

আমাদের একটি হেল্পার ফাংশন তৈরি করতে হবে যা রিকারস করতে পারবে কিন্তু আমরা সেটি ক্লাসের প্রপার্টি হিসেবে এক্সপোজ করতে চাই না, তাই এই ফাংশনটি ক্লাস ডেফিনিশনের বাইরে থাকবে।

উদাহরণ

function insertRecHelper(root, node) {
    if (node.data < root.data) {
        // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
        if (root.left === null) {
            root.left = node;
        } else {
            // বাম সাবট্রি দিয়ে এই ফাংশনটি রিকারসিভলি কল করুন
            insertRecHelper(root.left, node);
        }
    } else {
        // এখানে ভ্যালু সেট করুন কারণ আমরা লীফ নোডে পৌঁছেছি
        if (root.right === null) {
            root.right = node;
        } else {
            // ডান সাবট্রি দিয়ে এই ফাংশনটি রিকারসিভলি কল করুন
            insertRecHelper(root.right, node);
        }
    }
}

আপনি নিচের কোড দিয়ে এটি পরীক্ষা করতে পারেন:

উদাহরণ

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);