जावास्क्रिप्ट AVL ट्री में बैलेंस फैक्टर की गणना

AVL ट्री लेफ्ट और राइट सब-ट्रीज़ की ऊंचाई की जांच करता है और सुनिश्चित करता है कि अंतर 1 से अधिक न हो। इस अंतर को बैलेंस फैक्टर कहा जाता है।

उदाहरण के लिए, निम्नलिखित ट्रीज़ में, पहला ट्री बैलेंस्ड है और अगले दो ट्री बैलेंस्ड नहीं हैं:

दूसरे ट्री में, C के लेफ्ट सबट्री की ऊंचाई 2 है और राइट सबट्री की ऊंचाई 0 है, इसलिए अंतर 2 है। तीसरे ट्री में, A के राइट सबट्री की ऊंचाई 2 है और लेफ्ट गायब है, इसलिए यह 0 है, और अंतर फिर से 2 है। AVL ट्री केवल 1 तक के अंतर (बैलेंस फैक्टर) की अनुमति देता है।

बैलेंसफैक्टर = ऊंचाई(लेफ्ट-सबट्री) - ऊंचाई(राइट-सबट्री)

यदि लेफ्ट और राइट सब-ट्रीज़ की ऊंचाई में अंतर 1 से अधिक है, तो ट्री को कुछ रोटेशन तकनीकों का उपयोग करके बैलेंस किया जाता है।

आइए इस मेथड को परिभाषित करते हैं और क्लास को इनिशियलाइज़ भी करते हैं:

उदाहरण

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