[Powered by Google Translate] [द्विआधारी खोज] [पैट्रिक Schmid हार्वर्ड विश्वविद्यालय] [यह CS50 है. - CS50.TV] 

अगर मैं तुम्हें वर्णमाला क्रम में डिज्नी चरित्र के नाम की एक सूची दे दी है और आप से पूछा मिकी माउस मिल, आप ऐसा करने के बारे में कैसे जाना होगा? एक स्पष्ट तरीके से करने के लिए शुरू से ही सूची स्कैन होगा और हर एक के लिए देखने के लिए अगर यह मिकी नाम की जाँच करें. लेकिन जैसा कि आप अलादीन, ऐलिस, एरियल, पढ़ सकते हैं और बहुत आगे है, तुम जल्दी से एहसास है कि सूची के मोर्चे पर शुरू एक अच्छा विचार नहीं था. ठीक है, शायद आप सूची के अंत से पीछे की ओर काम शुरू कर देना चाहिए. अब आप टार्ज़न, सिलाई, स्नो व्हाइट, और इतना आगे पढ़ें. फिर भी, यह इसके बारे में जाने के लिए सबसे अच्छा तरीका की तरह प्रतीत नहीं होता. 

खैर, एक और तरीका है कि आप ऐसा करने के बारे में जा सकते हैं करने के लिए नीचे संकीर्ण की कोशिश नामों की सूची है कि आप को देखने के लिए है. , क्योंकि आप जानते हैं कि वे वर्णमाला क्रम में हैं आप सूची के बीच में सिर्फ नाम के पर लग सकता है और जाँच अगर मिकी माउस के पहले या बाद में इस नाम है. दूसरे स्तंभ में अंतिम नाम पर देख रहे हैं तुम्हें एहसास होगा कि मिकी के लिए एम जैस्मीन के लिए जम्मू के बाद आता है, ताकि आप आसानी से सूची की पहली छमाही की उपेक्षा होगी. तो फिर तुम शायद अंतिम स्तंभ के शीर्ष पर देखना चाहते हैं देखने के लिए और है कि यह Rapunzel के साथ शुरू होता है. मिकी रॅपन्ज़ेल से पहले आता है, लगता है कि हम अंतिम स्तंभ के रूप में अच्छी तरह से अनदेखा कर सकते हैं. सतत खोज रणनीति, आप जल्दी से देखेंगे कि मिकी शेष नामों की सूची की पहली छमाही में है और अंत में मिकी मर्लिन और Minnie के बीच में छिपा पाते हैं. 

क्या आप बस किया मूलतः द्विआधारी खोज थी. के रूप में इस नाम का अर्थ है, यह एक द्विआधारी मामले में अपनी खोज रणनीति करता है. इसका क्या मतलब है? खैर, हल मदों की एक सूची दी है, द्विआधारी खोज एल्गोरिथ्म एक द्विआधारी निर्णय करता है - छोड़ दिया है या सही है, की तुलना में अधिक से अधिक या कम की तुलना में, वर्णानुक्रम से पहले या बाद में प्रत्येक बिंदु पर. अब है कि हम एक नाम है कि इस खोज एल्गोरिथ्म के साथ चला जाता है, एक अन्य उदाहरण में लग रही है, लेकिन हल संख्या की एक सूची के साथ इस बार. हम क्रमबद्ध संख्या की इस सूची में 144 नंबर के लिए देख रहे हैं. पहले की तरह, हम नंबर पाते हैं कि बीच में है - जो इस मामले में 13 है और देखने के लिए अगर 144 से अधिक है या कम से कम 13 है. चूंकि यह स्पष्ट रूप से 13 से अधिक है, तो हम सब कुछ है कि 13 या उससे कम है अनदेखा कर सकते हैं और शेष आधे पर ध्यान केंद्रित. चूंकि अब हम मदों की एक भी नंबर छोड़ दिया है, हम केवल एक संख्या है कि मध्य के करीब है का चयन करें. इस मामले में हम 55 का चयन करें. हम बस के रूप में आसानी से 89 चुना जा सकता है. ठीक है. फिर, 144 55 से अधिक है, तो हम जाने के लिए सही है. सौभाग्य से हमारे लिए, अगले मध्यम संख्या 144 है, एक के लिए हम देख रहे हैं. तो क्रम में 144 को खोजने के लिए एक द्विआधारी खोज का उपयोग करने के लिए, हम यह केवल 3 चरणों में खोजने के लिए सक्षम हैं. यदि हम रैखिक खोज का इस्तेमाल किया जाएगा यहाँ, यह हमें ले लिया है 12 कदम. तथ्य की बात के रूप में, के बाद से इस खोज विधि मदों की संख्या को आधा कर देगा यह करने के लिए हर कदम पर लग रही है, यह आइटम के लिए खोज रहा है मिल जाएगा सूची में आइटम्स की संख्या के लॉग इन के बारे में. अब है कि हम 2 उदाहरण देखा है, चलो पर एक नज़र रखना एक पुनरावर्ती समारोह है कि द्विआधारी खोज को लागू करने के लिए कुछ pseudocode. शीर्ष पर शुरू, हम देखते हैं कि हम करने के लिए एक समारोह में कहा कि 4 तर्क लेता है: कुंजी, सरणी, मिनट, और अधिकतम. कुंजी संख्या है कि हम के लिए देख रहे हैं, तो पिछले उदाहरण में 144 है. ऐरे संख्याओं की सूची है कि हम खोज कर रहे हैं. न्यूनतम और अधिकतम न्यूनतम और अधिकतम पदों के सूचकांक हैं कि हम वर्तमान में देख रहे हैं. तो जब हम शुरू, मिनट शून्य हो सकता है और अधिकतम सरणी के अधिकतम सूचकांक होगा. जैसा कि हम नीचे खोज को संकीर्ण करने के लिए, हम न्यूनतम और अधिकतम अद्यतन सिर्फ सीमा है कि हम अभी भी देख रहे हैं. 

