জাভাস্ক্রিপ্টে AVL ট্রি ক্লাস

এখানে AVL Tree ক্লাসের পূর্ণ বাস্তবায়ন দেওয়া হলো:

উদাহরণ

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 || typeof root == "undefined") {
            height = -1;
        } else {
            height = Math.max(this.getHeight(root.left), this.getHeight(root.right)) + 1;
        }
        return height;
    }
    insert(data) {
        let node = new this.Node(data);
        // চেক করুন ট্রি খালি কিনা
        if (this.root === null) {
            // প্রথম উপাদান হিসেবে ইনসার্ট করুন
            this.root = node;
        } else {
            insertHelper(this, this.root, node);
        }
    }
    inOrder() {
        inOrderHelper(this.root);
    }
}
AVLTree.prototype.Node = class {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
};
function insertHelper(self, root, node) {
    (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;
}
function inOrderHelper(root) {
    if (root !== null) {
        inOrderHelper(root.left);
        console.log(root.data);
        inOrderHelper(root.right);
    }
}
function rotationLL(node) {
    let tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
}
function rotationRR(node) {
    let tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
}
function rotationLR(node) {
    node.left = rotationRR(node.left);
    return rotationLL(node);
}
function rotationRL(node) {
    node.right = rotationLL(node.right);
    return rotationRR(node);
}