क्या कोई यह बता सकता है कि इन दो डेटा संरचनाओं के बीच मुख्य अंतर क्या हैं? मैं ऑनलाइन स्रोत ढूंढने की कोशिश कर रहा हूं जो अंतर/समानताओं को हाइलाइट करता है, लेकिन मुझे कुछ भी जानकारीपूर्ण नहीं मिला है। दूसरे मामलों में किसी को किस मामले में प्राथमिकता दी जाएगी? क्या व्यावहारिक स्थितियां दूसरे की तुलना में एक "बेहतर" उपयोग करती हैं?लाल-काले पेड़ों और एवीएल पेड़ों के बीच अंतर
इस से हवाला देते हुए: Difference between AVL and Red-Black Trees
आरबी-पेड़ हैं, साथ ही AVL पेड़, आत्म संतुलन। उनमें से दोनों ओ (लॉग एन) लुकअप और सम्मिलन प्रदर्शन प्रदान करते हैं। अंतर यह है कि आरबी-पेड़ प्रति सम्मिलन ऑपरेशन ओ (1) घूर्णन की गारंटी देता है। वास्तविक कार्यान्वयन में वास्तव में प्रदर्शन की लागत यही है। सरलीकृत, आरबी-पेड़ गतिशील नोड संरचनाओं के ऊपरी हिस्से के चारों ओर ले जाने के बिना अवधारणात्मक रूप से 2-3 पेड़ होने से यह लाभ प्राप्त करते हैं। शारीरिक रूप से आरबी-पेड़ बाइनरी पेड़ों के रूप में लागू किए जाते हैं, लाल/काले-झंडे 2-3 व्यवहार अनुकरण करते हैं।
परिभाषा के अनुसार, प्रत्येक एवीएल इसलिए लाल-काले रंग का उप-समूह है। किसी को किसी भी एवीएल पेड़ को बिना किसी पुनर्गठन या घूर्णन के रंग देने में सक्षम होना चाहिए, इसे लाल-काले पेड़ में बदलने के लिए।
। यह इसे और अधिक कठोर संतुलित बनाता है।
लाल ब्लैक पेड़ के लिए नियमों के 5 सेट हैं जिन्हें आप सुनिश्चित करने के लिए आवश्यक हैं कि सम्मिलन और निष्कासन के माध्यम से रहें जो आप यहां पा सकते हैं http://en.wikipedia.org/wiki/Red-black_tree।
लाल चीज के पेड़ के लिए आपकी मदद करने वाली मुख्य बात यह तथ्य है कि चाचा लाल होने पर आप उन पांच नियमों के आधार पर पेड़ को फिर से रंग में रंग सकते हैं। यदि चाचा काला है तो आपको जो भी समस्याएं ठीक करने के लिए अधिकतम दो रोटेशन करने की आवश्यकता होगी, लेकिन उन दो या दो घूर्णनों के बाद आप कर चुके हैं। इसे पैक करें और शुभरात्रि कहें क्योंकि यह उस छेड़छाड़ का अंत है जिसे आपको करने की ज़रूरत है।
बिग नियम संख्या 5 है ... 'किसी दिए गए नोड से प्रत्येक सरल पथ में इसके किसी भी मूल पत्ते में काले नोड्स की संख्या होती है'।
इससे पेड़ के काम को करने के लिए आपको आवश्यक अधिकांश घूर्णन का कारण बन जाएगा और इससे पेड़ संतुलन से बहुत दूर नहीं जा सकता है।
एवीएल पेड़ लाल-काले पेड़ों की तुलना में अधिक कठोर संतुलन बनाए रखते हैं। एक एवीएल पेड़ में रूट से गहरे पत्ते तक पथ ~ 1.44 एलजी (एन + 2) होता है, जबकि लाल काले पेड़ में यह ~ 2 एलजी (एन + 1) होता है।
नतीजतन, एक एवीएल पेड़ में लुकअप आमतौर पर तेज़ होता है, लेकिन यह अधिक घुमावदार संचालन के कारण धीमी प्रविष्टि और हटाने की लागत पर आता है। इसलिए यदि आप लुकअप की संख्या पेड़ के अपडेट की संख्या पर हावी होने की उम्मीद करते हैं तो एवीएल पेड़ का उपयोग करें।
AVL पेड़ अक्सर लाल-काले पेड़ों के साथ तुलना की जाती है दोनों का समर्थन आपरेशन के एक ही सेट और बुनियादी कार्यों के लिए
O(log n)समय लगेगा क्योंकि। लुकअप-गहन अनुप्रयोगों के लिए, एवीएल पेड़ लाल-काले पेड़ों की तुलना में तेज़ होते हैं क्योंकि वे अधिक कठोर रूप से संतुलित होते हैं। लाल-काले पेड़ों की तरह, एवीएल पेड़ ऊंचाई-संतुलित होते हैं। दोनों सामान्य रूप से वजन-संतुलित नहीं होते हैं और न ही μ ≤ ½ के लिए μ- संतुलित होते हैं; यानी, भाई नोड्स में वंशजों की भारी संख्या में भिन्नता हो सकती है।
विकिपीडिया लेख से AVL Trees
पेड़ों की अधिकतम ऊंचाई पर संतुलन रखने के लिए सर्वोपरि महत्वपूर्ण है। यह लगभग एवीएल के लिए 1.44 * log(n) के बराबर है, लेकिन आरबी पेड़ के लिए, यह 2 * log(n) है। तो हम निष्कर्ष निकाल सकते हैं कि जब समस्या खोज प्रोत्साहन है तो एवीएल का उपयोग करना बेहतर होता है। एवीएल और आरबी पेड़ के लिए एक और सवाल क्या है। घूर्णन की निचली लागत पर यादृच्छिक प्रविष्टि का सामना करते समय आरबी पेड़ एवीएल से बेहतर होता है लेकिन एवीएल जो आरोही या अवरोही डेटा डालने के लिए अच्छा होता है। तो यदि समस्या सम्मिलन प्रोत्साहन है, तो हम आरबी पेड़ का उपयोग कर सकते हैं।
छोटे डेटा के लिए:
डालने: आरबी पेड़ & AVL पेड़ तेजी से है क्योंकि औसत आरबी पेड़ पर कम रोटेशन का उपयोग किया जाएगा अधिकतम रोटेशन लेकिन आरबी पेड़ की लगातार संख्या है।
लुकअप: एवीएल पेड़ तेज है, क्योंकि एवीएल पेड़ की गहराई कम है।
हटाएं: आरबी पेड़ में अधिकतम रोटेशन की निरंतर संख्या है लेकिन एवीएल पेड़ में घूर्णन के ओ (लॉग एन) के समय सबसे खराब हो सकते हैं। और औसत आरबी पेड़ में भी घूर्णन की कम संख्या होती है इस प्रकार आरबी पेड़ तेज होता है।
बड़े डेटा के लिए:
डालने: AVL पेड़ तेजी से होता है। क्योंकि आपको सम्मिलन से पहले किसी विशेष नोड को देखने की आवश्यकता है। क्योंकि आपके पास अधिक डेटा है, विशेष नोड को देखने पर समय अंतर ओ (लॉग एन) के आनुपातिक बढ़ता है। लेकिन एवीएल पेड़ & आरबी पेड़ अभी भी सबसे खराब मामले में घूर्णन की निरंतर संख्या की आवश्यकता है। इस प्रकार बोतल की गर्दन उस विशेष नोड के लिए खोजने का समय बन जाएगी।
लुकअप: एवीएल पेड़ तेज है। (जैसा कि छोटे डेटा मामले में है)
हटाएं: एवीएल पेड़ औसतन तेज़ है, लेकिन सबसे खराब स्थिति में आरबी पेड़ तेज है। क्योंकि आपको हटाने से पहले स्वैप करने के लिए बहुत गहरे नोड के लिए भी देखने की आवश्यकता है (सम्मिलन के कारण के समान)। औसतन दोनों पेड़ों में घूर्णन की निरंतर संख्या होती है। लेकिन आरबी पेड़ घूर्णन के लिए लगातार ऊपरी बाध्य है।
ऐसा लगता है कि एवीएल पेड़ों को हमेशा बड़ी मात्रा में डेटा के साथ प्राथमिकता दी जाएगी। इसका उपयोग जावा और सी ++ एसटीएल में कैसे किया जाता है? https://stackoverflow.com/questions/3901182/applications-of-red-black-trees – emschorsch
आपके पास एआरएल पेड़ को सम्मिलित/हटाए गए मामले में आरबी पेड़ से बेहतर बनाने के लिए कुछ मात्रा (उदाहरण के लिए 1 मिलियन) की आवश्यकता है, और यह वास्तव में इस पर निर्भर करता है कि आप इसे कैसे कार्यान्वित करते हैं। एक स्मार्ट एवीएल कार्यान्वयन डेटा की कम मात्रा के साथ भी std :: मानचित्र को हरा सकता है। उदाहरण के लिए, आपको यह जांचने की आवश्यकता नहीं है कि क्या माता-पिता-> ऊंचाई 5 से बड़ी है, तो बच्चे और पोते शून्य हैं। –
सारांश में: AvlTrees RedBlackTrees की तुलना में थोड़ा बेहतर संतुलित हैं। दोनों पेड़ लुकअप, सम्मिलन और हटाने के लिए कुल मिलाकर ओ (लॉग एन) समय लेते हैं, लेकिन सम्मिलन और हटाने के लिए पूर्व को ओ (लॉग एन) रोटेशन की आवश्यकता होती है, जबकि बाद वाले केवल ओ (1) रोटेशन लेते हैं।
के बाद से रोटेशन स्मृति के लिए लिख मतलब, और स्मृति के लिए लिख महंगा है, RedBlackTrees AvlTrees
से अद्यतन करने के लिए कैसे एक AVL ट्री काम करता है की एक विचार प्राप्त करने के लिए तेजी से व्यवहार में कर रहे हैं, this इंटरैक्टिव विज़ुअलाइज़ेशन मदद करता है।
एवीएल के साथ ही रेडब्लैक पेड़ ऊंचाई-संतुलित वृक्ष डेटा संरचनाएं हैं। वे बहुत समान हैं, और असली अंतर किसी भी जोड़/निकालने के संचालन पर किए गए घूर्णन ऑपरेशन की संख्या में होता है - एवीएल के मामले में उच्च, समग्र समग्र सजावट को संरक्षित करने के लिए।
दोनों कार्यान्वयन O(lg N) के रूप में स्केल करते हैं, जहां एन पत्तियों की संख्या है, लेकिन व्यावहारिक रूप से एवीएल ट्री लुकअप गहन कार्यों पर तेज़ है: बेहतर संतुलन का लाभ लेते हुए, पेड़ ट्रैवर्स औसत पर कम होते हैं। दूसरी तरफ, सम्मिलन और विलोपन के अनुसार, एक एवीएल वृक्ष धीमा है: संशोधन पर डेटा संरचना को ठीक से पुनर्व्यवस्थित करने के लिए घूर्णन की एक बड़ी संख्या की आवश्यकता होती है।
सामान्य प्रयोजन कार्यान्वयन के लिए (यानी प्राथमिकता यह स्पष्ट नहीं है कि लुकअप ऑपरेशंस के प्रमुख हैं), रेडब्लैक पेड़ को प्राथमिकता दी जाती है: उन्हें लागू करना आसान होता है, और सामान्य मामलों पर तेज़ी से - जहां डेटा संरचना संशोधित होती है जितनी बार खोज की गई। जावा में एक उदाहरण, TreeMap और TreeSet बैकिंग रेडब्लैक ट्री का उपयोग करते हैं।
तथ्य यह है कि रेडब्लैक पेड़ों में कम घूर्णन होते हैं, हालांकि उन्हें आवेषण/हटावट पर तेज़ी से बना सकते हैं ....। चूंकि वे आमतौर पर थोड़ा गहरा होता है, इसलिए वे आवेषण और हटाए जाने पर भी धीमे हो सकते हैं। हर बार जब आप पेड़ में एक स्तर से दूसरे तक जाते हैं, तो एक बड़ा परिवर्तन होता है कि अनुरोध की गई जानकारी कैश में नहीं है और उसे राम से पुनर्प्राप्त किया जाना चाहिए। इस प्रकार कम घूर्णन पर प्राप्त समय पहले ही खो जा सकता है क्योंकि इसे गहराई से नेविगेट करना पड़ता है और इस प्रकार इसे अपने कैश को अधिक बार अपडेट करना पड़ता है। कैश से काम करने में सक्षम होने या एक बड़ा अंतर नहीं बनाता है। यदि प्रासंगिक जानकारी कैश में है, तो आप एक अतिरिक्त स्तर पर नेविगेट करने के लिए आवश्यक समय में एकाधिक रोटेशन ऑपरेशन कर सकते हैं और अगली स्तर की जानकारी कैश में नहीं है। इस प्रकार रेडब्लैक सिद्धांत में तेजी से है, केवल परिचालनों की आवश्यकता है, यह कैश मिस के कारण अभ्यास में धीमा हो सकता है।
अवधारणा को बेहतर समझने के लिए कह रहे हैं। एवीएल पेड़ और लाल काले पेड़ दोनों में प्रति प्रविष्टि लगभग दो घूर्णन होते हैं। तो, आप कैसे कह सकते हैं कि एवीएल पेड़ धीमे हैं? अग्रिम धन्यवाद! – user2626445
@ लार्समैन! क्या प्रदर्शन अंतर इतना है कि एक नई अवधारणा बनाई गई है? – Shashwat
@Shashwat मुझे आपका मतलब नहीं मिलता है। नई अवधारणा? –