केविन SCHMID: कभी कभी, जब इमारत एक कार्यक्रम, आप का उपयोग करने के लिए चाहते हो सकता है एक एक शब्दकोश के रूप में जाना जाता आंकड़ा संरचना. जो कर रहे हैं एक शब्दकोश नक्शे चाबी, आमतौर पर तार, मूल्यों को, ints, घर का काम, किसी वस्तु के लिए एक सूचक, हम चाहते हैं कि जो भी हो. यह सिर्फ साधारण शब्दकोशों की तरह है परिभाषाओं के माध्यम से उस नक्शे शब्द. 

शब्दकोशों के साथ हमें प्रदान जानकारी स्टोर करने की क्षमता कुछ के साथ जुड़े और बाद में इसे देखो. तो कैसे हम वास्तव में लागू करते हैं एक सी कोड है, कहते हैं, में शब्दकोश कि हम कर सकते हैं हमारे कार्यक्रमों में से एक में उपयोग करें? खैर, तरीके का एक बहुत कुछ कर रहे हैं कि हम एक शब्दकोश लागू कर सकता है. 

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

अभी के लिए, कि हम कल्पना करते हैं कुंजी के रूप में तार का उपयोग करना चाहते हैं. की एक संभावना के बारे में बात करते हैं, एक आंकड़ा संरचना एक Trie कहा जाता है. तो यहाँ एक दृश्य प्रतिनिधित्व है एक Trie की. 

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

जिसका प्रकार एक वस्तु संरचना है नोड दो भागों में है डेटा और बच्चों को बुलाया. हम एक टिप्पणी के रूप में डेटा हिस्सा छोड़ दिया है एक घटक होने की जगह संरचना नोड है जब घोषणा एक सी कार्यक्रम में शामिल किया. एक नोड के डेटा हिस्सा एक हो सकता है इंगित करने के लिए बूलियन मान जाए या नहीं नोड पूरा होने का प्रतिनिधित्व करता है एक शब्दकोश में कुंजी या यह एक हो सकता है परिभाषा का प्रतिनिधित्व स्ट्रिंग इस शब्दकोश में एक शब्द की. 

हम इंगित करने के लिए एक स्माइली चेहरे का उपयोग करेंगे डेटा एक नोड में मौजूद है. में 26 तत्व हैं हमारे बच्चों सरणी, एक सूचकांक अल्फाबेट प्रति. हम महत्व देखेंगे जल्द ही इस बात का. 

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

, बड़ा चित्र में ध्यान दें कि जब हम अन्य नोड के लिए एक सूचक आकर्षित, यह कोई फर्क नहीं पड़ता जहां Arrowhead कि अन्य नोड मिलता है. हमारे नमूना शब्दकोश Trie शामिल दो शब्द, कि और जूम. का एक उदाहरण के माध्यम से चलते हैं एक कुंजी के लिए डेटा को देख रहे हैं. 

हम को देखने के लिए चाहते थे कि मान लीजिए कुंजी स्नान के लिए मूल्य इसी. हम अपने देखो शुरू करेंगे रूट नोड पर. तो फिर हम अपने से पहले पत्र ले जाऊँगा , कुंजी बी, और इसी खोजने हमारे बच्चों सरणी में हाजिर. वास्तव में 26 धब्बे हैं कि नोटिस सरणी के प्रत्येक अक्षर के लिए एक में वर्णमाला. और हम स्पॉट का प्रतिनिधित्व होगा आदेश में वर्णमाला के अक्षर. 

हम तो दूसरा सूचकांक में देख लेंगे सामान्य में बी के सूचकांक में एक,, अगर हम कुछ अल्फाबेट सी हम हैं इसी मौके का निर्धारण कर सकता का उपयोग कर बच्चों सरणी में इस तरह एक गणना. हम एक बड़े बच्चों इस्तेमाल किया जा सकता था हम देखो की पेशकश करना चाहते थे सरणी अगर अक्षरों का एक व्यापक रेंज के साथ कुंजी, इस तरह पूरे के रूप में ASCII वर्ण सेट. 