दिलचस्प हिस्सा 1 को छोड़ दो. पहली बात हम करते है midpoint खोजने के, सूचकांक कि मिनट और सरणी है कि हम अभी भी विचार कर रहे हैं के अधिकतम के बीच आधे रास्ते है. तो फिर हम कि midpoint स्थान पर सरणी के मूल्य में देखो और अगर संख्या है कि हम देख रहे हैं कि कुंजी से कम है. यदि उस स्थिति में संख्या कम है, तो इसका मतलब है कि कुंजी है कि स्थिति की बाईं सभी नंबरों की तुलना में बड़ा है. तो हम द्विआधारी खोज समारोह फिर से कॉल कर सकते हैं, लेकिन इस बार न्यूनतम और अधिकतम मापदंडों को अद्यतन करने के लिए सिर्फ आधे पढ़ने कि हम बस में देखा मूल्य से अधिक या बराबर है. दूसरी ओर, अगर कुंजी सरणी के वर्तमान मध्य में संख्या की तुलना में कम है, हम छोड़ दिया करने के लिए जाने के लिए और सभी संख्या है कि अधिक से अधिक कर रहे हैं की अनदेखी करना चाहते हैं. फिर, हम न्यूनतम और अधिकतम अद्यतन की सीमा के साथ द्विआधारी खोज है, लेकिन इस समय फोन लिए सिर्फ निचले आधे शामिल हैं. यदि सरणी में मौजूदा मध्य में न तो मूल्य है से भी बड़ा और न ही कुंजी से छोटा है, तो यह कुंजी के बराबर होना चाहिए. इस प्रकार, हम केवल वर्तमान midpoint सूचकांक वापसी कर सकते हैं, और हम कर रहे हैं. अंत में, इस जांच के मामले के लिए है कि संख्या वास्तव में हम खोज रहे हैं संख्या की सरणी में नहीं है. यदि सीमा की अधिकतम सूचकांक कि हम देख रहे हैं कभी न्यूनतम से भी कम है, इसका मतलब है कि हम बहुत दूर चले गए हैं. चूंकि संख्या इनपुट सरणी में नहीं था, हम -1 लौटने के करने के लिए कुछ भी नहीं है कि संकेत पाया गया. 

आपने गौर किया होगा कि इस एल्गोरिथ्म काम करने के लिए हो सकता है, संख्याओं की सूची को हल किया जाना है. दूसरे शब्दों में, हम केवल 144 द्विआधारी खोज का उपयोग कर सकते हैं अगर सभी नंबरों से सबसे कम उच्चतम करने के आदेश दिए हैं. यदि यह मामला नहीं थे, हम करने के लिए हर कदम पर संख्या के आधे को बाहर करने में सक्षम नहीं होगा. तो हम 2 विकल्प हैं. या तो हम एक unsorted सूची ले और द्विआधारी खोज का उपयोग करने से पहले इसे सुलझा, या हम यकीन कर सकते हैं कि संख्या की सूची के रूप में हम यह संख्या जोड़ने के लिए सॉर्ट किया जाता है. इस प्रकार, बजाय छँटाई बस जब हम खोज की है, सभी समय पर हल सूची क्यों नहीं रखते? 

