ढेर या लाल-काले पेड़?

Question

मैं डेटा संरचना को निरंतर स्थान के अतिप्रवाह बफर के रूप में उपयोग करने के लिए तैयार हूं। मैं कुशल सम्मिलित करना चाहता हूं लेकिन न्यूनतम तत्व का सबसे महत्वपूर्ण रूप से कुशल निष्कासन करना चाहता हूं। मैं एक ढेर का उपयोग करने के बारे में सोच रहा था क्योंकि मेरे पास ओ (लॉग (एन)) find_min() और लॉग (एन) सम्मिलन और हटाना है। दूसरी तरफ मुझे पता है कि एक लाल-काले पेड़ की तुलना में लाभ को समझ में नहीं आता है क्योंकि इसमें ओ (लॉग (एन)) भी सम्मिलित है और हटाएं लेकिन ओ (1) न्यूनतम/अधिकतम पाएं। और क्रमबद्ध आउटपुट का लाभ (मुझे इसके बारे में परवाह नहीं है)।

प्रश्न से संबंधित है: Is a red-black tree my ideal data structure?

जब से मैं संरचनाओं std :: नक्शे से और बढ़ावा से :: ढेर उपलब्ध के दोनों है कारण है कि मैं लाल-काले पेड़ के बजाय ढेर का उपयोग करना पसंद करना चाहिए? अंत में, लाल-काले पेड़ का उपयोग करके मेरे पास एक प्रविष्टि के लिए ओ (लॉग (एन)) खोज समय भी होता है जबकि एक ढेर के लिए समय ओ (एन) होता है जो डुप्लीकेट मौजूद होने के बाद से महत्वपूर्ण है।

Answer 1

अंतर मुख्य रूप से संरचनाओं का उपयोग करने के तरीके में होता है।

• बाइनरी ढेर मूल्यों को सम्मिलित करने और न्यूनतम मूल्य को पुनर्प्राप्त करने के लिए बहुत तेज डेटा संरचनाएं हैं। हालांकि, वे यादृच्छिक मूल्यों की कुशल खोज या हटाने का समर्थन नहीं करते हैं।

• लाल/काले पेड़ संतुलित बाइनरी खोज पेड़ हैं जो कुशल सम्मिलन, हटाना, मनमानी मूल्यों की तलाश, और (उचित रूप से तेज़) खोज-न्यूनतम का समर्थन करते हैं। हालांकि, उनके पास बाइनरी ढेर की तुलना में बहुत अधिक उपर है।

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

इसके अलावा, ध्यान दें कि यदि आप बाइनरी ढेर की आवश्यकता है तो आप std::priority_queue का उपयोग कर सकते हैं; आपको बूस्ट का उपयोग करने की आवश्यकता नहीं है। यह भी गारंटी नहीं है कि std::map एक लाल/काला पेड़ है; यह शायद कुछ प्रकार के संतुलित बीएसटी है, लेकिन इसे कुछ अन्य एल्गोरिदम का उपयोग करके संतुलित किया जा सकता है।

आशा है कि इससे मदद मिलती है!

Answer 2

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