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

AVL ट्री बाएँ और दाएँ उप-वृक्षों की ऊँचाई की जाँच करता है और आश्वासन देता है कि अंतर 1 से अधिक नहीं है। इस अंतर को बैलेंस फैक्टर कहा जाता है।

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

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

BalanceFactor = height(left-sutree) − height(right-sutree)

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

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

उदाहरण

class AVLTree {
   constructor() {
      // Initialize a root element to null.
      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;
   }
};