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

আমরা শিখব কীভাবে একটি AVL ট্রিতে নোড ইনসার্ট করা যায়। AVL ট্রিতে ইনসারশন বিনিএসটির মতোই, শুধু আমাদের ইনসারশনের সময় ট্রি নিচে যাওয়ার সময় একটি অতিরিক্ত ধাপ balace tree পারফর্ম করতে হয়।

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

আমরা আবার একটি ক্লাস মেথড এবং রিকারসিভ কলের জন্য একটি হেল্পার ফাংশন তৈরি করব:

উদাহরণ

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

হেল্পার মেথড

function insertHelper(self, root, node) {
    if (root === null) {
        root = node;
    } else if (node.data < root.data) {
        // বামে যান!
        root.left = insertHelper(self, root.left, node);
        // ব্যালেন্স ফ্যাক্টর চেক করুন এবং উপযুক্ত রোটেশন পারফর্ম করুন
        if (root.left !== null && self.getBalanceFactor(root) > 1) {
            if (node.data > root.left.data) {
                root = rotationLL(root);
            } else {
                root = rotationLR(root);
            }
        }
    } else if (node.data > root.data) {
        // ডানে যান!
        root.right = insertHelper(self, root.right, node);
        // ব্যালেন্স ফ্যাক্টর চেক করুন এবং উপযুক্ত রোটেশন পারফর্ম করুন
        if (root.right !== null && self.getBalanceFactor(root) < -1) {
            if (node.data > root.right.data) {
                root = rotationRR(root);
            } else {
                root = rotationRL(root);
            }
        }
    }
    return root;
}

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

উদাহরণ

let AVL = new AVLTree();
AVL.insert(10);
AVL.insert(15);
AVL.insert(5);
AVL.insert(50);
AVL.insert(3);
AVL.insert(7);
AVL.insert(12);
AVL.inOrder();

আউটপুট

এটি নিচের আউটপুট দেবে:

3 5 7 10 12 15 50