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

एवीएल पेड़ की अवधारणा

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

एवीएल पेड़ की एक विशेषता यह है कि यह निम्नलिखित अर्थों में संतुलित है: किसी भी पेड़ के नोड के लिए, इसके दाएं उप-वर्ग की ऊँचाई बाईं सबट्री की ऊंचाई से भिन्न होती है जो एक से अधिक नहीं होती है । यह साबित होता है कि यह संपत्ति पेड़ की ऊंचाई के लिए पर्याप्त रूप से तार्किक रूप से इसके नोड्स की संख्या पर निर्भर करती है: एवीएल पेड़ की ऊँचाई एच कुंजी के साथ n की सीमा ₂ लॉग (n + 1) से लेकर 1.44 लॉग ₂ (n + 2) - 0.328 तक है। और चूंकि बाइनरी सर्च ट्री (नोड्स की खोज, प्रविष्टि और विलोपन) पर बुनियादी संचालन रैखिक रूप से इसकी ऊंचाई पर निर्भर करता है, इसलिए हम इन एल्गोरिदम के ऑपरेटिंग समय की एक गारंटीकृत लॉगरिदमिक निर्भरता प्राप्त करते हैं जो कि पेड़ में संग्रहीत चाबियों की संख्या पर निर्भर करती है। याद रखें कि यादृच्छिक खोज वाले पेड़ केवल संभाव्य अर्थों में संतुलन प्रदान करते हैं: बड़े n के लिए अत्यधिक असंतुलित वृक्ष प्राप्त करने की संभावना, हालांकि यह नगण्य है, गैर-शून्य रहता है ।

नोड संरचना

हम निम्नलिखित संरचना के साथ AVL पेड़ के नोड्स का प्रतिनिधित्व करेंगे:

struct node //      { int key; unsigned char height; node* left; node* right; node(int k) { key = k; left = right = 0; height = 1; } }; 

मुख्य फ़ील्ड नोड कुंजी को संग्रहीत करता है, ऊंचाई फ़ील्ड दी गई नोड में रूट के साथ सबट्री की ऊंचाई है, बाएं और दाएं फ़ील्ड बाएं और दाएं उपशीर्षक के लिए संकेत हैं। एक साधारण कंस्ट्रक्टर दिए गए कुंजी k के साथ एक नया नोड (ऊंचाई 1) बनाता है।

परंपरागत रूप से, एवीएल पेड़ के नोड्स ऊंचाई को स्टोर नहीं करते हैं, लेकिन दाएं और बाएं उपप्रकारों (तथाकथित संतुलन कारक) की ऊंचाइयों में अंतर, जो केवल तीन मान ले सकता है -1, 0 और 1. हालांकि, ध्यान दें कि यह अंतर अभी भी एक चर में संग्रहीत है जिसका आकार कम से कम एक बाइट के बराबर है (जब तक कि आप इस तरह के मूल्यों की "प्रभावी" पैकेजिंग की कुछ मुश्किल योजनाओं के साथ नहीं आते हैं)। याद रखें कि ऊंचाई h <1.44 लॉग ₂ (n + 2), जिसका अर्थ है, उदाहरण के लिए, कि n = 10 ⁹ (एक बिलियन कुंजी, नोड्स को संचय करने के लिए 10 गीगाबाइट से अधिक मेमोरी) के लिए पेड़ की ऊंचाई = 44 से अधिक नहीं होगी, जो संतुलन कारक के रूप में स्मृति के एक ही बाइट में सफलतापूर्वक रखा गया। इस प्रकार, एक तरफ हाइट्स को स्टोर करने से ट्री नोड्स के लिए आवंटित मेमोरी की मात्रा में वृद्धि नहीं होती है, लेकिन दूसरी तरफ कुछ संचालन के कार्यान्वयन को महत्वपूर्ण रूप से सरल करता है।

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

 unsigned char height(node* p) { return p?p->height:0; } 

दूसरा दिए गए नोड के संतुलन कारक की गणना करता है (और केवल गैर-शून्य पॉइंटर्स के साथ काम करता है):

 int bfactor(node* p) { return height(p->right)-height(p->left); } 

तीसरा फ़ंक्शन दिए गए नोड के ऊंचाई क्षेत्र के सही मूल्य को पुनर्स्थापित करता है (बशर्ते कि दाएं और बाएं बच्चे के नोड में इस क्षेत्र के मूल्य सही हैं):

 void fixheight(node* p) { unsigned char hl = height(p->left); unsigned char hr = height(p->right); p->height = (hl>hr?hl:hr)+1; } 

ध्यान दें कि सभी तीन कार्य गैर-पुनरावर्ती हैं, अर्थात्। उनका परिचालन समय O (1) का मान है।

नोड संतुलन

