दक्षता में ऐरे और बाइनरी खोज पेड़ के बीच क्या अंतर है?

Question

मुझे पता है कि सबसे अच्छा क्या है: ऐरे या बाइनरी सर्च पेड़ (डालें, हटाएं, अधिकतम और मिनट ढूंढें) और मैं दोनों को कैसे सुधार सकता हूं?

Answer 1

एक सरणीrandom access इसमें प्रत्येक तत्व के लिए अनुमति देता है। इसलिए आप O(1) में एक विशिष्ट तत्व डालें, हटाएं और देखें, और अधिकतम/मिनट, O(n) में हटाएं। [आप अधिकतम/न्यूनतम O(1) भी बना सकते हैं और इसके बजाय O(n) हटा सकते हैं]। यदि आप अपनी सरणी को सॉर्ट कर रहे हैं, तो यह O(n) होने के लिए डालने/हटाएगा, लेकिन आपको O(logn) मिल जाएगा, और O(1) न्यूनतम/अधिकतम।

एक BST परिभाषा के अनुसार क्रमबद्ध किया जाता है, और एक नियमित [असंतुलित] BST के लिए, आप O(n) सबसे खराब स्थिति व्यवहार मिलता है। संतुलित बीएसटी के लिए, आपको O(logn) डालें/हटाएं/ढूंढें। आप O(1) मिनट/अधिकतम दोनों के लिए कैसे प्राप्त कर सकते हैं।

एरे आमतौर पर iterate [पुनरावृत्ति का मानना ​​महत्वपूर्ण नहीं है] के लिए तीर भी अधिक तेज़ होते हैं क्योंकि आप बेहतर cache प्रदर्शन प्राप्त करते हैं। इसके अलावा, बीएसटी के विपरीत - जिसमें प्रकृति द्वारा असंबद्ध आकार है, एक सरणी को पुनर्वितरण की आवश्यकता होती है और जब आपकी सरणी पूरी होती है तो डेटा की प्रतिलिपि बनाना आवश्यक होता है। AVL या red-black-trees तरह -

एक BST में सुधार यह balanced बनाकर किया जा सकता है।

कौन सा बेहतर है? यह आवेदन पर निर्भर करता है। आम तौर पर जब आप डेटा डालने और इसे क्रमबद्ध रखने की योजना बना रहे हैं, तो बीएसटी को प्राथमिकता दी जाएगी। यदि यादृच्छिक अभिगम या पुनरावृत्ति मुख्य उद्देश्य है: आप आमतौर पर एक सरणी का उपयोग करते हैं।

Answer 2

प्रदर्शन Arrays और द्विआधारी खोज पेड़ों की तुलना:

    Array      Binary search tree 
      Unsorted Sorted   Average   Worst case 
Space  O(n)  O(n)    O(n)    O(n) 
Search  O(n)  O(log n) *  O(log n)   O(n) 
Max/Min O(n)  O(1)    O(1) **   O(1) ** 
Insert  O(1)  O(n)    O(log n)   O(n) 
Delete  O(1)  O(n)    O(log n)   O(n) 

* संभालने द्विआधारी खोज

** न्यूनतम और अधिकतम करने के लिए अतिरिक्त संकेत की आवश्यकता है, अन्यथा यह हे है (लॉग एन)