AVL पेड़ और उनके आवेदन की चौड़ाई

मैंने अपनी राय में सबसे उपयोगी पेड़ संरचना में थोड़ा वर्णन करने का निर्णय लिया। एवीएल पेड़ एक द्विआधारी पेड़ है (प्रत्येक शीर्ष पर 2 बेटों से अधिक नहीं है), जिसमें एक पहचानकर्ता को प्रत्येक शीर्ष (यह वह पेड़ है जो इसे संग्रहीत करता है) को सौंपा गया है, पहचानकर्ता निम्नलिखित नियम का पालन करते हैं: बाएं बेटा आईडी <माता-पिता "सही बेटा आईडी।
यानी अगर हम पेड़ के चारों ओर बाएं से दाएं घूमते हैं, तो हमें आरोही क्रम में एक आईडी मिल जाएगी, दाएं से बाएं - अवरोही क्रम में।
इसके अलावा, पेड़ जितना संभव हो उतना संतुलित होता है: बाएं सबट्री की ऊंचाई अधिकतम 1 से दाएं की ऊंचाई से भिन्न होती है।

इसमें जो दिलचस्प है वह यह है कि तब पेड़ में एक तत्व के अस्तित्व की जांच करने के लिए लॉग (एन) एन लेता है - आईडी की संख्या। आखिरकार, आपको जड़ से नीचे जाने की जरूरत है, और चूंकि पेड़ यथासंभव सममित है, इसकी ऊंचाई लॉग (एन) +1 है
अच्छी खबर यह है कि कोई भी हमें किसी अन्य उपयोगी डेटा को वर्टेक्स में संलग्न करने से मना नहीं करता है, और फिर आईडी द्वारा मनमाने डेटा का चयन लॉग (एन) समय लेगा
बुरी खबर यह है कि परिभाषा के अनुसार, समान आईडी, इसमें मौजूद नहीं हो सकती है। आपको अपने कानों के साथ एक फिंट करना है, एक तरीका है कि प्रत्येक शीर्ष के बजाय एक ही आईडी के साथ कोने की सूची बनाई जाए, और दूसरा संतुलन एल्गोरिथ्म को बदलना है।

एक और संपत्ति - आप दिए गए सरणी के तत्वों को जल्दी से सबसे करीब से पा सकते हैं, लेकिन इससे कम, या अधिक - कुछ कार्यों के लिए यह बहुत महत्वपूर्ण है।

यह दिलचस्प है: जाहिर है, पहचानकर्ताओं की सूची से इस तरह के एक पेड़ का निर्माण किया जा सकता है, लेकिन यह भी पता चलता है कि आप बहुत कम समय में तत्वों को जल्दी से जोड़ सकते हैं और जल्दी से हटा सकते हैं <= log (N) (add)

इस प्रकार, एन तत्वों की एक सरणी को सॉर्ट करने के लिए, आप बस इसे पेड़ में जोड़ सकते हैं - एन * लॉग (एन) और फिर बाएं से दाएं घूमें - एन यानी। कुल समय एन * लॉग (एन) - और हमने एक और बहुत तेज़ सरणी छँटाई विधि बनाई

वैसे, सुविधा के लिए कुछ और संचालन - चूंकि हम जल्दी से वांछित आईडी के साथ शीर्ष की तलाश करते हैं, इसलिए हम सेट और गेट ऑपरेशंस को प्रदर्शन करने के लिए शीर्ष पर डेटा फ़ील्ड को बदल देंगे। इस प्रकार, हम <= log (N) मेमोरी में दिए गए आईडी के अनुरूप डेटा भी अपडेट करते हैं

