AA tree
कंप्यूटर विज्ञान में ए. ए. वृक्ष संतुलित वृक्ष का एक रूप है जिसका उपयोग आदेशित डेटा को कुशलता से संग्रहीत करने और पुनर्प्राप्त करने के लिए किया जाता है। ए. ए. पेड़ों का नाम उनके प्रवर्तक, स्वीडिश कंप्यूटर वैज्ञानिक आर्ने एंडरसन के नाम पर रखा गया है। एए ट्री लाल-काले पेड़ की एक भिन्नता है, जो द्विआधारी खोज पेड़ का एक रूप है जो प्रविष्टियों के कुशल जोड़ और हटाने का समर्थन करता है। लाल-काले पेड़ों के विपरीत, ए. ए. पेड़ पर लाल नोड केवल एक सही उप-बच्चे के रूप में जोड़े जा सकते हैं। दूसरे शब्दों में, कोई भी लाल नोड लेफ्ट सब-चाइल्ड नहीं हो सकता है। इसके परिणामस्वरूप एक 2-3-4 पेड़ के बजाय 2-3 पेड़ का अनुकरण होता है, जो रखरखाव कार्यों को बहुत सरल बनाता है। एक लाल-काले पेड़ के लिए रखरखाव एल्गोरिदम को पेड़ को ठीक से संतुलित करने के लिए सात अलग-अलग आकारों पर विचार करने की आवश्यकता होती हैः दूसरी ओर एक एए पेड़ को केवल दो आकारों पर विचार करने की आवश्यकता होती है क्योंकि सख्त आवश्यकता के कारण केवल सही लिंक लाल हो सकते हैंः संतुलन आवर्तन जबकि लाल-काले पेड़ों को प्रति नोड (रंग) मेटाडेटा को संतुलित करने के लिए एक बिट की आवश्यकता होती है, एए पेड़ों को प्रति नोड मेटाडेटा के ओ (लॉग (लॉग (एन))) बिट्स की आवश्यकता होती है, एक पूर्णांक "स्तर" के रूप में। एए पेड़ों के लिए निम्नलिखित अपरिवर्तनीय हैंः प्रत्येक पत्ती नोड का स्तर एक है। प्रत्येक बाएं बच्चे का स्तर उसके माता-पिता की तुलना में बिल्कुल एक कम होता है। प्रत्येक सही बच्चे का स्तर उसके माता-पिता के बराबर या उससे एक कम होता है। प्रत्येक सही पोते का स्तर उसके दादा-दादी से काफी कम होता है। एक से अधिक स्तर के प्रत्येक नोड में दो बच्चे होते हैं। एक कड़ी जहाँ बच्चे का स्तर उसके माता-पिता के स्तर के बराबर होता है, उसे क्षैतिज कड़ी कहा जाता है, और यह लाल-काले पेड़ में एक लाल कड़ी के समान होती है। व्यक्तिगत दाएँ क्षैतिज लिंक की अनुमति है, लेकिन लगातार लिंक निषिद्ध हैं; सभी बाएँ क्षैतिज लिंक निषिद्ध हैं। ये लाल-काले पेड़ों की तुलना में अधिक प्रतिबंधात्मक बाधाएं हैं, जिसके परिणामस्वरूप एक एए पेड़ को फिर से संतुलित करना एक लाल-काले पेड़ को फिर से संतुलित करने की तुलना में प्रक्रियात्मक रूप से बहुत सरल है। प्रविष्टि और विलोपन अस्थायी रूप से एक ए. ए. वृक्ष के असंतुलित होने का कारण बन सकते हैं (यानी, ए. ए. वृक्ष अपरिवर्तकों का उल्लंघन करने के लिए)। संतुलन बहाल करने के लिए केवल दो अलग-अलग संचालन की आवश्यकता होती हैः "तिरछा" और "विभाजित"। तिरछा एक दाएँ घूर्णन है जो एक उप-वृक्ष को बदलने के लिए होता है जिसमें एक बाईं क्षैतिज कड़ी होती है और इसके बजाय एक दाएँ क्षैतिज कड़ी होती है। स्प्लिट एक बाएँ घूर्णन और स्तर की वृद्धि है जिसमें दो या दो से अधिक लगातार दाएँ क्षैतिज लिंक वाले उप-वृक्ष को दो कम लगातार दाएँ क्षैतिज लिंक वाले एक के साथ प्रतिस्थापित किया जाता है। संतुलन-संरक्षण प्रविष्टि और विलोपन के कार्यान्वयन को सरल बनाया गया है, जिसमें आवश्यकता पड़ने पर ही वृक्ष को संशोधित करने के लिए तिरछे और विभाजित संचालन पर भरोसा किया जाता है, बजाय इसके कि उनके कॉल करने वाले यह तय करें कि उन्हें तिरछा या विभाजित करना है या नहीं। फंक्शन स्क्यू इनपुट हैः टी, एक ए. ए. ट्री का प्रतिनिधित्व करने वाला एक नोड जिसे फिर से संतुलित करने की आवश्यकता होती है। आउटपुटः एक और नोड जो रीबैलेंस्ड एए ट्री का प्रतिनिधित्व करता है। यदि शून्य (टी) है तो शून्य लौटें अन्यथा शून्य (बाएं (टी)) है तो टी वापस करें अन्यथा यदि स्तर (बाएं (टी)) = = स्तर (टी) है तो क्षैतिज बाएं लिंक के संकेतों की अदला-बदली करें। एल = लेफ्ट (टी) लेफ्ट (टी): = राइट (एल) राइट (एल): = टी रिटर्न एल अन्यथा टी एंड लौटाता है यदि एंड फंक्शन स्क्यूः फंक्शन स्प्लिट इनपुट हैः टी, एक ए. ए. ट्री का प्रतिनिधित्व करने वाला नोड जिसे फिर से संतुलित करने की आवश्यकता होती है। आउटपुटः एक और नोड जो रीबैलेंस्ड एए ट्री का प्रतिनिधित्व करता है। यदि शून्य (टी) तो शून्य लौटें अन्यथा शून्य (दाएँ (टी)) या शून्य (दाएँ (टी)) तो टी लौटें अन्यथा यदि स्तर (टी) = = स्तर (दाएँ (टी)) तो हमारे पास दो क्षैतिज दाएँ लिंक हैं। बीच के नोड को लें, इसे ऊपर उठाएं और इसे वापस कर दें। आर = दाएँ (टी) दाएँ (टी): = बाएँ (आर) बाएँ (आर): = टी स्तर (आर): = स्तर (आर) + 1 वापसी आर अन्यथा टी अंत लौटाता है यदि अंतिम कार्य विभाजनः सम्मिलन सम्मिलन सामान्य द्विआधारी वृक्ष खोज और सम्मिलन प्रक्रिया के साथ शुरू होता है। फिर, जैसे ही कॉल स्टैक बंद होता है (खोज के पुनरावर्ती कार्यान्वयन को मानते हुए), पेड़ की वैधता की जांच करना और आवश्यकतानुसार कोई भी आवर्तन करना आसान होता है। यदि एक क्षैतिज बाएँ लिंक उत्पन्न होता है, तो एक तिरछा प्रदर्शन किया जाएगा, और यदि दो क्षैतिज दाएँ लिंक उत्पन्न होते हैं, तो एक विभाजन किया जाएगा, संभवतः वर्तमान सबट्री के नए रूट नोड के स्तर को बढ़ाते हुए। ध्यान दें, ऊपर दिए गए कोड में, स्तर (टी) की वृद्धि। इससे पेड़ की वैधता की जांच जारी रखना आवश्यक हो जाता है क्योंकि परिवर्तन पत्तियों से उभरते हैं। फंक्शन इन्सर्ट इनपुट हैः X, डालने के लिए मान, और T, इसे डालने के लिए ट्री का मूल। आउटपुटः एक्स सहित एक संतुलित संस्करण टी। सामान्य द्विआधारी वृक्ष प्रविष्टि प्रक्रिया करें। पुनरावर्ती कॉल के परिणाम को सही चाइल्ड पर सेट करें यदि एक नया नोड बनाया गया था या सबट्री का मूल बदल जाता है। यदि शून्य (टी) है तो एक्स के साथ एक नया लीफ नोड बनाएँ. रिटर्न नोड (एक्स, 1, नील, नील) अन्यथा यदि एक्स <मान (टी) है तो बाएँ (टी): = सम्मिलित करें (एक्स, बाएँ (टी)) अन्यथा यदि एक्स> मान (टी) है तो दाएँ (टी): = सम्मिलित करें (एक्स, दाएँ (टी)) समाप्त होता है यदि ध्यान दें कि एक्स = = मान (टी) का मामला अनिर्दिष्ट है। जैसा कि दिया गया है, एक प्रविष्टि का कोई प्रभाव नहीं होगा। कार्यान्वयनकर्ता अलग व्यवहार की इच्छा कर सकता है। तिरछा प्रदर्शन करें और फिर विभाजित करें। शर्तें जो यह निर्धारित करती हैं कि रोटेशन होगा या नहीं, वे प्रक्रियाओं के भीतर हैं, जैसा कि ऊपर दिया गया है। टीः = तिरछा (टी) टीः = विभाजित (टी) वापसी टी अंत कार्य विलोपन अधिकांश संतुलित द्विआधारी पेड़ों के रूप में, एक आंतरिक नोड के विलोपन को आंतरिक नोड को उसके निकटतम पूर्ववर्ती या उत्तराधिकारी के साथ अदला-बदली करके एक पत्ती नोड के विलोपन में बदला जा सकता है, जो इस बात पर निर्भर करता है कि पेड़ में या कार्यान्वयनकर्ता की सनक पर क्या है। पूर्ववर्ती को पुनः प्राप्त करना केवल एक बाएं लिंक और फिर शेष सभी दाएं लिंक का अनुसरण करने की बात है। इसी तरह, उत्तराधिकारी को एक बार दाएँ और बाएं जाकर पाया जा सकता है जब तक कि एक शून्य सूचक न मिल जाए। दो बच्चों वाले एक से अधिक स्तर के सभी नोड्स के एए गुण के कारण, उत्तराधिकारी या पूर्ववर्ती नोड स्तर 1 में होगा, जिससे उनका निष्कासन तुच्छ हो जाएगा। एक पेड़ को फिर से संतुलित करने के लिए, कुछ तरीके हैं। एंडरसन द्वारा अपने मूल लेख में वर्णित सबसे सरल है, और इसका वर्णन यहां किया गया है, हालांकि वास्तविक कार्यान्वयन अधिक अनुकूलित दृष्टिकोण का विकल्प चुन सकते हैं। हटाने के बाद, पेड़ की वैधता बनाए रखने के लिए पहला कदम किसी भी नोड के स्तर को कम करना है जिसके बच्चे उनके दो स्तर नीचे हैं, या जो लापता बच्चे हैं। फिर, पूरे स्तर को तिरछा और विभाजित किया जाना चाहिए। यह दृष्टिकोण अनुकूल था, क्योंकि जब वैचारिक रूप से निर्धारित किया जाता है, तो इसके तीन आसानी से समझे जाने वाले अलग-अलग चरण होते हैंः यदि उपयुक्त हो तो स्तर को कम करें। स्तर को तिरछा करें। स्तर को विभाजित करें। हालाँकि, हमें इस बार केवल एक नोड के बजाय पूरे स्तर को तिरछा और विभाजित करना होगा, जिससे हमारा कोड जटिल हो जाएगा। फंक्शन डीलीट इनपुट हैः X, हटाने के लिए मान, और T, ट्री का मूल जिससे इसे हटाया जाना चाहिए। आउटपुटः टी, संतुलित, मान एक्स के बिना. यदि शून्य (टी) तो टी अन्यथा वापस करें यदि एक्स> मान (टी) तो दाएँ (टी): = हटाएं (एक्स, दाएँ (टी)) अन्यथा यदि एक्स <मान (टी) तो बाएँ (टी): = हटाएं (एक्स, बाएँ (टी)) अन्यथा यदि हम एक पत्ती हैं, तो आसान है, अन्यथा पत्ती केस में कम हो जाते हैं। यदि पत्ता (टी) है तो दाएँ (टी) को वापस करें अन्यथा यदि शून्य (बाएँ (टी)) है तो एलः = उत्तराधिकारी (टी) दाएँ (टी): = हटाएँ (मान (एल), दाएँ (टी)) मान (टी): = मान (एल) अन्यथा एलः = पूर्ववर्ती (टी) बाएँ (टी): = हटाएँ (मान (एल), बाएँ (टी)) मान (टी): = मान (एल) समाप्त हो जाता है यदि वृक्ष को फिर से संतुलित करें। यदि आवश्यक हो तो इस स्तर में सभी नोड्स के स्तर को कम करें, और फिर नए स्तर में सभी नोड्स को तिरछा और विभाजित करें। टीः = कमी _ स्तर (टी) टीः = तिरछा (टी) सही (टी): = तिरछा (दाएं (टी)) अगर शून्य नहीं (दाएं (टी)) सही (दाएं (टी)): = तिरछा (दाएं (टी)) समाप्त होता है अगर टीः = विभाजन (टी) सही (टी): = विभाजन (दाएं (टी)) रिटर्न टी एंड फंक्शन फ़ंक्शन कमी _ स्तर इनपुट हैः टी, एक ट्री जिसके लिए हम लिंक को हटाना चाहते हैं जो स्तरों को छोड़ देते हैं। आउटपुटः टी अपने स्तर के साथ कम हो गया। होना चाहिए = न्यूनतम (स्तर (बाएँ (टी)), स्तर (दाएँ (टी))) + 1 यदि होना चाहिए <स्तर (टी) तो स्तर (टी): = होना चाहिए यदि होना चाहिए <स्तर (दाएँ (टी)) तो स्तर (दाएँ (टी)): = होना चाहिए अंत यदि अंत यदि लौटाता है टी अंत कार्य इस एल्गोरिथ्म द्वारा हटाने का एक अच्छा उदाहरण एंडरसन पेपर में मौजूद है। एक एए पेड़ का प्रदर्शन एक लाल-काले पेड़ के प्रदर्शन के बराबर है। जबकि एक ए. ए. वृक्ष लाल-काले वृक्ष की तुलना में अधिक घूर्णन करता है, सरल एल्गोरिदम तेज होते हैं, और ये सभी समान प्रदर्शन के परिणामस्वरूप संतुलित होते हैं। एक लाल-काला पेड़ एक ए. ए. पेड़ की तुलना में अपने प्रदर्शन में अधिक सुसंगत होता है, लेकिन एक ए. ए. पेड़ चपटा होता है, जिसके परिणामस्वरूप खोज का समय थोड़ा तेज होता है। लाल-काला पेड़ बी-पेड़ एवीएल पेड़ बलि का बकरा पेड़ संदर्भ बाहरी लिंक ए. एंडरसन भी देखें। संतुलित खोज वृक्षों ने सरल ए. एंडरसन को बनाया। द्विआधारी खोज वृक्ष बी. एस. टी. एल. बी. में खोज पर एक टिप्पणी-ट्राईजेज़डी. सी. ए. विज़ुअल 2007 1.5 द्वारा सी के लिए एक मुक्त स्रोत ए. ए. वृक्ष पुस्तकालय-ए. ए. वृक्ष संरचनाओं को शिक्षित करने के लिए ओपनसोर्स डेल्फी कार्यक्रम बहुत सारे कोड के साथ पूरी तरह से ट्यूटोरियल जूलियन वॉकर जिसमें एक व्यावहारिक कार्यान्वयन वस्तु उन्मुख कार्यान्वयन परीक्षणों के साथ एक द्विआधारी खोज वृक्ष डेटा संरचनाओं के प्रदर्शन व्यवहार पर एक निष्कर्ष (पृष्ठ 67-75)-ए. ए. वृक्षों, लाल-काले वृक्षों, ट्रेप, स्किप सूचियों और मूल वृक्षों की तुलना एक उद्देश्य-सी कार्यान्वयन पायथन खोज वृक्ष