बड़ी संख्या में नोड्स के त्वरित सम्मिलन के लिए सर्वश्रेष्ठ स्व-संतुलन बीएसटी

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

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

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

0
जोड़ा संपादित
विचारों: 1

3 उत्तर

Red-black is better than AVL for insertion-heavy applications. If you foresee relatively uniform look-up, then Red-black is the way to go. If you foresee a relatively unbalanced look-up where more recently viewed elements are more likely to be viewed again, you want to use splay trees.

0
जोड़ा

[हैश टेबल हैं] ओ (1) सम्मिलन और खोज

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

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

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

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

This means that with finitely many buckets, there must be an infinite set of strings which all have the same hash value. Suppose I insert a lot, i.e. ω(1), of those, and start querying. This means that your hash table has to fall back on some other O(1) insertion/search mechanism to answer my queries. Which one, and why not just use that directly?

0
जोड़ा
यह पारंपरिक ज्ञान है। सबसे अच्छा मामला, ओ (1), स्पष्ट रूप से कार्यान्वयन अलग-अलग होंगे। विभिन्न हैश टेबल एल्गोरिदम भी हैं।
जोड़ा लेखक ApplePieIsGood, स्रोत
@MeNoMore Jonas सही ने अपने उत्तर की पहली पंक्ति के लिए एक उद्धरण प्रारूप का उपयोग किया, क्योंकि यह किसी और के उद्धरण था। भविष्य में इस तरह के संपादन मत करो।
जोड़ा लेखक Andrew Barber, स्रोत
@menomore ब्रैकेट समरूप सामग्री का प्रतिनिधित्व करते हैं, समझने में आसानी के लिए किया जाता है। यह एक बहुत ही आम उपयोग है। पैराफ्रेश और उद्धरण Boyetboy के जवाब से आते हैं।
जोड़ा लेखक Andrew Barber, स्रोत
@ जोनासकोल्कर माफ़ी माफ करना; तुम सही हो। याद दिलाने के लिए शुक्रिया :)
जोड़ा लेखक Andrew Barber, स्रोत
@AndrewBarber अगली बार आपके पास अनुरोध है कि आप शब्द का प्रयोग करें या मॉडरेटर से संपर्क करें। अब इस मुद्दे पर, जबकि इसके बारे में आपका अधिकार मुझे स्क्वायर ब्रैकेट द्वारा संरक्षित किया गया था: [हैश टेबल] क्या आप इसके लिए कोई कारण देखते हैं? यह शब्द पृष्ठ पर कहीं और नहीं है?
जोड़ा लेखक CloudyMarble, स्रोत
@AndrewBarber धन्यवाद
जोड़ा लेखक CloudyMarble, स्रोत
"यह एक पारंपरिक ज्ञान है।" - मैंने इसे कई बार सुना है, लेकिन मैंने अभी भी एक सबूत नहीं देखा है। मुझे लगता है कि लोकगीत के इस टुकड़े को चुनौती देना अच्छा होगा यदि आप सैद्धांतिक परिणाम चाहते हैं "यह ओ (1)" है, या यदि आप "अभ्यास में तेज़" चाहते हैं तो विभिन्न लुकअप संरचनाओं को मापें। "सर्वश्रेष्ठ मामला, ओ (1)" - असंतुलित खोज वृक्षों के पास भी है, फिर भी कोई भी तर्क नहीं देता कि उनके पास "ओ (1) सम्मिलन और खोज" है।
जोड़ा लेखक Jonas Kölker, स्रोत
सबसे अच्छे मामले में, उपयोगकर्ता रूट नोड पर संग्रहीत मान की खोज कर रहा है, जो ओ (1) समय तक पहुंचने के लिए लेता है ...
जोड़ा लेखक Jonas Kölker, स्रोत
@ एंड्रयूबार्बर: "अगली बार जब आपके पास कोई अनुरोध है तो आप शब्द का प्रयोग करें या मॉडरेटर से संपर्क करें।" // अगली बार जब आप किसी को सही करते हैं, तो क्या आप दूसरों के व्यवहार के लिए एक अच्छा भूमिका मॉडल बनने का निर्णय लेंगे?
जोड़ा लेखक Jonas Kölker, स्रोत
आपका स्वागत है :-)
जोड़ा लेखक Jonas Kölker, स्रोत
एक सबसे अच्छा मामला असंतुलित खोज पेड़ संतुलित से एक नोड होगा। सर्वश्रेष्ठ केस सम्मिलन / लुकअप अभी भी लॉग है (एन)
जोड़ा लेखक µBio, स्रोत

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

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

0
जोड़ा