मैं बहुत बार AVL पेड़ का उपयोग करता हूं: यहां तक ​​कि मानक CRC हैश में भी, मैं CRC समूहों को पेड़ में संग्रहीत करता हूं, सरणियों और सूचियों को सॉर्ट करता हूं, सरणी में तत्वों के अस्तित्व की जांच करने के लिए इसका उपयोग करता हूं, डेटाबेस अनुक्रमित करता हूं, उन्हें खोज परिणाम सॉर्ट करता हूं (जैसा कि ऊपर वर्णित है), अंत में। , यह सीधे एक फ़ाइल में लिखा जा सकता है और इससे भी अधिक गति के लिए पढ़ा जा सकता है।
सामान्य तौर पर, यह संरचना सूची की तुलना में बहुत बड़ी नहीं है, लेकिन आपको सैकड़ों गुना अधिक संचालन करने की अनुमति देती है, अर्थात। 1-2 लिंक्ड सूची में एक अच्छा विकल्प।

अब पेड़ को कैसे जोड़ा जाए, इसके बारे में थोड़ा सा विवरण सार्वजनिक डोमेन में बहुत सारे हैं, इसलिए संक्षेप में:
हम प्रत्येक शीर्ष पर संख्या संतुलन का परिचय देते हैं, जो दिखाता है कि ऊपर दिए गए उप-भागों में से कौन सा बाएं या दाएं है।
जब आप एक पेड़ में एक शीर्ष जोड़ते हैं, तो यह कभी-कभी असंतुलित हो जाता है। जोड़ने की प्रक्रिया सरल है - हम नियम का उपयोग करके पेड़ के बहुत नीचे तक जाते हैं
बाएं बेटे की आईडी <माता-पिता की आईडी <सही बेटा आईडी, यानी। यदि नई आईडी <वर्टेक्स आईडी बाईं ओर जाती है, अन्यथा दाईं ओर। नीचे की चोटी पर एक बेटे को जोड़ते हुए, हमें अपने रास्ते के साथ संतुलन सूचक को अपडेट करने की आवश्यकता है जो हम जा रहे थे - हम वंश के साथ ऐसा कर सकते हैं, हम ऊपर की ओर वापस जा सकते हैं - अगर हम बाएं उप-वर्ग से आए हैं तो शेष राशि - अन्यथा शेष ++
अगर किसी स्तर पर हमें संतुलन मिला है = 0 - तो सबट्री संतुलित है और आप जोड़ना समाप्त कर सकते हैं (शीर्ष पर पूरे पेड़ को पुनर्गणना करने की आवश्यकता नहीं है क्योंकि उपरी की ऊंचाई नहीं बदली है - वहाँ संतुलन = -1 बन गया 0 - बाएं सबट्री outweighed, दाईं ओर जोड़ा गया और संरेखित, या संतुलन = 1 0 बन गया - दायाँ उपरी भाग आगे निकल गया, बाईं और जोड़ दिया गया)

खैर, सबसे दिलचस्प बात यह है कि सबट्री को संतुलित किया जा रहा है अगर रास्ते में कुछ कदम पर हमें संतुलन = -2 या 2 मिला है, जिसका अर्थ है कि पेड़ का आधा हिस्सा दृढ़ता से निकल गया है, और आपको एक निश्चित मोड़ बनाने की आवश्यकता है - 1 लिंक द्वारा बढ़ाएं, उदाहरण के लिए, सही एक और बाईं ओर लम्बा। पूरा मोड़ परिस्थितियों की जांच करने और लिंक को फिर से व्यवस्थित करने के लिए नीचे आता है, मैंने व्यक्तिगत रूप से इसे अपने लिए कागज के एक टुकड़े पर समझा - केवल 3 संभव विकल्प हैं, जो मैं आपको बेहतर जागरूकता के लिए सलाह देता हूं - मैं यहां विशेष रूप से व्यक्त नहीं करूंगा कि क्या खींचा जा सकता है, और अगर यह पूरी तरह से आलस्य है, तो इंटरनेट पर तैयार समाधान खोजें।

खोज इंजन पर मेरे लेखों की पूरी सामग्री और सूची यहां अपडेट की जाएगी: http://habrahabr.ru/blogs/search_engines/123671/