জাভাস্ক্রিপ্ট AVL ট্রিতে ব্যালেন্স ফ্যাক্টর ক্যালকুলেট করা

AVL ট্রি বাম এবং ডান সাব-ট্রির উচ্চতা চেক করে এবং নিশ্চিত করে যে পার্থক্যটি ১-এর বেশি নয়। এই পার্থক্যকে ব্যালেন্স ফ্যাক্টর (Balance Factor) বলা হয়।

উদাহরণস্বরূপ, নিচের ট্রিগুলোতে, প্রথম ট্রিটি ব্যালেন্সড এবং পরের দুটি ট্রি আনব্যালেন্সড:

দ্বিতীয় ট্রিতে, C-এর বাম সাবট্রির উচ্চতা ২ এবং ডান সাবট্রির উচ্চতা ০, তাই পার্থক্য ২। তৃতীয় ট্রিতে, A-এর ডান সাবট্রির উচ্চতা ২ এবং বামটি নেই, তাই ০, এবং পার্থক্য আবার ২। AVL ট্রি পার্থক্য (ব্যালেন্স ফ্যাক্টর) কেবল ১ হতে দেয়।

BalanceFactor = height(left-subtree) - height(right-subtree)

যদি বাম এবং ডান সাব-ট্রির উচ্চতার পার্থক্য ১-এর বেশি হয়, তবে ট্রিটি কিছু রোটেশন টেকনিক ব্যবহার করে ব্যালেন্স করা হয়।

আসুন এই মেথডটি ডিফাইন করি এবং ক্লাসটিও ইনিশিয়ালাইজ করি:

উদাহরণ

class AVLTree {
    constructor() {
        // একটি রুট এলিমেন্ট নাল দিয়ে ইনিশিয়ালাইজ করুন।
        this.root = null;
    }
    getBalanceFactor(root) {
        return this.getHeight(root.left) - this.getHeight(root.right);
    }
    getHeight(root) {
        let height = 0;
        if (root === null) {
            height = -1;
        } else {
            height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
        }
        return height;
    }
}
AVLTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};