data structures red आरबी पेड़, बी-ट्री या एवीएल पेड़ कब चुनना है?




red black tree example (4)

एक प्रोग्रामर के रूप में मुझे आरबी पेड़, बी-पेड़ या एवीएल पेड़ का उपयोग करने पर विचार करना चाहिए? चुनाव पर निर्णय लेने से पहले महत्वपूर्ण बिंदुओं पर विचार करने की आवश्यकता क्या है?

क्या कोई प्रत्येक वृक्ष संरचना के लिए परिदृश्य के साथ समझा सकता है क्यों इसे मुख्य बिंदुओं के संदर्भ में दूसरों पर चुना जाता है?


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

बी + पेड़ों में समस्याएं होती हैं, हालांकि - जैसे कि जब आप इनर्ट्स / डिलीट करते हैं तो आइटम नोड्स के चारों ओर घूमते हैं, उन आइटम्स को पॉइंटर्स को अमान्य कर देते हैं। मेरे पास एक कंटेनर लाइब्रेरी है जो "कर्सर रखरखाव" करती है - कर्सर स्वयं को उस लिंक्ड सूची में संदर्भित करते हैं जो वे वर्तमान में एक लिंक्ड सूची में संदर्भित करते हैं, इसलिए उन्हें स्वचालित रूप से तय या अमान्य किया जा सकता है। चूंकि वहां शायद ही कभी एक या दो कर्सर हैं, यह अच्छी तरह से काम करता है - लेकिन यह सब कुछ एक ही काम है।

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

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

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

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


इसे नमक के चुटकी से लें:

बी-पेड़ जब आप हजारों से अधिक वस्तुओं का प्रबंधन कर रहे हैं और आप उन्हें डिस्क या कुछ धीमी स्टोरेज माध्यम से पेजिंग कर रहे हैं।

आरबी पेड़ जब आप पेड़ पर काफी बार आवेषण, हटाना और पुनर्प्राप्ति कर रहे हैं।

एवीएल पेड़ जब आपके आवेषण और हटाना आपके पुनर्प्राप्ति के सापेक्ष कम होते हैं।


स्मृति में बी-ट्री का लाभ तब होता है जब वस्तुओं की संख्या 32000 से अधिक है ... stx-btree से speedtest.pdf को देखो।


डेटा संरचनाओं को चुनते समय आप कारकों से व्यापार कर रहे हैं जैसे कि

  • अद्यतन की पुनर्प्राप्ति वी गति की गति
  • संरचना सबसे बुरी स्थिति संचालन के साथ कितनी अच्छी तरह से copes, उदाहरण के लिए एक क्रमबद्ध क्रम में आने वाले रिकॉर्ड सम्मिलन
  • अंतरिक्ष बर्बाद हो गया

मैं रॉबर्ट हार्वे द्वारा संदर्भित विकिपीडिया लेखों को पढ़कर शुरू करूंगा।

व्यावहारिक रूप से, जावा जैसे भाषाओं में काम करते समय औसत प्रोग्रामर प्रदान किए गए संग्रह वर्गों का उपयोग करता है। यदि प्रदर्शन ट्यूनिंग गतिविधि में कोई पता चलता है कि संग्रह प्रदर्शन समस्याग्रस्त है तो कोई वैकल्पिक कार्यान्वयन की तलाश कर सकता है। व्यापारिक नेतृत्व वाले विकास पर विचार करना शायद ही कभी पहली बात है। यह बेहद दुर्लभ है कि किसी को ऐसे डेटा संरचनाओं को हाथ से लागू करने की आवश्यकता होती है, आमतौर पर पुस्तकालयों का उपयोग किया जा सकता है।





red-black-tree