सी ++ एसटीएल मानचित्र कंटेनर ओ (लॉग (एन)) की जटिलता क्यों है?

Question

सी ++ एसटीएल कंटेनर जैसे vector और list के लिए, तत्व ढूंढने की जटिलता और उन्हें डालने या निकालने के लिए स्वयं व्याख्यात्मक है। हालांकि, map कंटेनर के लिए, भले ही मैं अपने पढ़ने से जानता हूं कि एक्सेस और सम्मिलन जटिलता/प्रदर्शन ओ (लॉग (एन)) है, मैं क्यों काम नहीं कर सकता। मैं स्पष्ट रूप से मानचित्रों को जितना समझता हूं उतना समझ नहीं पा रहा हूं, इसलिए इस विषय पर कुछ ज्ञान की बहुत सराहना की जाएगी।

Answer 1

मानचित्र या सेट के तत्व पेड़ संरचना में निहित हैं; हर बार जब आप पेड़ के नोड की जांच करते हैं, तो आप यह निर्धारित करते हैं कि जिस तत्व को आप ढूंढने/डालने का प्रयास कर रहे हैं वह नोड से कम या उससे अधिक है। आपको ऐसा करने की आवश्यकता है (उचित रूप से संतुलित पेड़ के लिए) लॉग 2 (एन) है क्योंकि प्रत्येक तुलना संभावनाओं के आधे से बाहर निकलती है।

Answer 2

slavik262 अंक के रूप में, नक्शे आमतौर पर लाल-काले पेड़ों के साथ लागू होते हैं, जो स्वयं संतुलित होते हैं। उदाहरण के लिए wikipedia में एक लाल-काले-पेड़ की जटिलता की जांच करें, मुझे बाइनरी पेड़ वाले मानचित्र के किसी भी कार्यान्वयन को नहीं पता; अगर मार्क रान्ससम एक जानता है, तो मुझे यह जानकर प्रसन्नता होगी कि कौन सा है।