संख्याओं की एक सूची रखने के लिए एक तरह हल जबकि एक साथ अनुमति देता है एक या जोड़ने के लिए इस सूची से संख्या को स्थानांतरित एक द्विआधारी खोज वृक्ष बुलाया कुछ का उपयोग कर रहा है. एक द्विआधारी खोज वृक्ष एक डेटा संरचना है कि 3 गुण है. सबसे पहले, किसी भी नोड के बाईं subtree केवल मूल्यों है कि कम से कम कर रहे हैं शामिल या नोड के मूल्य के बराबर है. दूसरा, ठीक एक नोड के subtree केवल मूल्यों है कि अधिक से अधिक कर रहे हैं शामिल या नोड के मूल्य के बराबर है. और अंत में, सभी नोड्स के दोनों बाएँ और दाएँ subtrees भी द्विआधारी खोज के पेड़ हैं. चलो एक उदाहरण देखो एक ही नंबर के साथ कि हम पहले भी इस्तेमाल किया. तुम में से जो एक कंप्यूटर विज्ञान के पेड़ से पहले कभी नहीं देखा है के लिए, मुझे आप कह रही है कि एक कंप्यूटर विज्ञान के पेड़ के नीचे की ओर बढ़ता है द्वारा शुरू करते हैं. हाँ, पेड़ आप के आदी रहे हैं के विपरीत, एक कंप्यूटर विज्ञान के पेड़ की जड़ में शीर्ष पर है, और पत्तियों के नीचे हैं. प्रत्येक छोटे से बॉक्स एक नोड कहा जाता है, और नोड्स के किनारों के द्वारा एक दूसरे से जुड़े हुए हैं. तो इस पेड़ की जड़ 13 मूल्य के साथ एक नोड मूल्य है, जो 5 और 34 मूल्यों के साथ 2 बच्चों नोड्स है. एक subtree पेड़ कि पूरे ट्री की एक उपधारा पर देखने से बस का गठन किया है. 

उदाहरण के लिए, 3 नोड के बाईं subtree पेड़ नोड्स 0, 1, और 2 के द्वारा बनाई गई है. तो, अगर हम एक द्विआधारी खोज वृक्ष के गुणों को वापस जाओ, हम देखते हैं कि पेड़ में प्रत्येक नोड सभी 3 संपत्तियों, अर्थात् के अनुरूप है, केवल छोड़ दिया subtree मूल्यों है कि कम से कम या नोड के मूल्य के बराबर होता है; सभी नोड्स का सही subtree केवल मूल्यों है कि अधिक से अधिक या नोड के मूल्य के बराबर कर रहे हैं, और सभी नोड्स के दोनों को छोड़ दिया और सही subtrees भी द्विआधारी खोज के पेड़ हैं. हालांकि इस पेड़ से अलग दिखता है, यह एक वैध द्विआधारी खोज वृक्ष संख्या के एक ही सेट के लिए. तथ्य की बात के रूप में, वहाँ कई संभव तरीके कि आप बना सकते हैं इन नंबरों से एक वैध द्विआधारी खोज वृक्ष. खैर, पहली एक हम पैदा करने के लिए वापस जाओ. तो क्या हम इन पेड़ों के साथ कर सकते हैं? ठीक है, हम बहुत आसानी से न्यूनतम और अधिकतम मूल्य मिल सकता है. न्यूनतम मूल्यों को हमेशा के लिए छोड़ दिया करने के लिए जा रहा द्वारा पाया जा सकता है जब तक वहाँ कोई और अधिक नोड्स यात्रा करने के लिए कर रहे हैं. इसके विपरीत, के लिए अधिकतम एक मिल बस सही करने के लिए नीचे एक समय में चला जाता है. 