एवीएल पेड़ में नोड्स जोड़ने या हटाने की प्रक्रिया में, एक स्थिति उत्पन्न हो सकती है जब कुछ नोड्स का संतुलन कारक 2 या -2 हो जाता है, अर्थात। उपसर्ग का असंतुलन है । स्थिति को ठीक करने के लिए, कुछ पेड़ के नोड्स के आसपास प्रसिद्ध घुमाव का उपयोग किया जाता है। मैं आपको याद दिलाता हूं कि दाएं (बाएं) के लिए एक साधारण मोड़ निम्नलिखित पेड़ परिवर्तन का उत्पादन करता है:



सही मोड़ को लागू करने वाला कोड निम्नानुसार दिखता है (सामान्य रूप से, पेड़ को संशोधित करने वाले प्रत्येक फ़ंक्शन परिणामी पेड़ की एक नई जड़ देता है:

 node* rotateright(node* p) //    p { node* q = p->left; p->left = q->right; q->right = p; fixheight(p); fixheight(q); return q; } 

बाईं ओर दाईं ओर सममित प्रति है:

 node* rotateleft(node* q) //    q { node* p = q->right; q->right = p->left; p->left = q; fixheight(q); fixheight(p); return p; } 

आइए अब एक असंतुलन की स्थिति पर विचार करें, जब नोड पी के दाहिने उपप्रकार की ऊंचाई बाएं उपरी की ऊंचाई से 2 अधिक है (विपरीत मामला सममित है और इसी तरह लागू किया गया है)। बता दें कि q नोड नोड का दायां बच्चा है और नोड q के बाएं बच्चे का नाम है।



इस स्थिति के ढांचे के भीतर संभावित मामलों के विश्लेषण से पता चलता है कि नोड पी में असंतुलन को ठीक करने के लिए, यह पी के चारों ओर एक साधारण बाएं मोड़ या एक ही पी के चारों ओर एक तथाकथित बड़े बाएं मोड़ को करने के लिए पर्याप्त है। एक साधारण घुमाव प्रदान किया जाता है बशर्ते कि नोड q के बाएँ उपप्रकार की ऊँचाई उसकी दाईं उपरी की ऊँचाई से अधिक हो: h (s) (h (D)।



हालत एच (एस)> एच (डी) के तहत एक बड़ा रोटेशन लागू किया जाता है और इस मामले में दो सरल लोगों में घटाया जाता है - पहले, क्यू के चारों ओर एक सही रोटेशन और फिर पी के चारों ओर एक बाएं रोटेशन।



संतुलन बनाने वाला कोड स्थितियों की जाँच करने और मोड़ करने के लिए नीचे आता है:

 node* balance(node* p) //   p { fixheight(p); if( bfactor(p)==2 ) { if( bfactor(p->right) < 0 ) p->right = rotateright(p->right); return rotateleft(p); } if( bfactor(p)==-2 ) { if( bfactor(p->left) > 0 ) p->left = rotateleft(p->left); return rotateright(p); } return p; //    } 

रोटेशन और संतुलन के वर्णित कार्यों में भी चक्र या पुनरावृत्ति शामिल नहीं है, जिसका अर्थ है कि वे निरंतर समय के लिए प्रदर्शन किए जाते हैं, एवीएल पेड़ के आकार से स्वतंत्र होते हैं।

मुख्य प्रविष्टि

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

 node* insert(node* p, int k) //   k     p { if( !p ) return new node(k); if( k<p->key ) p->left = insert(p->left,k); else p->right = insert(p->right,k); return balance(p); } 

एवीएल पेड़ों की ऊंचाई के लिए सैद्धांतिक अनुमानों को कार्यान्वित सम्मिलन एल्गोरिदम के पत्राचार की जांच करने के लिए, एक सरल कम्प्यूटेशनल प्रयोग किया गया था। एक सरणी को यादृच्छिक रूप से स्थित संख्याओं से 1 से 10,000 तक उत्पन्न किया गया था, फिर इन संख्याओं को क्रमिक रूप से शुरू में खाली AVL पेड़ में डाला गया और प्रत्येक सम्मिलन के बाद पेड़ की ऊंचाई को मापा गया। परिणाम 1000 से अधिक गणनाओं में औसत थे। निम्नलिखित ग्राफ औसत ऊंचाई (लाल रेखा) के एन पर निर्भरता को दर्शाता है; न्यूनतम ऊंचाई (हरी रेखा); अधिकतम ऊंचाई (नीली रेखा)। इसके अलावा, ऊपरी और निचले सैद्धांतिक अनुमान दिखाए जाते हैं।



यह देखा जा सकता है कि चाबियों के यादृच्छिक क्रम के लिए, प्रायोगिक रूप से पाई जाने वाली ऊंचाइयां एक छोटे से मार्जिन के साथ भी सैद्धांतिक सीमाओं में आती हैं। यदि मूल कुंजी अनुक्रम आरोही क्रम में आदेश दिया जाता है, तो एक निचली सीमा प्राप्त करने योग्य होती है (कम से कम कुछ बिंदुओं पर)।

कुंजी निकालना

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

लागू करते समय, कई बारीकियां हैं। सबसे पहले, अगर पाया गया नोड पी में एक सही उपप्रकार नहीं है, तो बाईं ओर एवीएल पेड़ की संपत्ति के द्वारा, इस नोड में केवल एक ही बच्चा नोड (ऊंचाई 1 का पेड़) हो सकता है, या सामान्य रूप से नोड पी एक पत्ती है। इन दोनों मामलों में, आपको केवल नोड पी को हटाना होगा और परिणाम के रूप में नोड पी के बाएं बच्चे के नोड को पॉइंटर वापस करना होगा।

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

 node* findmin(node* p) //        p { return p->left?findmin(p->left):p; } 

एक और उपयोगिता कार्य किसी दिए गए पेड़ से न्यूनतम तत्व को हटाने के लिए होगा। एवीएल पेड़ की संपत्ति द्वारा, फिर से दाईं ओर न्यूनतम तत्व या तो एक नोड निलंबित है या वहां खाली है। दोनों ही मामलों में, आपको केवल पॉइंटर को दाएं नोड में वापस करने की जरूरत है और वापस आने पर (जब रिकर्सन से लौटते समय) बैलेंसिंग करना है। कम से कम नोड को ही हटाया नहीं जाता है, क्योंकि वह अभी भी हमारे लिए उपयोगी है।

 node* removemin(node* p) //        p { if( p->left==0 ) return p->right; p->left = removemin(p->left); return balance(p); } 

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

 node* remove(node* p, int k) //   k   p { if( !p ) return 0; if( k < p->key ) p->left = remove(p->left,k); else if( k > p->key ) p->right = remove(p->right,k); 

एक बार कुंजी k मिल जाने के बाद, B पर जाएं: नोड p के बाएं और दाएं उप-वर्ग की जड़ों को याद रखें; नोड पी हटाएं; यदि सही सबट्री खाली है, तो पॉइंटर को बाईं सबट्री पर लौटा दें; यदि सही सबट्री खाली नहीं है, तो हम वहां न्यूनतम तत्व मिनट पाते हैं, फिर हम इसे वहां से निकालते हैं, q को बाएं से मिनट तक लटकाते हैं, और r से दाईं ओर क्या निकला, इसे संतुलित करने के बाद मिनट वापस करते हैं।

  else // k == p->key { node* q = p->left; node* r = p->right; delete p; if( !r ) return q; node* min = findmin(r); min->right = removemin(r); min->left = q; return balance(min); } 

जब आप पुनरावृत्ति से बाहर निकलते हैं, तो संतुलन करना न भूलें:

  return balance(p); } 

बस इतना ही! न्यूनतम नोड और इसके निष्कर्षण की खोज, सिद्धांत रूप में, एक फ़ंक्शन में कार्यान्वित की जा सकती है, और आपको फ़ंक्शन से पॉइंटर्स की एक जोड़ी को वापस करने की (बहुत मुश्किल नहीं) समस्या को हल करना होगा। लेकिन आप सही सबट्री पर एक पास को बचा सकते हैं।

स्पष्ट रूप से, सम्मिलित करें और हटाएं ऑपरेशन (साथ ही सरल खोज ऑपरेशन) को पेड़ की ऊंचाई के आनुपातिक समय में किया जाता है, क्योंकि इन ऑपरेशनों को करने की प्रक्रिया में, किसी दिए गए नोड के मूल से एक वंश का प्रदर्शन किया जाता है, और प्रत्येक स्तर पर निश्चित संख्या में क्रियाएं की जाती हैं। और इस तथ्य के कारण कि एवीएल पेड़ संतुलित है, इसकी ऊंचाई नोड्स की संख्या पर लघु रूप से निर्भर करती है। इस प्रकार, सभी तीन बुनियादी कार्यों के निष्पादन का समय पेड़ के नोड्स की संख्या पर लघु रूप से निर्भर करने की गारंटी है।

आपका ध्यान देने के लिए आप सभी का धन्यवाद!

सूत्रों का कहना है

• बी। Pfaff, बाइनरी सर्च ट्रीज़ और बैलेंस्ड ट्रीज़ का एक परिचय - लिबाव्ल लाइब्रेरी विवरण
• एन। विर्थ, एल्गोरिदम और डेटा संरचना - पुण्य के अनुसार संतुलित पेड़ - ये सिर्फ एवीएल पेड़ हैं
• टी। कोरमेन एट अल।, एल्गोरिदम: निर्माण और विश्लेषण - एबीएल के पेड़ लाल-काले पेड़ों पर अध्याय के अभ्यास में वर्णित हैं
• डी। नॉट, द आर्ट ऑफ़ प्रोग्रामिंग - धारा 6.2.3 एवीएल पेड़ों के सैद्धांतिक विश्लेषण के लिए समर्पित है।