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

चलो थोड़ा शुरू करते हैं

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

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

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

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

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

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

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

 int getsize(node* p) //    size,     (t=NULL) { if( !p ) return 0; return p->size; } void fixsize(node* p) //     { p->size = getsize(p->left)+getsize(p->right)+1; }

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

पेड़ की जड़ में डालें

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

उपप्रकार के आकार को समायोजित करने और नए पेड़ की जड़ को वापस करने के लिए मत भूलना:

 node* rotateright(node* p) //     p { node* q = p->left; if( !q ) return p; p->left = q->right; q->right = p; q->size = p->size; fixsize(p); return q; }

 node* rotateleft(node* q) //     q { node* p = q->right; if( !p ) return q; q->right = p->left; p->left = q; p->size = q->size; fixsize(q); return p; }

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

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

रैंडमाइज्ड इंसर्ट

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

 node* insert(node* p, int k) //       k   p { if( !p ) return new node(k); if( rand()%(p->size+1)==0 ) return insertroot(p,k); if( p->key>k ) p->left = insert(p->left,k); else p->right = insert(p->right,k); fixsize(p); return p; }

यह ट्रिक है ... आइए देखें कि यह कैसे काम करता है। 500 नोड्स के पेड़ के निर्माण का एक उदाहरण (बढ़ते क्रम में 0 से 499 तक की चाबियाँ प्राप्त की गईं)

यह कहने के लिए नहीं कि सुंदरता का आदर्श, लेकिन ऊंचाई स्पष्ट रूप से छोटा है। हम कार्य को जटिल करते हैं - हम 0 से 2 ¹⁴ -1 (आदर्श ऊंचाई 14 है) की कुंजी की आपूर्ति करके एक पेड़ का निर्माण करेंगे, और निर्माण प्रक्रिया के दौरान ऊंचाई को मापेंगे। विश्वसनीयता के लिए, हम एक हजार रन बनाते हैं और परिणाम को औसत करते हैं। हम निम्नलिखित ग्राफ प्राप्त करते हैं, जिस पर हमारे परिणाम मार्करों के साथ चिह्नित हैं, और ठोस रेखा [ 3 ] - h = 4.3ln (n) -1.9ln (ln (n)) - 4 से सैद्धांतिक अनुमान है। सबसे महत्वपूर्ण बात जो हम आकृति से देखते हैं वह है कि प्रायिकता सिद्धांत शक्ति है!

यह समझा जाना चाहिए कि प्रस्तावित ग्राफ बड़ी संख्या में गणनाओं के लिए पेड़ की ऊंचाई का औसत मूल्य दर्शाता है। और एक विशेष गणना में ऊँचाई कितनी भिन्न हो सकती है। उपरोक्त लेख में इस प्रश्न का उत्तर है। हम किसान का काम करेंगे और 4095 नोड्स डालने के बाद ऊंचाइयों के वितरण का एक हिस्टोग्राम बनाएंगे।

सामान्य तौर पर, कोई अपराध दिखाई नहीं देता है, वितरण पूंछ कम होती हैं - प्राप्त अधिकतम ऊंचाई 39 है, जो ~~अस्पताल के~~ औसत से काफी अधिक नहीं है।

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

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

दूसरी ओर, उसी सफलता के साथ, हम नोड q को नए पेड़ की जड़ बना सकते हैं। एक यादृच्छिक कार्यान्वयन में, इन विकल्पों के बीच का चुनाव यादृच्छिक रूप से किया जाता है। बाएं पेड़ का आकार n हो, और दायाँ m हो। तब p को प्रायिकता n / (n + m), और q को प्रायिकता m / (n + m) के साथ एक नई जड़ के साथ चुना जाता है।

 node* join(node* p, node* q) //    { if( !p ) return q; if( !q ) return p; if( rand()%(p->size+q->size) < p->size ) { p->right = join(p->right,q); fixsize(p); return p; } else { q->left = join(p,q->left); fixsize(q); return q; } }

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

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

जांच लें कि हटाने से पेड़ का संतुलन बिगड़ता नहीं है। ऐसा करने के लिए, 2 ¹⁵ कुंजी के साथ एक पेड़ बनाएं, फिर आधा हटा दें (0 से 2 से ¹⁴ -1 के मूल्यों के साथ) और ऊंचाइयों के वितरण को देखें ...

वस्तुतः कोई अंतर नहीं, जैसा कि "साबित" करने के लिए आवश्यक ...

एक निष्कर्ष के बजाय

यादृच्छिक बाइनरी खोज पेड़ों का निस्संदेह लाभ उनके कार्यान्वयन की सादगी और सुंदरता है। हालांकि, जैसा कि आप जानते हैं, मुफ्त केक मौजूद नहीं हैं। हम इस मामले में क्या भुगतान करते हैं? सबसे पहले, अतिरिक्त आकार के भंडारण के लिए अतिरिक्त मेमोरी। प्रति नोड एक पूर्णांक फ़ील्ड। लाल-काले पेड़ों में, कुछ कौशल के साथ, आप बिना किसी अतिरिक्त क्षेत्र के कर सकते हैं। दूसरी ओर, पेड़ का आकार पूरी तरह से बेकार जानकारी नहीं है, क्योंकि यह आपको संख्या (चयन कार्य या क्रमिक आँकड़ों की खोज) द्वारा डेटा तक पहुंच को व्यवस्थित करने की अनुमति देता है, जो हमारे पेड़ को, किसी भी तत्व को डालने और हटाने की क्षमता के साथ एक क्रमबद्ध सरणी में बदल देता है। दूसरे, यद्यपि लॉगरिदमिक समय काम कर रहा है, मुझे संदेह है कि आनुपातिकता निरंतर बड़ी होगी - लगभग सभी ऑपरेशन दो पास (ऊपर और नीचे) में किए जाते हैं, इसके अलावा, यादृच्छिक संख्याओं को सम्मिलित करना और हटाना आवश्यक है। अच्छी खबर है - सब कुछ खोज चरण में बहुत जल्दी से काम करना चाहिए। अंत में, गंभीर अनुप्रयोगों में ऐसे पेड़ों का उपयोग करने के लिए एक बुनियादी बाधा यह है कि लॉगरिदमिक समय की गारंटी नहीं है, हमेशा एक मौका है कि पेड़ खराब रूप से संतुलित होगा। सच है, हजारों नोड्स के साथ भी इस तरह की घटना की संभावना इतनी छोटी है कि, शायद, आप एक मौका ले सकते हैं ...

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

साहित्य

रॉबर्ट सेडविक, सी ++ एल्गोरिदम, एम ।: विलियम्स, 2011 - सिर्फ एक अच्छी किताब
मार्टिनेज, कॉनरोडो; रूरा, सल्वाडोर (1998), रैंडमाइज्ड बाइनरी सर्च ट्री , जर्नल ऑफ एसीएम (ACM प्रेस) 45 (2): 288–323 - मूल लेख
रीड, ब्रूस (2003), एक यादृच्छिक द्विआधारी खोज पेड़ की ऊंचाई , एसीएम 50 के जर्नल (3): 306–332 - पेड़ की ऊंचाई का अनुमान

यादृच्छिक खोज पेड़