इस मामले में, सूचक हमारे बच्चों सरणी में सूचकांक एक अशक्त नहीं है. इसलिए हम देख जारी रखेंगे कुंजी स्नान अप. हम कभी भी एक शून्य सूचक का सामना करना पड़ा, तो बच्चों में उचित स्थान पर सरणी हम नोड्स तय की है, जबकि फिर हम कि हम कहने के लिए होगा उस चाबी के लिए कुछ भी नहीं मिल सकता है. 

अब, हम दूसरे पत्र के ले जाऊँगा हमारे कुंजी, एक, और जारी रखने के लिए निम्न इस तरह से संकेत है कि हम जब तक हमारे कुंजी के अंत तक पहुँचते हैं. हम बिना चाबी के अंत तक पहुँचते हैं किसी भी मृत समाप्त होता मार, अशक्त संकेत, मामला यहाँ के रूप में है, तो हम केवल एक और बात की जांच करने के लिए है. यह महत्वपूर्ण है वास्तव में शब्दकोश में? 

यदि हां, तो हम एक अच्छी तरह से, एक मूल्य का पता लगाना चाहिए हमारे चित्र में स्माइली चेहरा आइकन जहां शब्द समाप्त होता है. साथ संग्रहीत वहाँ कुछ और है तो डेटा, तो हम इसे वापस कर सकते हैं. उदाहरण के लिए, कुंजी चिड़ियाघर में नहीं है हम कर सकते थे, भले ही शब्दकोश, कभी बिना इस कुंजी के अंत तक पहुँच , एक शून्य सूचक मार जबकि हम Trie के माध्यम से पुनरावृति. 

हम, कुंजी स्नान को देखने की कोशिश की तो पिछले नोड के सरणी सूचकांक करने के लिए दूसरा, , अक्षर एच के लिए होगा इसी एक शून्य सूचक का आयोजन किया है. इसलिए स्नान शब्दकोश में नहीं है. और इसलिए एक Trie कुंजी है कि आप में अनूठा है स्पष्ट रूप में संग्रहीत नहीं कर रहे हैं डेटा संरचना. तो कैसे हम कुछ सम्मिलित है एक Trie में? 

की कुंजी सम्मिलित करते हैं हमारे Trie में चिड़ियाघर. याद रखें कि एक नोड में एक स्माइली चेहरा एक सरल करने के लिए कोड में अनुरूप सकता है कि चिड़ियाघर इंगित करने के लिए बूलियन मूल्य शब्दकोश में है या यह हो सकता है अधिक जानकारी के लिए संगत हम कुंजी चिड़ियाघर के साथ संबद्ध करना चाहते हैं, की परिभाषा की तरह शब्द है या कुछ और. कुछ मायनों में, इस प्रक्रिया को सम्मिलित करने के लिए एक Trie में कुछ करने के लिए इसी तरह की है एक Trie में कुछ देख रहे हैं. 

हम फिर से रूट नोड के साथ शुरू करेंगे निम्नलिखित संकेत के लिए इसी हमारी प्रमुख का पत्र. सौभाग्य से, हम संकेत का पालन करने में सक्षम थे हम पर पहुंच गया जब तक सभी तरह कुंजी के अंत. चिड़ियाघर शब्द के उपसर्ग है के बाद से का एक सदस्य है जो जूम, शब्दकोश, हम की जरूरत नहीं है किसी भी नए नोड्स आवंटित. 

हम इंगित करने के लिए नोड संशोधित कर सकते हैं करने के लिए प्रमुख पात्रों का पथ यह हमारे शब्दकोश में एक महत्वपूर्ण का प्रतिनिधित्व करता है. अब, चलो डालने की कोशिश करते हैं Trie में प्रमुख स्नान. हम जड़ नोड में शुरू करेंगे और फिर संकेत का पालन करें. लेकिन इस स्थिति में, हम एक मृत मारा हम को प्राप्त करने के लिए सक्षम होने से पहले खत्म कुंजी के अंत. अब, हम कुछ नया आवंटित करने की आवश्यकता होगी नोड्स एक नया आवंटित करने की आवश्यकता होगी प्रत्येक शेष के लिए नोड हमारी प्रमुख का पत्र. 