किसी भी अन्य संख्या ढूँढना कि न्यूनतम या अधिकतम नहीं है बस के रूप में आसान है. कहते हैं कि हम 89 नंबर के लिए देख रहे हैं. हम बस प्रत्येक नोड के मूल्य की जाँच करें और छोड़ दिया है या सही करने के लिए जाना है, पर निर्भर करता है कि नोड मान से कम या से अधिक होता है एक के लिए हम देख रहे हैं. तो, 13 के रूट पर शुरू, हम देखते हैं कि अधिक से अधिक 89 है, और इसलिए हम जाने के लिए सही है. तो हम 34 के लिए नोड देखते हैं, और फिर हम जाने के लिए सही है. 89 अभी भी 55 से अधिक है, तो हम सही करने के लिए जा रही जारी रखने. हम तो 144 के मूल्य के साथ एक नोड के साथ आते हैं और बाईं करने के लिए जाना है. लो और निहारना, 89 अभी भी वहाँ है. 

एक और बात यह है कि हम क्या कर सकते है बाहर एक inorder चंक्रमण प्रदर्शन करके सभी नंबरों मुद्रित. एक inorder चंक्रमण सब कुछ subtree में छोड़ बाहर प्रिंट का मतलब नोड ही मुद्रण द्वारा पीछा और फिर सब कुछ सही subtree में मुद्रण द्वारा पीछा किया. उदाहरण के लिए, हमारे पसंदीदा द्विआधारी खोज वृक्ष और बाहर क्रमबद्ध क्रम में संख्या मुद्रित. हम 13 के रूट पर शुरू है, लेकिन 13 मुद्रण से पहले हम बाहर प्रिंट subtree में छोड़ दिया सब कुछ. तो हम 5 के लिए जाना है. हम अभी भी पेड़ में गहरी नीचे जाने के लिए जब तक हम नोड बाएँ सबसे मिल है, जो शून्य है. शून्य मुद्रण के बाद, हम 1 करने के लिए वापस जाने के लिए और कहा कि बाहर प्रिंट. तो हम सही subtree है, जो 2 है के लिए जाना है, और कहा कि बाहर प्रिंट. अब है कि हम कि subtree के साथ कर रहे हैं, हम वापस जाने के 3 के लिए कर सकते हैं और इसे बाहर प्रिंट. वापस ऊपर सतत, हम 5 प्रिंट और फिर 8. अब है कि हम पूरे पूरा कर लिया है subtree छोड़ दिया, हम बाहर 13 मुद्रित कर सकते हैं और सही subtree पर काम शुरू करते हैं. हम 34 के लिए नीचे हॉप, लेकिन 34 मुद्रण से पहले हम अपनी बाईं subtree प्रिंट है. इसलिए हम बाहर मुद्रित करने के लिए 21, तो हम बाहर 34 प्रिंट और इसकी सही subtree जाएँ. के बाद से 55 नहीं छोड़ दिया subtree है, हम इसे प्रिंट बाहर और पर इसकी सही subtree जारी. 144 एक बाएं subtree है, और इसलिए हम बाहर मुद्रित करने के लिए 89, 144 के द्वारा पीछा किया, और अंत में 233 का अधिकार सबसे नोड. वहाँ आप यह है, सभी नंबरों को बाहर से सबसे कम उच्चतम करने के क्रम में मुद्रित कर रहे हैं. 

पेड़ को कुछ जोड़ने के रूप में अच्छी तरह से अपेक्षाकृत दर्दरहित है. हम सभी को करना है यकीन है कि हम 3 द्विआधारी खोज वृक्ष गुण का पालन और फिर मान सम्मिलित जहाँ वहाँ जगह नहीं है. हम कहते हैं कि हम 7 के मूल्य सम्मिलित करना चाहते हैं. 7 के बाद से कम से कम 13 है, हम छोड़ दिया करने के लिए जाना. लेकिन यह 5 से अधिक है, तो हम सही करने के लिए पार. चूंकि यह कम से कम 8 और 8 एक पत्ता नोड है, हम 8 के बाईं बच्चे की 7 जोड़ते हैं. देखा! हम हमारे द्विआधारी खोज वृक्ष एक संख्या को जोड़ दिया है. 

