ट्रीसेट पुनरावृत्ति की समय जटिलता क्या है?

Question

मेरे कोड में, जावा TreeSet पुनरावृत्ति प्रभावशाली समय कारक है। सिस्टम को देखने में मुझे विश्वास है कि यह ओ (एन) जटिलता है। क्या कोई इसे सत्यापित कर सकता है?

मुझे लगता है कि बाल नोड से पैरेंट नोड तक पिछड़े लिंक प्रदान करके मैं प्रदर्शन में सुधार कर सकता हूं।

Answer 1

TreeSet पुनरावृत्ति निश्चित रूप से ओ (एन) है, जैसा किसी भी समझदार पेड़-चलने वाले एल्गोरिदम से अपेक्षा की जा सकती है।

मैं सोच रहा हूँ कि लिंक नोड माता-पिता के लिए बच्चे नोड से पिछड़े प्रदान करके मैं प्रदर्शन में सुधार कर सकते हैं।

TreeMap (जो TreeSet पर आधारित है) पहले से ही ऐसे मूल संदर्भ हैं।

private Entry<K,V> successor(Entry<K,V> t) { 
    if (t == null) 
     return null; 
    else if (t.right != null) { 
     Entry<K,V> p = t.right; 
     while (p.left != null) 
      p = p.left; 
     return p; 
    } else { 
     Entry<K,V> p = t.parent; 
     Entry<K,V> ch = t; 
     while (p != null && ch == p.right) { 
      ch = p; 
      p = p.parent; 
     } 
     return p; 
    } 
} 

Answer 2

आप TreeSet की एक प्रति लेने जब आप इसे बदल माना जाता है: यह विधि यह सब करने पर निर्भर करता है? यदि हावी समय ट्रीसेट पुनरावृत्ति (इसे संशोधित करने के बजाय) में बिताया जाता है तो ट्रीसेट को एक सरणी या ऐरेलिस्ट (केवल तभी बदला जाता है) में कॉपी करना और केवल इस सरणी/एरेलेस्टिस्ट पर पुनरावृत्ति करना ट्रीसेट पुनरावृत्ति की लागत को लगभग समाप्त कर सकता है।