Table of Contents
स्व संतुलन पेड़ कंप्यूटर विज्ञान में डेटा संरचनाएं हैं जो सॉर्ट किए गए डेटा को कुशलतापूर्वक बनाए रखने के लिए उपयोग की जाती हैं। संतुलन कारक एक महत्वपूर्ण मीट्रिक है जो यह निर्धारित करने में मदद करता है कि क्या एक पेड़ सम्मिलन या हटाने के बाद संतुलित रहता है। इस कारक की गणना कैसे की जाए, इंजीनियरों को अनुकूलित एल्गोरिदम डिजाइन करने के लिए आवश्यक है।
बैलेंस फैक्टर क्या है?
एक आत्म संतुलन वृक्ष में एक नोड का संतुलन कारक अपने बाएं और दाएं उप-ट्रे की ऊंचाई के बीच का अंतर है। यह इंगित करता है कि नोड संतुलित, बाएं-भारी या दाएँ-भारी है। 0, 1, या -1 का एक संतुलन कारक आम तौर पर संतुलित नोड को दर्शाता है।
बैलेंस फैक्टर की गणना
शेष कारक की गणना करने के लिए, बाईं उप-ट्री की ऊंचाई को मापें और दाईं उप-ट्री की ऊंचाई को घटा दें। एक उप-ट्री की ऊंचाई नोड से एक पत्ती तक सबसे लंबे रास्ते पर किनारों की संख्या है। सूत्र है:
Balance Factory = ऊंचाई (Left Subtree) - ऊंचाई (Right Subtree)
वृक्ष संचालन में आवेदन
सम्मिलन या हटाने के दौरान, शेष कारक को पुन: प्राप्त करने से यह निर्धारित करने में मदद मिलती है कि पेड़ के संतुलन को बनाए रखने के लिए रोटेशन आवश्यक है। यदि शेष कारक 1 से अधिक हो जाता है या -1 से नीचे गिर जाता है, तो पेड़ संतुलन को बहाल करने के लिए घूर्णन करता है, जिससे कुशल खोज, सम्मिलित करने और संचालन को हटा दिया जाता है।
आम स्व-बैलेंसिंग पेड़
- एवीएल वृक्ष
- लाल-काले पेड़
- प्ले ट्री
- ट्रेप