एए-ट्री या सिंपल बाइनरी ट्री

हबीब ( यहां और यहां ) पर पहले से ही द्विआधारी पेड़ों के विषय पर चर्चा की गई है।



एए-ट्री के बारे में, यह कहा गया था कि "अतिरिक्त प्रतिबंध के कारण, संचालन लाल-काले पेड़ों (विश्लेषण किए जाने वाले मामलों की संख्या को कम करके) की तुलना में आसान है।"



हालांकि, यह मुझे लगता है कि एए पेड़ एक अलग लेख के हकदार हैं।



क्यों?



क्योंकि वास्तव में यह एक सरल कार्यान्वयन के साथ सबसे तेज़ (या सबसे तेज़) बाइनरी ट्री है।



मैं एवीएल और लाल-काले पेड़ में सम्मिलन और विलोपन एल्गोरिदम पर विचार करने के लिए इस लेख के दायरे के बाहर छोड़ दूंगा, लेकिन एक नियम के रूप में, उनका कार्यान्वयन तुच्छ नहीं है। क्यों?



जैसा कि आप जानते हैं, एक द्विआधारी पेड़ की मुख्य समस्या इसका संतुलन है, अर्थात, एक नियमित रूप से जुड़ी हुई सूची में अध: पतन के प्रतिरूप। आमतौर पर, जब एक पेड़ को संतुलित करते हैं, तो वर्टिकल की पारस्परिक व्यवस्था के लिए कई विकल्प होते हैं, जिनमें से प्रत्येक को अलग से एल्गोरिथ्म में ध्यान में रखा जाना चाहिए।



एए-ट्री का आविष्कार अर्ने एंडरसन द्वारा किया गया था, जिन्होंने फैसला किया कि पेड़ के संतुलन को सरल बनाने के लिए, किसी को एक शीर्ष स्तर की अवधारणा को पेश करना होगा। यदि आप एक पेड़ की जड़ से ऊपर से नीचे की ओर बढ़ने की कल्पना करते हैं (जो कि, पत्तियों पर खड़ा है), तो किसी भी पत्ती के शीर्ष का स्तर 1 होगा। अपने काम में, Arne एंडरसन एक सरल नियम देता है कि एक AA पेड़ को संतुष्ट करना चाहिए:



आप एक ही स्तर के एक और शीर्ष को एक शीर्ष पर संलग्न कर सकते हैं लेकिन केवल एक और केवल दाईं ओर ।



(अपने लेख में, एए-ट्री के लेखक 2-3 पेड़ों से संबंधित थोड़ी अलग शब्दावली का उपयोग करते हैं, लेकिन सार नहीं बदलता है)।



इस प्रकार, शिखर स्तर की शुरू की गई अवधारणा हमेशा वास्तविक शिखर ऊंचाई (जमीन से दूरी) के साथ मेल नहीं खाती है, लेकिन नियम "एक स्तर पर एक सही कनेक्शन" का पालन करते समय पेड़ संतुलन बनाए रखता है।



एए पेड़ को संतुलित करने के लिए, आपको केवल 2 ( दो ) संचालन की आवश्यकता है।



उन्हें नियम "एक सही एकल-स्तरीय कनेक्शन" से समझना आसान है: यह एक ही स्तर पर बाएं कनेक्शन का उन्मूलन और एक ही स्तर पर दो सही कनेक्शन का उन्मूलन है।



इन परिचालनों को क्रमशः तिरछा और विभाजित करने के मूल कार्य में नामित किया गया है। उपरोक्त आंकड़ों में, क्षैतिज तीर एक स्तर के कोने के बीच संबंध को दर्शाता है, और झुकाव (ऊर्ध्वाधर) - विभिन्न स्तरों के कोने के बीच।



तिरछा, एक ही स्तर पर बाएं लिंक का उन्मूलन





विभाजित, एक ही स्तर पर दो सही संबंधों को समाप्त करना





