>> [संगीत बजाना]
डौग लॉयड: तो हम करीब inching किया गया है और करीब है कि डेटा की होली ग्रेल
हम सम्मिलित कर सकते हैं कि संरचनाओं, एक में, से हटा सकते हैं, और देखो
लगातार समय में।
ठीक है।
यही कारण है कि लक्ष्य की तरह है।
हम ऐसा करने में सक्षम होना चाहता हूँ बातें बहुत, बहुत जल्दी।
>> हम यहाँ जब यह मिल गया है हम कोशिश करता है के बारे में बात कर रहे हैं?
ठीक है, चलो एक नज़र रखना।
इसलिए हम कई देखा है विभिन्न डेटा संरचनाओं
इस बात का मानचित्रण संभाल महत्वपूर्ण मूल्य जोड़े तथाकथित,
डेटा के कुछ टुकड़े मानचित्रण डेटा के कुछ अन्य टुकड़ा करने के लिए
तो हम कहाँ खोजने के लिए पता संरचना में जानकारी।
>> तो सरणी के लिए, उदाहरण के लिए, प्रमुख तत्व सूचकांक या सरणी है
स्थान 0 या सरणी 1 और इतने पर।
और मान डेटा है कि उस स्थान पर मौजूद है।
तो सरणी 0 में क्या भंडारित किया जाता है?
क्या सिर्फ बनाम सरणी 1 में संग्रहित है 0 और 1, चाबी होगा।
>> एक हैश तालिका के साथ यह है एक ही विचार की तरह।
एक हैश तालिका के साथ, हम इस हैश है हैश कोड उत्पन्न करता है कि समारोह।
इसलिए महत्वपूर्ण डेटा के हैश कोड है।
और मूल्य है, विशेष रूप से हम श्रृंखलन के बारे में बात की थी
हैश टेबल पर वीडियो में, डेटा की है कि लिंक सूची है
कि कि हैशकोड को hashes।
ठीक है।
एक और दृष्टिकोण के बारे में क्या इस विधि, हालांकि?
एक विधि के बारे में क्या, जहां कुंजी, अद्वितीय होने की गारंटी है
एक हैश तालिका, जहां हम कर सकते थे के विपरीत डेटा के दो टुकड़े के साथ खत्म
एक ही हैशकोड कर रही है।
और फिर हम साथ सौदा किया है कि या तो जांच कर या अधिक द्वारा
अधिमानतः है कि समस्या को ठीक करने के लिए श्रृंखलन।
>> तो अब हम गारंटी ले सकते हैं कि हमारे प्रमुख अद्वितीय होगा।
और हमारे मूल्य क्या था आसान के रूप में अभी कुछ
चाहे वह हमें बताता है कि के रूप में सही और गलत जानकारी के या नहीं कि टुकड़ा
संरचना में मौजूद है?
एक बूलियन एक बिट के रूप में सरल किया जा सकता है।
वास्तविक यह शायद एक एक बिट से अधिक होने की संभावना बाइट।
लेकिन उस की तुलना में बहुत छोटा है एक 50-चरित्र स्ट्रिंग शायद भंडारण,
उदाहरण के लिए।
>> कोशिश करता है तो, टेबल हैश करने के लिए समान है, जो गठबंधन सरणियों और लिंक सूची,
कोशिश करता है सरणियों गठबंधन, संरचनाओं, और संकेत
साथ में डेटा स्टोर करने के लिए है कि एक दिलचस्प तरीका
से बहुत अलग हम अब तक देखा है कुछ भी।
अब हम एक रूपरेखा के रूप में डेटा का उपयोग इस डेटा संरचना नेविगेट करने के लिए।
और हम पालन कर सकते हैं रोडमैप, हम कर सकते हैं, तो
से डेटा का पालन करें अंत करने के लिए शुरुआत है, हम करेंगे
डेटा है कि पता है कि क्या Trie में मौजूद हैं।
>> और हम नक्शे का पालन नहीं कर सकते हैं सब पर समाप्त करने के लिए, जिसका अर्थ से,
डेटा मौजूद नहीं कर सकते।
फिर, चाबी यहाँ हैं अद्वितीय होने की गारंटी।
इसलिए एक हैश तालिका के विपरीत, हम कभी नहीं हूँ यहां टक्करों के साथ सौदा किया है।
और डेटा की कोई दो टुकड़े वास्तव में एक ही खाका
जब तक कि डेटा समान है।
>> हम जॉन, तब सम्मिलित हैं हम जॉन के लिए खोज करते हैं।
यही कारण है कि के दो समान टुकड़े है डेटा, ठीक है, हम के माध्यम से देख रहे हैं।
लेकिन अन्यथा, किसी भी डेटा के दो टुकड़े कर रहे हैं
अनूठा roadmaps है की गारंटी इस डेटा संरचना के माध्यम से।
और हम पर एक नज़र लेने के लिए जा रहे हैं बस एक पल में इस का एक दृश्य।
>> हम करने के लिए कोशिश कर रहा द्वारा इस करूँगा एक नए डेटा संरचना बनाने,
निम्नलिखित महत्वपूर्ण मूल्य जोड़े मानचित्रण।
इस मामले में, हम का उपयोग करने के लिए नहीं जा रहे हैं एक बूलियन के रूप में सरल रूप में कुछ।
हम वास्तव में स्ट्रिंग की दुकान है।
और कहा कि स्ट्रिंग के लिए जा रहा है एक विश्वविद्यालय का नाम हो।
>> और महत्वपूर्ण वर्ष होने जा रहा है कि विश्वविद्यालय की स्थापना की गई थी।
विश्वविद्यालयों के लिए सभी वर्षों चार अंक होने जा रहे हैं।
और इसलिए हम करने के लिए उन चार अंकों का उपयोग करेंगे इस डेटा संरचना के माध्यम से नेविगेट।
और हम फिर से, देखता हूँ, कैसे हम सिर्फ एक दूसरे में ऐसा करते हो।
>> पथ के अंत में, हम नाम देखेंगे
मेल खाती है कि विश्वविद्यालय की उस कुंजी के लिए, उन चार अंक।
एक Trie के पीछे मूल विचार हम एक केंद्रीय मार्ग है।
तो एक पेड़ की तरह इसके बारे में सोचते हैं।
और इस वर्तनी में समान है और एक पेड़ के लिए अवधारणा में।
आम तौर पर हम के बारे में लगता है कि जब असली दुनिया में पेड़,
वे में है कि एक जड़ जमीन और वे ऊपर की ओर बढ़ने
और वे शाखाएं हैं और वे छोड़ दिया है।
और मूल रूप से विचार एक Trie, बिल्कुल वैसी ही है
उस रूट लंगर डाले है सिवाय आकाश में कहीं।
और पत्तियों तल पर हैं।
>> तो यह एक पेड़ लेने की तरह की तरह है और सिर्फ यह उल्टा flipping।
लेकिन फिर भी शाखाएं हैं।
और उन लोगों के लिए हमारे रास्ते होगा, उन हमारे कनेक्शन हो जाएगा
पत्तियों को जड़ से।
इस मामले में, उन पथ, उन शाखाओं
हमें बताओ कि अंकों के साथ चिह्नित कर रहे हैं किस तरह से हम कर रहे हैं, जहां से जाने के लिए।
>> हम एक 0 देखते हैं, तो हम इस शाखा नीचे जाना, हम एक 1 देखें, तो हम इस शाखा नीचे जाना,
और तो और इतने पर।
खैर, यह क्या मतलब है?
वैसे, यह मतलब है कि हर जंक्शन बिंदु पर
और हर नोड मध्यम और हर शाखा,
संभव 10 देखते हैं हम जा सकते हैं कि स्थानों पर।
तो 10 संकेत देखते हैं हर स्थान से।
>> कोशिश करता है एक कहाँ मिल सकता है और यह है किसी के लिए डराना थोड़ा सा
जो की एक बहुत कुछ नहीं है पहले कंप्यूटर विज्ञान के क्षेत्र में अनुभव।
लेकिन कोशिश करता है वास्तव में बहुत भयानक हैं।
और यदि आप उनके साथ काम करने का मौका
और तुम खुदाई में करने के लिए तैयार कर रहे हैं और उन लोगों के साथ प्रयोग,
वे वास्तव में काफी दिलचस्प हो डेटा संरचनाओं के साथ काम करने के लिए।
हम एक तत्व सम्मिलित करना चाहते हैं Trie में, हम सब करने की ज़रूरत है
सही मार्ग का निर्माण किया गया है पत्ती को जड़ से।
यहाँ क्या हर कदम पर साथ है रास्ते की तरह लग सकता है।
हम एक नए डेटा को परिभाषित करने के लिए जा रहे हैं एक नए नोड के लिए संरचना एक Trie बुलाया।
>> और कहा कि आंकड़ों के अंदर संरचना दो टुकड़े कर रहे हैं।
हम स्टोर करने के लिए जा रहे हैं एक विश्वविद्यालय के नाम।
और हम स्टोर करने के लिए जा रहे हैं संकेत की एक सरणी
एक ही प्रकार के अन्य नोड्स के लिए।
तो, फिर, यह है कि तरह है हर जगह की अवधारणा की
हम 10 संभव पर कर रहे हैं, हम जा सकते हैं स्थानों पर।
हम एक 0 देखते हैं, तो हम इस शाखा नीचे जाना।
हम एक 1 देखते हैं, तो इस शाखा, और इतने पर और इतने पर और इतने पर।
हम 9 कहते हैं, हम इस शाखा नीचे जाना।
हर जंक्शन बिंदु पर तो हम 10 संभव स्थानों जा सकते हैं।
इसलिए हर नोड 10 संकेत को रोकने के लिए है 10 अन्य नोड्स के लिए अन्य नोड्स, करने के लिए।
>> और हम भंडारण कर रहे हैं डेटा है विश्वविद्यालय के सिर्फ नाम।
तो चलो एक Trie का निर्माण करते हैं।
के एक जोड़े को सम्मिलित करते हैं हमारे Trie में आइटम की।
, ऊपर से ही तो यह हमारे रूट नोड है।
यह शायद कुछ होने जा रहा है आप की घोषणा विश्व स्तर पर जा रहे हैं।
और अगर आप को बनाए रखने के लिए विश्व स्तर पर जा रहे हैं हमेशा इस नोड के लिए एक सूचक।
>> तुम्हें पता है, कहने के लिए जा रहे हैं जड़ के बराबर होती है, और आप कर रहे हैं
खुद Trie नोड malloc के लिए जा रहा है।
और अगर तुम कभी नहीं जा रहे हैं फिर जड़ को छूने के लिए।
आप चाहते हैं हर बार के माध्यम से नेविगेट शुरू,
यदि आप किसी अन्य सूचक सेट इस तरह के सफर के रूप में, जड़ के बराबर है,
जो उदाहरण मैं है मेरे वीडियो में से कई में उपयोग
यहां के ढेर और कतारों पर और लिंक सूचियों और इतने पर।
>> आप एक और सूचक सेट चंक्रमण के लिए Trav बुलाया।
और अगर आप नेविगेट करने में सफर का उपयोग डेटा संरचना के माध्यम से।
तो चलो इस कैसे लग सकता है देखते हैं।
इसलिए अभी, क्या एक नोड की तरह दिखता है?
खैर, अभी हमारे डेटा के रूप में संरचना घोषणा संकेत
हम एक स्ट्रिंग है, जो इस मामले में खाली है।
यहाँ कुछ भी नहीं है।
>> और 10 संकेत की एक सरणी।
और अभी, हम केवल इस Trie में एक नोड है।
उस में और कुछ नहीं है।
तो उन के सभी 10 बिंदु संकेत अशक्त करने के लिए।
यही कारण है कि लाल को इंगित करता है।
>> स्ट्रिंग हार्वर्ड सम्मिलित करते हैं।
के विश्वविद्यालय सम्मिलित करते हैं इस Trie में हार्वर्ड, जो
साल 1636 में स्थापित किया गया था।
हम कुंजी का उपयोग करना चाहते हैं, 1636 में, हम कर रहे हैं जहां हमें बताने के लिए
Trie में हार्वर्ड स्टोर करने के लिए जा रहा है।
अब, हम ऐसा कैसे कर सकता है?
>> यह कुछ इस तरह लग सकता है।
हम जड़ में शुरू करते हैं।
और हम हम जा सकते हैं इन 10 स्थानों के लिए है।
जड़ बस किसी भी तरह है Trie के दूसरे नोड।
हम यहाँ से जा सकते हैं 10 स्थानों रहे हैं।
>> हम कहाँ शायद करना चाहते हैं कुंजी 1636 है, तो जाने के लिए?
वास्तव में दो विकल्प है।
ठीक है।
हम से प्रमुख निर्माण कर सकते हैं सही छोड़ दिया और 6 के साथ शुरू करने के लिए।
या हम से चाबी का निर्माण कर सकता सही करने के लिए छोड़ दिया और एक के साथ शुरू करते हैं।
>> यह शायद अधिक है एक इंसान के रूप में सहज
हम करेंगे समझने के लिए सिर्फ सही करने के लिए छोड़ दिया जाना।
और इसलिए मैं सम्मिलित करना चाहते हैं, तो इस Trie में हार्वर्ड,
मैं शायद शुरू करना चाहते हैं जड़ में शुरू करने से,
मेरे 10 विकल्पों को देख मेरे सामने, और कह रही
मैं एक रास्ते नीचे जाना चाहता हूँ।
ठीक।
>> अब, एक पथ वर्तमान में रिक्त है।
इसलिए मुझे लगता है कि रास्ते नीचे आगे बढ़ना चाहते हैं, तो Trie में इस तत्व डालने के लिए,
मैं एक है, एक नया नोड malloc के लिए है वहाँ इंगित करें और फिर मैं जाने के लिए अच्छा कर रहा हूँ।
>> इसलिए मैं मूल रूप से एक में हूँ बिंदु जहां मैं खड़ा हूँ
पेड़ या की जड़ में Trie और 10 शाखाएं हैं।
लेकिन हर शाखा है एक इसे के सामने गेट।
ठीक है।
कुछ भी नहीं है क्योंकि बाकी है।
कोई सुरक्षित रास्ता।
यही कारण है कि कुछ भी नहीं है कि इसका मतलब है उन शाखाओं में से किसी भी नीचे।
मैं निर्माण शुरू करना चाहते हैं कुछ और, मैं गेट निकालना चाहते हैं।
मैं गेट निकालना चाहते हैं नंबर 1 के सामने।
और मुझे लगता है कि नीचे चलना चाहते हैं।
और मैं निर्माण करना चाहते हैं मेरे लिए एक और जगह जाने के लिए।
>> और कहा कि मैं यहाँ क्या किया है।
तो एक नहीं रह अशक्त करने के लिए बताते हैं।
मैं इसे अब यहाँ नीचे जाने के लिए सुरक्षित है कहा है।
मैं एक और नोड का निर्माण किया।
और मुझे लगता है कि नोड के लिए मिलता है, मैं बनाने के लिए एक और फैसला किया है।
कहाँ मैं यहाँ से जाने के लिए जा रहा हूँ?
>> खैर, मैं पहले से ही एक नीचे चला गया है।
तो अब मैं शायद 6 नीचे जाने के लिए चाहते हैं।
ठीक है।
फिर से, मैं मैं चुन सकते हैं 10 स्थानों पर है।
तो चलो अब 6 नंबर नीचे चलते हैं।
तो मैं गेट स्पष्ट नंबर 6 के सामने।
और मैं वहाँ नीचे चलते हैं।
और मैं अन्य नोड का निर्माण।
और मैं एक और जंक्शन बिंदु पर पहुंच गए हैं।
>> फिर, मैं 10 विकल्प हैं मैं कहाँ जा सकता है के लिए।
मैं 1-6 स्थानांतरित किया है।
तो अब मैं शायद 3 में जाना चाहते हैं।
3, कहीं नहीं मैं नहीं जा सकती है।
तो मैं रास्ता साफ करने के लिए है और अपने आप को एक नए अंतरिक्ष का निर्माण।
और फिर मैंने जाना चाहते हो जहां 3 से?
मैं नीचे 6 जाना चाहता हूँ।
>> और, फिर से, मैं करने के लिए किया था यह करने के लिए रास्ता साफ है।
तो अब मैं बनाने डालने के लिए मेरी चाबी का उपयोग किया है नोड्स इस Trie का निर्माण शुरू किया।
मैं रूट पर शुरू कर दिया है।
मैं 1636 से नीचे चला गया है।
और अब मैं नीचे हूँ वहाँ उस नोड पर।
और आप करने में सक्षम हो सकता है यह अपनी स्क्रीन पर देखते हैं।
>> यह पीले रंग में प्रकाश डाला है।
मैं वर्तमान में हूँ कि जहां।
मेरे कुंजी किया जाता है।
मैं अपने कुंजी में हर स्थिति को समाप्त किया है।
तो मैं किसी भी आगे नहीं जा सकते।
इस बिंदु पर, सब मैं तो वास्तव में ठीक है, का कहना है कि करने की ज़रूरत है।
यह एक तरह से देख तरह है जमीन पर नीचे,
आप envisioning रहे हैं खुद पथ के इस प्रकार के रूप में
अलग कनेक्शन के साथ।
क्रमबद्ध के नीचे और एक तरह से देख जमीन पर हार्वर्ड स्प्रे पेंटिंग।
यही कारण है कि इस का नाम है।
कि इस स्थान पर क्या है पता है।
हम जड़ में शुरू और हम नीचे जाना है 1 और फिर 6 और फिर 3 और फिर 6,
हम कहाँ हैं?
खैर, हम नीचे नजर डालें तो और हम तो, हार्वर्ड देखना
हम हार्वर्ड था कि पता रास्ते पर आधारित 1636 में स्थापित
हम इस डेटा संरचना को लागू कर रहे हैं।
तो यह है कि उम्मीद है कि सीधा था।
हम दो और सम्मिलन क्या करने जा रहे हैं।
और उम्मीद है कि यह करने में मदद करेंगे इस दो बार अधिक किया।
>> अब, चलो एक और विश्वविद्यालय डालने दें।
चलो इस Trie में येल सम्मिलित करते हैं।
येल 1701 में स्थापित किया गया था।
इसलिए हम पर शुरू करेंगे जड़ है, हम हमेशा करते हैं।
और हम एक चंक्रमण सूचक निर्धारित किया है।
हम के माध्यम से स्थानांतरित करने के लिए उपयोग करने के लिए जा रहे हैं।
हम चाहते हैं पहली बात ऐसा एक रास्ता नीचे जाना है।
यही कारण है कि हमारे प्रमुख के पहले अंक है।
सौभाग्य से, हालांकि, हम नहीं करते किसी भी काम को इस समय क्या करना है।
1 पथ पहले से ही मंजूरी दे दी है।
मैं पहले जब मैं इसे मंजूरी दे दी है 1636 में हार्वर्ड डालने गया था।
तो मैं सुरक्षित रूप से स्थानांतरित कर सकते हैं 1 नीचे और सिर्फ वहाँ जाओ।
1 नीचे स्थानांतरित कर सकते हैं।
>> अब, हालांकि, मैं 7 में जाना चाहते हैं।
मैं 6 में जिस तरह से मंजूरी दे दी।
मैंने सोचा कि मैं सुरक्षित रूप से पता कर सकते हैं 6 रास्ते नीचे आगे बढ़ना है।
लेकिन मैं 7 पथ पर आगे बढ़ने की जरूरत।
तो मैं क्या करने की जरूरत है?
खैर, पहले की तरह, मैं बस जरूरत है गेट स्पष्ट करने, रास्ते से हट जाओ,
और 7 पथ से एक नया नोड का निर्माण।
ऐसे ही।
>> तो अब मैं एक और फिर 7 स्थानांतरित किया है।
और अब, नोटिस की तरह मैं कर रहा हूँ के इस नए Subbranch पर।
ठीक है।
16 से बाकी सब कुछ पर, मैं के बारे में परवाह नहीं है।
मैं 16 के लिए कुछ भी नहीं कर रहा हूँ।
मैं 17 सामान कर रहा हूँ।
>> तो अब 17 से पर, मैं करने के लिए है एक तरह से यहां नए ट्रेल्स ज्वाला।
अगले अंकों मेरी चाबी 0 है।
मैं स्पष्ट रूप से कहीं भी नहीं मिल सकता।
मैं सिर्फ इस नोड का निर्माण किया।
इसलिए मैं कोई पता है वहाँ आगे यहाँ से रास्तों।
तो मैं एक अपने आप को बनाने के लिए है।
>> तो मैं एक नया नोड malloc और वहाँ शून्य बिंदु है।
और फिर एक और बार, मैं malloc एक नए नोड और वहाँ एक बिंदु है।
फिर से, मैं मेरी चाबी, 1701 को समाप्त किया है।
तो मैं नीचे देखो और मैं येल पेंट स्प्रे।
यही कारण है कि इस नोड का नाम है।
>> और इसलिए अब मैं कभी येल देखने के लिए अगर जरूरत है तो इस Trie में, मैं जड़ में शुरू किया गया है,
मैं 1701 से नीचे जाना है, और नीचे देखो।
और मैं येल स्प्रे देखते हैं तो तब, जमीन पर चित्रित
मैं येल इस Trie में मौजूद है।
चलो एक और करते हैं।
चलो इस में डार्टमाउथ सम्मिलित करते हैं 1769 में स्थापित किया गया था, जो Trie,।
>> फिर जड़ में शुरू करो।
मेरी चाबी का मेरा पहला अंक 1 है।
मैं सुरक्षित रूप से उस रास्ते नीचे स्थानांतरित कर सकते हैं।
यही कारण है कि पहले से ही मौजूद है।
मेरी चाबी के अगले अंक 7 है।
मैं सुरक्षित रूप से उस रास्ते नीचे स्थानांतरित कर सकते हैं।
यह रूप में अच्छी तरह से मौजूद है।
>> मेरी अगली 6 है।
यहाँ से, मैं वर्तमान में हूँ, जहां से कि मध्य नोड में वहाँ पीले रंग में,
6 वर्तमान में बंद बंद कर दिया है।
मुझे लगता है कि रास्ते नीचे जाना चाहते हैं, मैं इसे अपने आप का निर्माण किया है।
तो मैं एक नया नोड malloc करेंगे और वहाँ 6 बिंदु है।
और फिर, फिर से, मैं कर रहा हूँ यहाँ नए ट्रेल्स प्रज्वलन।
>> तो मैं एक नया नोड malloc से इतना है कि अब तो उस node-- पथ नंबर 9-- और
मैं 1769 यात्रा, और मैं नीचे देखो।
कुछ भी वर्तमान में नहीं है वहाँ चित्रित स्प्रे।
मैं डार्टमाउथ लिख सकते हैं।
और मैं डाला है Trie में डार्टमाउथ।
>> तो यह है कि डालने है Trie में बातें।
अब हम चीजों के लिए खोज करना चाहते हैं।
हम कैसे Trie में चीजों के लिए खोज करते हैं?
खैर, यह बहुत ज्यादा एक ही विचार है।
अब हम सिर्फ कुंजी के अंकों का उपयोग हम जड़ से नेविगेट कर सकते हैं देखने के लिए
हम Trie में जाना चाहते हैं, जहां के लिए।
>> हम तो किसी भी बिंदु पर एक मरा हुआ अंत मारा हम उस तत्व मौजूद नहीं कर सकते पता
वरना कि पथ होगा पहले से ही साफ हो गया है।
हम यह सब तरह से करने के लिए बनाते हैं अंत में, सब हम क्या करने की जरूरत है
नीचे देखो और है कि अगर देखना है हम देख रहे हैं तत्व।
यह सफलता है।
यदि ऐसा नहीं है, असफल।
>> तो चलो के लिए खोज करते हैं इस Trie में हार्वर्ड।
हम जड़ में शुरू करते हैं।
और, फिर से, हम करने जा रहे हैं एक चंक्रमण सूचक बनाने
हमारे लिए हमारे चालें करने के लिए।
जड़ से हम जानते हैं कि हम जाने की जरूरत पहले स्थान पर, 1 है
क्या हम ऐसा कर सकते हैं?
हाँ हम कर सकते हैं।
तो सुरक्षित रूप से मौजूद है।
हम वहां जा सकते हैं।
>> अब, हम जाने की जरूरत है अगले जगह 6 है।
6 पथ यहाँ से मौजूद है?
हाँ, यह करता है।
हम 6 रास्ते नीचे जा सकते हैं।
और हम यहाँ खत्म होता है।
>> हम यहां से 3 रास्ते नीचे जा सकते हैं?
खैर, यह पता चला है, के रूप में हाँ, वह भी मौजूद है।
और हम यहां से 6 पथ पर प्राप्त कर सकते हैं?
हाँ हम कर सकते हैं।
>> हम काफी जवाब नहीं दिया अभी तक सवाल है।
एक और अभी भी है है, जो अब कदम है,
हम नीचे देखने की जरूरत है और कि actually-- है देखने
हम हार्वर्ड के लिए देख रहे हैं, वह यह है कि हम कुंजी निकास के बाद हम क्या मिला?
उदाहरण में हम यहाँ का उपयोग कर रहे हैं, वर्ष हमेशा चार अंक हैं।
लेकिन अगर आप उदाहरण हैं, जहां का उपयोग किया जा सकता है आप शब्दों का एक शब्दकोश भंडारण कर रहे हैं।
>> और तो 10 के बजाय संकेत होने मेरे स्थान के लिए, आप 26 हो सकता है।
वर्णमाला के प्रत्येक अक्षर के लिए एक।
और बल्ले की तरह कुछ शब्द हैं, जो उदाहरण के लिए बैच के एक सबसेट है।
और अगर आप को मिलता है तो भले ही कुंजी के अंत और आप नीचे देखो,
आप क्या नहीं देख सकता है आप के लिए देख रहे हैं।
>> तो तुम हमेशा पार करने के लिए है पूरे पथ और उसके बाद
आप सफलतापूर्वक सक्षम थे पूरे रास्ते को पार करने के लिए,
नीचे देखो और एक अंतिम पुष्टि करते हैं।
कि मैं देख रहा हूँ क्या है?
खैर, मैं शुरू करने के बाद नीचे देखो शीर्ष पर और 1636 जा रहा है।
मैं नीचे देखो।
मैं हार्वर्ड में देखते हैं।
तो, हाँ, मैं सफल रहा।
क्या होगा अगर मैं क्या देख रहा हूँ हालांकि, Trie में नहीं है।
मैं प्रिंसटन के लिए देख रहा हूँ तो क्या होगा, जो 1746 में स्थापित किया गया था।
और तो 1746 मेरे महत्वपूर्ण हो जाता है Trie के माध्यम से नेविगेट करने के लिए।
खैर, मैं जड़ में शुरू करते हैं।
और मैं चाहता हूँ पहले स्थान पर करने के लिए एक रास्ता नीचे चला जाता है।
क्या इसे मै कर सकता हूँ?
हाँ मैं कर सकता हूँ।
>> मैं वहाँ से 7 रास्ते नीचे जा सकते हैं?
हाँ मैं कर सकता हूं।
वह भी मौजूद है।
लेकिन मुझे लगता है कि यहां से 4 रास्ते नीचे जा सकते हैं?
यही कारण है कि यह कर सकते हैं, सवाल पूछ की तरह है मैं छोटे से वर्ग कि नीचे आगे बढ़ना
कि मैं पीले रंग में प्रकाश डाला है?
यहां तो कुछ नहीं।
ठीक है।
>> कोई रास्ता आगे 4 रास्ते नीचे है।
प्रिंसटन, इस Trie में था 4 कि अगर पहले से ही हमारे लिए मंजूरी दे दी हो गया होता।
और इसलिए इस बिंदु पर हम एक मरे हुए अंत में पहुँच गए हैं।
हम किसी भी आगे नहीं जा सकते।
और इसलिए हम नहीं, निश्चित रूप से कह सकते हैं।
प्रिंसटन इस Trie में मौजूद नहीं है।
>> तो इस सब का क्या मतलब है?
ठीक है।
यहाँ पर जा रहा एक बहुत कुछ है।
सभी जगह पर संकेत नहीं है।
और, के रूप में आप देख सकते हैं बस, आरेख से
नोड्स के एक बहुत कुछ है कि एक तरह से चारों ओर उड़ रहे हैं।
लेकिन हम चाहते थे हर बार नोटिस कुछ Trie में किया गया था कि क्या जांच,
हम केवल 4 चालें बनाने के लिए किया था।
>> हम चाहते थे हर समय Trie में कुछ डालने,
हम संभवतः, 4 चालें बनाने के लिए है रास्ते में कुछ सामान mallocing।
हम जब डाला लेकिन जैसा कि हमने देखा Trie में डार्टमाउथ,
कभी कभी पथ के कुछ पहले से ही हमारे लिए मंजूरी दी जा सकती है।
और इसलिए हमारे Trie हो जाता है के रूप में बड़ा है और बड़ा है, हम कम काम हर बार ऐसा किया है
नई चीजों को डालने के लिए हम पहले से ही है क्योंकि
मध्यवर्ती का एक बहुत बनाया जिस तरह से साथ शाखाओं।
हम केवल कभी को देखने के लिए है, तो 4 चीजें, 4 सिर्फ एक स्थिर है।
हम वास्तव में एक तरह से आ रहे हैं लगातार समय प्रविष्टि
और लगातार समय देखने।
tradeoff, ज़ाहिर है, जा रहा है कि इस Trie, के रूप में आप शायद बता सकते हैं
ये बहुत बड़ा है।
इन नोड्स में से हर एक अंतरिक्ष के एक बहुत लेता है।
>> लेकिन यह है कि tradeoff है।
हम बहुत जल्दी चाहते हैं प्रविष्टि, वास्तव में जल्दी विलोपन,
और बहुत जल्दी देखने के लिए, हम करने के लिए है डेटा का एक बहुत चारों ओर उड़ान है।
हम अंतरिक्ष के एक बहुत अलग सेट करने के लिए है और उस डेटा संरचना के लिए स्मृति
अस्तित्व के लिए।
>> और इतना है कि tradeoff है।
लेकिन यह हम जैसे लग रहा है यह पाया गया हो सकता है।
हम ने पाया है कि हो सकता है डाटा संरचनाओं की होली ग्रेल
त्वरित प्रविष्टि के साथ, विलोपन, और देखने।
और हो सकता है कि यह एक होना होगा उपयुक्त डेटा संरचना
जो भी जानकारी के लिए उपयोग करने के लिए हम स्टोर करने के लिए कोशिश कर रहे हैं।
मैं डौग लॉयड हूँ, इस CS50 है।