बड़ी संख्या में नोड्स

Question

के त्वरित सम्मिलन के लिए सर्वश्रेष्ठ स्व-संतुलन बीएसटी कई स्रोतों के माध्यम से मैं कई आत्म-संतुलन BST एस पर विवरण ढूंढने में सक्षम हूं, लेकिन मुझे कोई अच्छा विवरण नहीं मिला है कि कौन सा सबसे अच्छा है विभिन्न परिस्थितियों में उपयोग करने के लिए (या अगर यह वास्तव में कोई फर्क नहीं पड़ता)।

मैं एक BST कि दस लाख नोड्स से अधिक भंडारण के लिए इष्टतम है चाहता हूँ। नोड्स को सम्मिलित करने का क्रम मूल रूप से यादृच्छिक है, और मुझे कभी भी नोड्स को हटाने की आवश्यकता नहीं होगी, इसलिए सम्मिलन समय केवल एक चीज है जिसे अनुकूलित करने की आवश्यकता होगी।

मैं इतना है कि मैं जल्दी से देख सकते हैं कि पिछले एक विन्यास पहले से ही सामना करना पड़ा गया है, एक पहेली खेल में पहले देखी खेल राज्यों स्टोर करने के लिए इसका इस्तेमाल करने का इरादा रखते हैं।

Answer 1

Red-black प्रविष्टि भारी अनुप्रयोगों के लिए AVL से बेहतर है। यदि आप अपेक्षाकृत समान रूप से दिखने लगते हैं, तो लाल-काले रास्ता तय करने का तरीका है। यदि आप अपेक्षाकृत असंतुलित लुक-अप की अपेक्षा करते हैं जहां हाल ही में देखा गया तत्व अधिक बार देखा जा सकता है, तो आप splay trees का उपयोग करना चाहते हैं।

Answer 2

दो आत्म संतुलन BST रों मैं के साथ सबसे परिचित हूँ लाल काले और AVL हैं, इसलिए किसी भी अन्य समाधान बेहतर हैं अगर मैं कुछ के लिए यह नहीं कह सकते, लेकिन जैसा कि मुझे याद है, लाल-काले तेजी से प्रविष्टि है और AVL की तुलना में धीमी पुनर्प्राप्ति।

तो यदि प्रविष्टि पुनर्प्राप्ति से अधिक प्राथमिकता है, तो लाल-काला एक बेहतर समाधान हो सकता है।

Answer 3

BST का उपयोग क्यों करें? आपके विवरण से एक शब्दकोश भी बेहतर काम करेगा, अगर बेहतर नहीं है।

एक BST का उपयोग कर यदि आप कुंजी के लिए, कंटेनर की सामग्री की सूची चाहता था होगा के लिए एकमात्र कारण। यह निश्चित रूप से ऐसा नहीं लगता है कि आप ऐसा करना चाहते हैं, इस मामले में हैश टेबल के लिए जाना है। O(1) सम्मिलन और खोज, हटाने के बारे में कोई चिंता नहीं, बेहतर क्या हो सकता है?

Answer 4

हे (1) प्रविष्टि [हैश टेबल है] और खोज

मुझे लगता है कि यह गलत है।

सबसे पहले, यदि आप keyspace की सीमा सीमित होने के लिए आपको एक सरणी में तत्वों की दुकान और एक हे (1) रैखिक स्कैन कर सकता है। या आप सरणी को शफल कर सकते हैं और फिर ओ (1) अपेक्षित समय में एक रैखिक स्कैन कर सकते हैं। जब सामान सीमित होता है, सामान आसानी से ओ (1) होता है।

तो मान लीजिए कि आपकी हैश तालिका किसी भी मनमानी बिट स्ट्रिंग को स्टोर करेगी; इससे कोई फर्क नहीं पड़ता, जब तक कि चाबियों का एक अनंत सेट होता है, जिनमें से प्रत्येक सीमित होते हैं। फिर आपको किसी भी क्वेरी और सम्मिलन इनपुट के सभी बिट्स को पढ़ना होगा, अन्यथा मैं y0 पर रिक्त हैश और y1 पर क्वेरी डालता हूं, जहां y0 और y1 एक बिट बिट स्थिति में भिन्न होते हैं जिसे आप नहीं देखते हैं।

लेकिन मान लें कि मुख्य लंबाई पैरामीटर नहीं है। यदि आपका सम्मिलन और खोज ओ (1) लेती है, विशेष रूप से हैशिंग ओ (1) समय लेती है, जिसका अर्थ है कि आप केवल हैश फ़ंक्शन से आउटपुट की सीमित मात्रा देखते हैं (जिससे हो सकता है केवल एक सीमित आउटपुट , दिया)।

इसका मतलब है कि परिमित कई बाल्टी के साथ, वहाँ तार जो सभी एक ही हैश मान है की एक अनंत सेट होना चाहिए। मान लीजिए कि मैं बहुत कुछ डालता हूं, यानी ω (1), उनमें से, और पूछताछ शुरू करें।इसका मतलब है कि आपकी हैश तालिका को मेरे प्रश्नों के उत्तर देने के लिए किसी अन्य ओ (1) सम्मिलन/खोज तंत्र पर वापस आना है। कौन सा, और क्यों न सिर्फ इसका उपयोग करें?