इस मामले में, हम सिर्फ जरूरत एक नए नोड आवंटित करने के लिए. तो फिर हम एच सूचकांक बनाने की आवश्यकता होगी इस नए नोड संदर्भ में है. एक बार फिर, हम करने के लिए नोड को संशोधित कर सकते हैं संकेत मिलता है कि वर्ण का पथ यह करने के लिए अग्रणी एक का प्रतिनिधित्व करता है हमारे शब्दकोश में कुंजी. के asymptotic के बारे में कारण दो. इन के लिए हमारी प्रक्रिया की जटिलता दो ऑपरेशन. 

हम नोटिस कि दोनों ही मामलों में नंबर के बारे में हमारी एल्गोरिथ्म किया गया था ने कदम उठाए की संख्या के अनुपात कीवर्ड में पत्र. यह सही है. तुम एक में एक शब्द को देखना चाहता हूँ Trie आप बस के माध्यम से पुनरावृति करने की आवश्यकता पत्र एक के बाद एक जब तक आप या तो शब्द के अंत या तक पहुँचने Trie में एक मरा हुआ अंत मारा. 

और अगर आप एक कुंजी को सम्मिलित करना चाहते हैं जब का उपयोग कर एक Trie में मूल्य जोड़ी प्रक्रिया हम सबसे खराब स्थिति पर चर्चा की आप एक नया नोड का आवंटन होगा प्रत्येक अक्षर के लिए. और हम उस आवंटन मान लेंगे एक निरंतर समय ऑपरेशन है. हम कुंजी लंबाई को लगता है कि यदि ऐसा है तो एक निश्चित स्थिर, दोनों से घिरा सम्मिलन और ऊपर देखो लगातार कर रहे हैं एक Trie के लिए समय आपरेशनों. 

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

इसके विपरीत, कहते हैं, के लिए प्रविष्टियों में उनका कहना है, एक हैश तालिका बनाने के लिए जाता भविष्य में धीमी देखो. यह पहली बार में अपील ध्वनि, हो सकता है हम ध्यान में रखना चाहिए कि एक अनुकूल asymptotic जटिलता नहीं करता इसका मतलब यह है कि अभ्यास में डेटा संरचना जरूरी है तिरस्कार से परे. हम भी स्टोर करने के लिए विचार करना चाहिए कि एक सबसे खराब में जरूरत है कि हम एक Trie, में शब्द मामले, नोड्स के एक नंबर आनुपातिक शब्द ही की लंबाई के लिए. 

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

लेकिन इन तंत्रों सबसे अच्छा काम जब स्मृति accesses कॉम्पैक्ट में किया जाता है क्षेत्रों या क्षेत्रों. और एक Trie की नोड्स रहते सकता उस ढेर में कहीं. लेकिन इन व्यापार नापसंद कर रहे हैं हम पर विचार करना चाहिए कि. 

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

एक Trie अनोखे उपयोगी है इस ऑपरेशन के लिए. इसके माध्यम से पुनरावृति करने के लिए सरल है हर किरदार के लिए Trie उपसर्ग. बस, एक को देखने के ऑपरेशन की तरह हम संकेत का पालन कर सकता है चरित्र से चरित्र. फिर, हम के अंत में आने पर उपसर्ग, हम के माध्यम से पुनरावृति सकता डेटा संरचना का शेष भाग कुंजियों के किसी भी परे के बाद इस बिंदु उपसर्ग है. 

यह इस सूची प्राप्त करने के लिए भी आसान है के बाद से वर्णमाला क्रम में बच्चों सरणी के तत्वों वर्णानुक्रम आदेश दिए हैं. तो उम्मीद है कि आप पर विचार करेंगे देने की एक कोशिश की कोशिश करता है. मैं केविन श्मिड हूँ, और इस CS50 है. 

आह, यह शुरुआत है गिरावट के. मैं माफी चाहता हूँ. माफ़ कीजिए. माफ़ कीजिए. माफ़ कीजिए. 

चार हड़ताल. मैं बाहर हूँ. माफ़ कीजिए. माफ़ कीजिए. माफ़ कीजिए. व्यक्ति बनाने के लिए खेद है जो इस पागल हो जाना संपादित करने के लिए है. 

माफ़ कीजिए. माफ़ कीजिए. माफ़ कीजिए. माफ़ कीजिए. 

स्पीकर 1: अच्छी तरह से किया. यह वास्तव में अच्छी तरह से किया गया था.