आइए देखें कि एए पेड़ में डालने और हटाने जैसा क्या दिखता है। कार्यान्वयन को सरल बनाने के लिए, हम नीचे के तल (" जमीन ") की अवधारणा को पेश करते हैं। उसका स्तर हमेशा 0 होता है और उसके बाएं और दाएं कनेक्शन उसके लिए इशारा करते हैं। सभी पत्ती कोने लिंक में 0 को संग्रहीत करने के बजाय नीचे की ओर संदर्भित करते हैं।



हैबे पर डेल्फी के हफ्तों के भीतर, स्रोत कोड डेल्फी के समान छद्मकोड के रूप में होगा ( कॉफी प्रेमियों के लिए C ++: ऑपरेशन P ^ .x डेल्फी में P-> x के बराबर है, इसका मतलब है कि चर संदर्भ से पारित किया गया है, और मूल्य से नहीं। यानी, बदलते समय, बाहरी परिवर्तनशील परिवर्तन)।



एए-ट्री के शीर्ष को परिभाषित करें।

PNode = ^ TNode ;

TNode = पैक रिकॉर्ड

बाएं , दाएं : PNode ;

स्तर : पूर्णांक ; // स्केल; पत्तियों पर 1

कुंजी : सूचक ; // कुंजी, डेटा शीर्ष के साथ जुड़ा हुआ है

अंत ;

नए तत्व को सम्मिलित करना सबसे आसानी से एक पुनरावर्ती कार्यान्वयन में दिखता है।

प्रक्रिया NodeInsert ( var P : PNode ; newkey : सूचक ) ;

शुरू करना

यदि पी = नीचे तो शुरू / शुरू नीचे तक पहुंच गया - एक नया शीर्ष बनाएं

नया ( पी ) ;

पी ^ । बाएँ : = नीचे ;

पी ^ । सही : = नीचे ;

पी ^ । स्तर : = 1 ;

पी ^ । कुंजी : = newkey ;

अंत और शुरू

अगर newkey <p ^ । फिर चाबी

NodeInsert ( पी ^ । लेफ्ट , न्यूकी )

और अगर newkey> P ^ । फिर चाबी

NodeInsert ( P ^ । सही , newkey )

और शुरू करें

पी ^ । कुंजी : = newkey ;

बाहर निकलने के;

अंत ;

तिरछा ( पी ) ;

स्प्लिट ( पी ) ;

अंत ;

अंत ;

पेड़ में newkey कुंजी डालने के लिए, NodeInsert (रूट, newkey) को कॉल करें। हम पेड़ों की जड़ से नीचे जाते हैं, चाबी की तुलना करते हैं; पेस्ट; ऊपर जाएं और संतुलन बनाएं: प्रत्येक शीर्ष के लिए तिरछा और विभाजित करें।



निकालना थोड़ा मुश्किल है।

प्रक्रिया NodeDelete ( var P : PNode ; newkey : सूचक ) ;

शुरू करना



यदि P <> नीचे है तो शुरू करें



// 1. नीचे जाएं और आखिरी और डिलीट को याद रखें

अंतिम : = पी ;

अगर तुलना करें ( newkey , P ) < 0 तो // newkey <key

NodeDelete ( पी ^ । लेफ्ट , न्यूकी )

और शुरू करें

हटा दिया गया : = पी ;

नोडडेलेट ( पी ^ । राइट , न्यूकी ) ;

अंत ;



// 2. अगर पाया गया तत्व को हटा दें

यदि ( P = अंतिम ) और ( हटाए गए <> तल ) और ( newkey == हटाए गए कुंजी । ) तो शुरू करें

हटा दिया गया । कुंजी : = पी ^ । कुंजी ;

हटा दिया : = नीचे ;

P : = P ^ । सही ;

अंतिम हटाएं ;

अंत में अगर ( P ^ । बाएँ । स्तर <P ^ । स्तर - 1 ) या ( P ^ । दायाँ । स्तर <P ^ । स्तर - 1 ) फिर शुरू करें।

// 3. ऊपर जाते समय संतुलन का प्रदर्शन करें

