सेट की जटिलता :: डालने

Question

मैंने पढ़ा है कि एक सेट में सम्मिलित ऑपरेशन केवल लॉग (एन) समय लेता है। वो कैसे संभव है?

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

मेरा संदेह मेरी समझ पर आधारित है कि सेट को सरणी के रूप में कार्यान्वित किया गया है और तत्व क्रमबद्ध क्रम में संग्रहीत हैं। अगर मेरी समझ गलत है तो कृपया मुझे सही करें।

Answer 1

std::set आमतौर पर एक लाल-काले बाइनरी खोज पेड़ के रूप में लागू किया जाता है। इस डेटा संरचना पर सम्मिलन में ओ (लॉग (एन)) जटिलता का सबसे खराब मामला है, क्योंकि वृक्ष संतुलित रखा जाता है।