बैलेंस फैक्टर AVL पेड़ों में एक महत्वपूर्ण अवधारणा है, जो एक प्रकार का आत्म संतुलन द्विआधारी खोज पेड़ है। यह पेड़ की ऊंचाई को बनाए रखने में मदद करता है और खोज, सम्मिलन और हटाने जैसे कुशल संचालन को सुनिश्चित करता है। यह समझना कि बैलेंस फैक्टर की गणना कैसे की जाए और लागू करना प्रभावी ढंग से AVL पेड़ों के प्रबंधन के लिए आवश्यक है।

बैलेंस फैक्टर क्या है?

एवीएल वृक्ष में एक नोड का संतुलन कारक इसके बाएं और दाएं उप-ट्रे की ऊंचाई के बीच का अंतर है। इसे निम्नानुसार गणना की जाती है:

Balance Factory = लेफ्ट सबट्री की ऊंचाई - दायें Subtree की ऊंचाई

एक नोड का बैलेंस फैक्टर - 1, 0, या 1 हो सकता है क्योंकि पेड़ को संतुलित किया जा सकता है। यदि बैलेंस फैक्टर इन मूल्यों से अधिक हो जाता है तो पेड़ को रोटेशन के माध्यम से पुनर्संतुलन की आवश्यकता होती है।

बैलेंस फैक्टर की गणना

शेष कारक को निर्धारित करने के लिए, पहले नोड के बच्चों में जड़े प्रत्येक उप-त्रि की ऊंचाई को ढूंढें। ऊंचाई नोड से पत्ती तक सबसे लंबे रास्ते पर किनारों की संख्या है। शेष कारक प्राप्त करने के लिए बाएं उप-त्रि की ऊंचाई से दाईं उप-त्रि की ऊंचाई को घटाएं।

उदाहरण के लिए, यदि बाएं उप-त्रि की ऊंचाई 3 है और दायें उप-त्रि की ऊंचाई 1 है, तो शेष कारक 2 है, जिससे संकेत मिलता है कि नोड असंतुलित है और घूर्णन की आवश्यकता है।

बैलेंस फैक्टर के अनुप्रयोग

बैलेंस फैक्टर का उपयोग एवीएल वृक्ष के संतुलन को बनाए रखने के लिए सम्मिलन और हटाने के दौरान किया जाता है। जब एक नोड का बैलेंस फैक्टर -1 से 1 की सीमा से बाहर हो जाता है, तो संतुलन को बहाल करने के लिए रोटेशन किया जाता है।

  • एकल दायां रोटेशन
  • सिंगल लेफ्ट रोटेशन
  • बाएं-दाएं रोटेशन
  • राइट-लेफ्ट रोटेशन

ये ऑपरेशन पेड़ की ऊंचाई को कम रखने में मदद करते हैं, जो खोज संचालन के लिए इष्टतम प्रदर्शन सुनिश्चित करते हैं।