दिसंबर ( पी ^ स्तर ) ;

यदि पी ^ । सही है । स्तर > पी ^ । स्तर तब पी ^ । सही है । स्तर : = पी ^ । स्तर ;

तिरछा ( पी ) ;

तिरछा ( पी ^ अधिकार ) ;

तिरछा ( पी ^ । राइट ^ राइट ) ;

स्प्लिट ( पी ) ;

स्प्लिट ( पी ^ । राइट ) ;

अंत ;

अंत ;



अंत ;

दो सहायक चर का उपयोग किया जाता है - हटाए गए और अंतिम। जब पेड़ के नीचे उतरते हैं (प्रविष्टि के दौरान), हटाए गए कुंजी के साथ वर्टेक्स कुंजी की तुलना की जाती है। यदि शीर्ष कुंजी को हटाए गए से कम है, तो बाएं लिंक पर जाएं, अन्यथा - दाईं ओर (यानी, कुंजी मिलान होने पर भी दाईं ओर जाएं)। अंत में, प्रत्येक ट्रैवर्स किए गए शीर्ष को दर्ज किया जाता है, और हटाए जाने में - केवल एक ही जहां "सही निकला।"



जब पेड़ के नीचे पहुंच जाता है, तो हटाए गए बिंदु को उस शीर्ष बिंदु पर पहुंचा दिया जाता है जहां हटाए जाने की कुंजी स्थित होती है (यदि वह पेड़ में है), और अंतिम इंगित करता है कि हटाए जाने वाला शीर्ष (यह वही शीर्ष हो सकता है)। कुंजी को पिछली से हटा दिया गया है और अंतिम शीर्ष हटा दिया गया है।



अगला, संतुलन किया जाता है - आपको 3 तिरछा और 2 विभाजन करने की आवश्यकता है।



तिरछा और विभाजन का कार्यान्वयन आम बात है।

// रिकॉर्ड के _content_ को स्वैप करें (पॉइंटर्स नहीं)

प्रक्रिया स्वैप ( P1 , P2 : PNode ) ;

वर

tmp : TNode ;

शुरू करना

tmp : = P1 ^ ;

पी 1 ^ : = पी 2 ^ ;

P2 ^ : = tmp ;

अंत ;



प्रक्रिया तिरछा ( टी : PNode ) ;

वर

एल : पीयोड ;

शुरू करना

एल : = टी ^ । छोड़ दिया ;

यदि टी ^ । स्तर = एल ^ । स्तर तब शुरू होता है

स्वैप ( टी , एल ) ; // अब टी ==> एल, एल ==> टी

एल ^ । बायां : = टी ^ । सही ; // अर्थात T.left = L.right

टी ^ । सही : = एल ; // अर्थात L.right = T

अंत ;

अंत ;



प्रक्रिया भाजित ( टी : PNode ) ;

वर

आर : पीनोड ;

शुरू करना

आर : = टी ^ । सही ;

यदि टी ^ । स्तर = आर ^ । सही ^ स्तर तब शुरू होता है

स्वैप ( टी , आर ) ; // अब टी ==> आर, आर ==> टी

आर ^ । सही : = टी ^ । छोड़ दिया ;

टी ^ । बायां : = आर ;

इंक ( टी ^ स्तर ) ;

अंत ;

अंत ;

वास्तव में, दिए गए छद्म कोड एक एए-ट्री कार्यान्वयन (केवल "छोटी चीजें जोड़ें" जैसे एक पेड़ की जड़ (जड़), आदि को बनाने के लिए पर्याप्त है)।



कुछ उपयोगी लिंक



सी में एए पेड़ का कार्यान्वयन ।



एक अद्भुत ऐपलेट जिसमें आप विभिन्न प्रकार के पेड़ों (एए पेड़ों सहित) के साथ खेल सकते हैं।



एए पेड़ दृश्य और स्रोत कोड के साथ डेल्फी परियोजना ।



विकिपीडिया लेख ।