द्विआधारी खोज बनाम बाइनरी खोज पेड़

Question

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

में क्रमबद्ध सरणी द्विआधारी खोज
खोज: हे (लॉग (एन))
प्रविष्टि: हे (लॉग (एन))
विलोपन (हम जहां तत्व सम्मिलित करने के लिए खोजने के लिए द्विआधारी खोज चलाने): ओ (लॉग इन करें (एन)) (हम नष्ट करने के लिए तत्व)

द्विआधारी खोज वृक्ष
खोज खोजने के लिए द्विआधारी खोज चलाने: हे (लॉग (एन))
प्रविष्टि: हे (लॉग (एन))
हटाने की प्रक्रिया: ओ (लॉग (एन))

बाइनरी खोज ट्रे उपरोक्त सूचीबद्ध संचालन के लिए ओ (एन) का सबसे खराब मामला है (यदि पेड़ संतुलित नहीं है), तो ऐसा लगता है कि यह वास्तव में बाइनरी खोज के साथ क्रमबद्ध सरणी से भी बदतर होगा।

इसके अलावा, मुझे यह नहीं लगता है कि हमें पहले से सरणी को सॉर्ट करना होगा (जो ओ (nlog (n)) खर्च करेगा, हम तत्वों को एक-एक करके सरणी में डालेंगे, जैसा कि हम बाइनरी पेड़ के लिए करेंगे । BST का केवल लाभ मैं देख सकता हूँ कि यह inorder, अग्रिम आदेश, क्रंमोत्तर तरह traversals के अन्य प्रकार का समर्थन करता है है।

Answer 1

आपका विश्लेषण गलत है, दोनों प्रविष्टि और विलोपन, हे (एन) एक क्रमबद्ध सरणी के लिए है, क्योंकि आप शारीरिक रूप से करने के लिए कदम प्रविष्टि के लिए जगह बनाने के लिए या इसे सेक हटाए गए आइटम को ढकने के लिए करने के लिए डेटा है।

ओह और पूरी तरह असंतुलित बाइनरी खोज पेड़ के लिए सबसे खराब मामला ओ (एन) है, ओ (लॉग) नहीं है।

Answer 2

वहाँ नहीं एक लाभ के ज्यादा में या तो एक से क्वेरी है।

लेकिन एक निर्माण सॉर्टेड पेड़ एक सॉर्टेड सरणी बनाने से बहुत तेज़ है, जब आप एक समय में तत्व जोड़ रहे हैं। तो इसे बदलने में कोई बात नहीं है जब आप कर लेंगे तो एक सरणी में।

Answer 3

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

इसके अलावा, बड़ा-ओ एक जैसा हो सकता है, लेकिन स्थिरांक हमेशा नहीं होते हैं। बाइनरी पेड़ के साथ यदि आप डेटा को सही तरीके से स्टोर करते हैं, तो आप कई स्तरों पर कैशिंग का बहुत अच्छा उपयोग कर सकते हैं। नतीजा यह है कि यदि आप बहुत सी पूछताछ कर रहे हैं, तो आपका अधिकांश काम सीपीयू कैश के अंदर रहता है जो चीजों को बहुत तेज़ करता है। यह विशेष रूप से सच है यदि आप सावधान हैं कि आप अपने पेड़ को कैसे बनाते हैं। उदाहरण के लिए http://blogs.msdn.com/b/devdev/archive/2007/06/12/cache-oblivious-data-structures.aspx देखें कि पेड़ का चालाक लेआउट प्रदर्शन में सुधार कैसे कर सकता है। एक सरणी जो आप बाइनरी खोज करते हैं, ऐसी किसी भी चाल का उपयोग करने की अनुमति नहीं देती है।