सॉर्टेड डिक्शनरी

Question

में किसी आइटम की अनुक्रमणिका ढूंढने का सबसे प्रभावी तरीका मैं वस्तुओं की एक सूची बनाए रखने के लिए एक क्रमबद्ध शब्दकोश का उपयोग कर रहा हूं, जिसमें से मुझे नियमित रूप से शीर्ष x आइटमों की स्थिति की निगरानी करने की आवश्यकता होती है। हर बार जब मैं कोई आइटम अपडेट करता हूं, तो मुझे यह पता लगाने का एक त्वरित तरीका चाहिए कि मैं जिस आइटम का जिक्र कर रहा हूं उसका उपयोग कर रहा हूं। मैं समझता हूं कि मैं पूरी सूची का आकलन कर सकता हूं और अपनी स्थिति को गिन सकता हूं, लेकिन मैं सभी प्रकार के शब्दकोश रेडब्लैक पेड़ पर होने के बाद ओ (लॉग एन) समय या बेहतर के साथ कुछ ढूंढ रहा हूं। प्रत्येक नोड अपने बच्चों का ट्रैक रखने में सक्षम होना चाहिए, और यह एक त्वरित गणना होना चाहिए।

Answer 1

आप बस को बदल सकते हैं अपने SortedDictionary<TKey, TValue> एक SortedList<TKey, TValue> में और उसके बाद का उपयोग IndexOfKey(key):

var s = new SortedList<string, string> 
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } }; 

// Outputs 1 
Console.WriteLine(s.IndexOfKey("b")); 

आंतरिक Array.BinarySearch<TKey>() का उपयोग करता है, तो यह हे हो जाएगा (लॉग n) है, जो हे की तुलना में तेजी है (n) (जो यह होगा यदि आप इसके माध्यम से आगे बढ़कर सामने से पीछे की ओर खोज करते हैं)।

Answer 2

सूचकांक द्वारा वस्तुओं तक पहुंचने के लिए एक पेड़ संरचना का निर्माण किया जा सकता है या एलजीएन समय में किसी मौजूदा आइटम की अनुक्रमणिका की रिपोर्ट करने के लिए, आवेषण और हटाए जाने के लिए बहुत ही कम समय की आवश्यकता होती है। ऐसा करने का एक तरीका यह ट्रैक रखना होगा कि प्रत्येक नोड की बाएं और दाएं शाखाओं में कितनी वस्तुएं हैं (डालने या हटाने पर, बच्चों की गिनती बदलते समय पैरेंट नोड्स की नोड गिनती बदलें)। यदि पेड़-आधारित संरचना ऐसी सुविधा प्रदान नहीं करती है, हालांकि, मुझे इसे फिर से निकालने का कोई आसान तरीका नहीं है।