मुझे याद आया कि ढेर का उपयोग यह पता लगाने के लिए किया जा सकता है कि इसमें कोई तत्व है या नहीं (ओएन (लॉगएन) समय जटिलता के साथ। लेकिन अचानक मुझे विवरण नहीं मिल सकता है। मैं केवल getmin हटाने और अन्य पर मिल सकता है।एक ढेर में एक तत्व खोजें
क्या कोई संकेत दे सकता है?
यह निर्धारित करने के लिए कि क्या कोई तत्व अंदर है या नहीं, आपको ढेर में प्रत्येक तत्व को खोजना होगा।
एक अनुकूलन संभव है, हालांकि (हम यहां अधिकतम ढेर मानते हैं)। यदि आप जिस तत्व को खोज रहे हैं उससे कम मान वाले नोड तक पहुंच गए हैं, तो आपको उस नोड से आगे की खोज करने की आवश्यकता नहीं है। हालांकि, इस अनुकूलन के साथ भी, खोज अभी भी ओ (एन) है (औसत में एन/2 नोड्स की जांच करने की आवश्यकता है)।
मुझे लगता है कि आप जो खोज रहे हैं वह एक बीएसटी (बाइनरी सर्च ट्री) है।
यदि आपके पास पहले से ही प्राथमिकता कतार है और यह जांचना चाहते हैं कि इसमें कोई दिया गया तत्व है या नहीं। – finnw
क्या यह पूरी तरह से सच है? उदाहरण के रूप में निम्न ढेर लें: '[5, 4, 1, 3] 'यदि मैं नंबर 3 के लिए इस ढेर (सरणी के रूप में) खोजता हूं तो मैं 1 दबा दूंगा और आपके एल्गोरिदम के अनुसार, यहां रुकें यह निष्कर्ष निकालना है कि वास्तव में यह ढेर में नहीं है? क्या मुझसे कोई चूक हो रही है? –
अनुकूलन के साथ, रूट 1 के साथ उपट्री की खोज नहीं की जाएगी, क्योंकि इसमें 3 शामिल नहीं हो सकते हैं। 3 एक और उप-विषय में है। मैं मानता हूं कि एक रैखिक खोज (एक रिकर्सिव एक के विपरीत) गलत जवाब दे सकती है। –
@ जेम्ससैंडर्स यह सभी मामलों में भी एक रैखिक खोज के लिए सच है। पूर्ण बाइनरी पेड़ में 4 के बाएं बच्चे के रूप में मूल्य 3 होगा, और 1 समान ऊंचाई पर होगा। भले ही आप रैखिक खोज कर रहे हों, ऑप्टिमाइज़ेशन कहता है कि 4> 3, इस प्रकार आपको कम से कम , 4 के बच्चों की तुलना करें, अन्य सभी तत्वों के अलावा 4 की ऊंचाई पर। – lee