12
क्या van Emde Boas trees के अलावा कोई भी अनुप्रयोग पूर्णांक के लिए तेज़ प्राथमिकता कतार के रूप में है?वैन एम्डे बोस पेड़ के अनुप्रयोग?
A
उत्तर
15
वैन एम्डे बोस पेड़ सामान्य बाइनरी खोज पेड़ के स्थान पर कहीं भी इस्तेमाल किया जा सकता है जब तक कि खोज पेड़ की चाबियां कुछ निश्चित सीमा में पूर्णांक हों। इस प्रकार उन अनुप्रयोगों के लिए जहां आपको किसी अन्य पूर्णांक के निकटतम सेट में पूर्णांक खोजने में सक्षम होना चाहिए, एक वीईबी-पेड़ का उपयोग करके संभावित संतुलित बाइनरी खोज पेड़ का उपयोग करने से संभावित रूप से तेज़ हो सकता है। उदाहरण के तौर पर, आपके पास कुछ लाइनों पर स्टोर का रैखिक लेआउट है और कुछ विशेष ग्राहक को निकटतम स्टोर ढूंढना है, एक वीईबी-पेड़ का उपयोग करके खोज (पहले से तेज़) बीएसटी की तुलना में तेजी से तेज हो सकती है।
आशा है कि इससे मदद मिलती है!
निश्चित सीमा कैसे तय की जानी चाहिए? मेरा मतलब है, अगर यह कोई सीमा हो सकती है, तो इसका उल्लेख करने में कोई बात नहीं है, है ना? – SexyBeast
@ क्यूपिडवोगेल वैन एम्डे बोस पेड़ को सीमा के आकार पर ऊपरी बाउंड के ज्ञान के साथ बनाया जाना चाहिए। उस आकार के लिए कोई ऊपरी सीमा नहीं है, लेकिन इसे चुनने के बाद, यह तय हो गया है। – templatetypedef
@Cupidvogel इस बात पर निर्भर करता है कि आपके कार्यान्वयन की कितनी जगह खाली है। विकिपीडिया से: "छोटे पेड़ों के लिए वीईबी पेड़ों से जुड़े उपरि का हिस्सा बहुत बड़ा है: वर्ग (एम) के क्रम में। यह एक कारण है कि वे अभ्यास में लोकप्रिय नहीं हैं। इस सीमा को संबोधित करने का एक तरीका केवल एक निश्चित उपयोग करना है प्रति स्तर बिट्स की संख्या, जिसके परिणामस्वरूप एक त्रिभुज होता है। वैकल्पिक रूप से, प्रत्येक तालिका को हैश तालिका द्वारा प्रतिस्थापित किया जा सकता है, जिससे अंतरिक्ष को ओ (एन) में स्थानांतरित किया जा सकता है (जहां एन डेटा संरचना में संग्रहीत तत्वों की संख्या है) डेटा संरचना को यादृच्छिक बनाते हुए। " – nilsi