यदि हम बातें जोड़ सकते हैं, हम बेहतर चीजों के रूप में अच्छी तरह से नष्ट करने में सक्षम हो. दुर्भाग्य से हमारे लिए, हटाने थोड़ा और अधिक जटिल है - ज्यादा नहीं है, लेकिन सिर्फ एक छोटा सा. इसमें 3 अलग परिदृश्यों कि हम विचार कर रहे हैं जब द्विआधारी खोज के पेड़ से तत्वों को हटाने. सबसे पहले, सबसे आसान मामला है कि तत्व एक पत्ता नोड है. इस मामले में, हम बस इसे हटा सकते हैं और हमारे व्यापार के साथ पर जाओ. कहते हैं कि हम 7 कि हम सिर्फ जोड़ा हटाना चाहते हैं. ठीक है, हम बस यह पता है, इसे हटाने, और यह बात है. अगले मामला है अगर नोड केवल 1 बच्चा है. यहाँ हम नोड को हटाने के लिए, कर सकते हैं लेकिन हम पहले यह सुनिश्चित करना है subtree है कि अब parentless छोड़ दिया है कनेक्ट नोड के माता पिता के लिए हम सिर्फ नष्ट कर दिया. कहते हैं कि हम हमारे पेड़ से हटाना चाहते हैं 3. हम उस नोड के चाइल्ड तत्व ले और यह नोड के माता पिता को देते हैं. इस मामले में, हम अब 5 करने के लिए कर रहे हैं 1 संलग्न. यह एक समस्या के बिना काम करता है क्योंकि हम जानते हैं द्विआधारी खोज वृक्ष संपत्ति के अनुसार, 3 के बाईं subtree में है कि सब कुछ कम से कम 5 था. अब जब कि 3 subtree ध्यान रखा जाता है, हम इसे हटा सकते हैं. तीसरे और अंतिम सबसे जटिल मामला है. यह मामला है जब हम हटाना चाहते नोड 2 बच्चों की है. आदेश में यह करने के लिए, हम पहले नोड कि अगला सबसे बड़ा मान है खोजने के लिए है, स्वैप दो, और फिर सवाल में नोड हटा. नोड कि अगला सबसे बड़ा मान 2 बच्चों ही नहीं हो सकता है नोटिस के बाद से अपनी बाईं बच्चे अगला सबसे बड़ा के लिए एक बेहतर उम्मीदवार होगा. इसलिए, 2 बच्चों के साथ एक नोड को हटाने 2 नोड्स के गमागमन करने के लिए बराबर है, और फिर हटाने से 1 2 aforementioned नियमों के द्वारा नियंत्रित किया जाता है. उदाहरण के लिए, हम कहते हैं कि हम जड़ नोड, 13 हटाना चाहते हैं. पहली बात हम करते है हम पेड़ में अगला सबसे बड़ा मान जो इस मामले में, 21 है. हम तो 2 नोड्स स्वैप, 13 एक पत्ती और 21 केंद्रीय समूह नोड. अब हम सिर्फ 13 को नष्ट कर सकते हैं. 

जैसा कि पहले के लिए alluded, वहाँ कई संभव करने के लिए एक वैध द्विआधारी खोज वृक्ष बनाने के तरीके हैं. हमारे लिए दुर्भाग्य से, कुछ अन्य लोगों से भी बदतर हैं. उदाहरण के लिए, क्या होता है जब हम एक द्विआधारी खोज के पेड़ का निर्माण संख्याओं की एक सॉर्ट की गई सूची से? सभी बस संख्या हर कदम पर सही करने के लिए जोड़ा गया है. , जब हम एक नंबर के लिए खोज करने के लिए करना चाहते हैं हम कोई विकल्प नहीं है, लेकिन केवल सही में हर कदम पर देखने के लिए. यह सब पर रैखिक खोज की तुलना में बेहतर नहीं है. हालांकि हम उन्हें यहाँ नहीं कवर किया जाएगा, वहाँ अन्य, अधिक जटिल हैं, डेटा संरचनाओं कि यकीन है कि ऐसा नहीं होता है. हालांकि, एक साधारण बात है कि इस से बचने के लिए किया जा सकता है सिर्फ अनियमित इनपुट मूल्यों फेरबदल. यह लगभग नामुमकिन है कि संख्या की एक यादृच्छिक मौका द्वारा shuffled सूची हल है. अगर इस मामले थे, कैसीनो के कारोबार में लंबे समय तक नहीं रहना होगा. 

वहाँ तुम्हारे पास है. अब आप द्विआधारी खोज और द्विआधारी खोज के पेड़ के बारे में जानते हैं. मैं पैट्रिक Schmid हूँ, और इस CS50 है. [CS50.TV] एक स्पष्ट तरीके से सूची स्कैन होगा ... [बीप] ... आइटम की संख्या ... हां [हंसते हुए] ... 234 ... augh के नोड के बाद. >> हाँ! यही था -