[عزف الموسيقى] DOUG لويد: هكذا كنا يقترب وأقرب أن الكأس المقدسة البيانات الهياكل، واحدة أن نتمكن من إدراج إلى، حذف منها، والبحث عن في وقت ثابت. الصحيح. هذا النوع من المرمى. نحن نريد أن تكون قادرة على القيام الأشياء بسرعة شديدة جدا. هل لديك وجدنا أنه عندما هنا نحن نتحدث عن محاولات؟ حسنا، دعونا نلقي نظرة. لذلك رأينا العديد من هياكل بيانات مختلفة التي تتعامل مع رسم خرائط ل ما يسمى أزواج قيمة المفتاح، رسم بعض قطعة من البيانات لبعض قطعة أخرى من البيانات حتى نعرف أين تجد المعلومات الواردة في الهيكل. وذلك لمجموعة، على سبيل المثال، المفتاح هو مؤشر عنصر أو مجموعة 0 موقع أو مجموعة 1 وهلم جرا. وكانت قيمة البيانات موجود في ذلك المكان. فما يتم تخزينها في مجموعة 0؟ ما يتم تخزينها في مجموعة 1 مقابل فقط 0 و 1، والتي ستكون المفاتيح. مع جدول تجزئة انها نوع من الفكرة نفسها. مع جدول تجزئة، لدينا هذه البعثرة وظيفة أن يولد رموز التجزئة. وبالتالي فإن الحل هو رمز تجزئة البيانات. والقيمة، وخاصة تحدثنا حول تسلسل في الفيديو على الجداول التجزئة، هي أن قائمة مرتبطة البيانات أن يفرم إلى أن hashcode. الصحيح. ماذا عن نهج آخر هذا الأسلوب، على الرغم من؟ ماذا عن طريقة حيث مكفول المفتاح لتكون فريدة من نوعها، خلافا لجدول التجزئة، حيث استطعنا ينتهي مع قطعتين من البيانات لها نفس hashcode. ثم علينا أن نتعامل مع هذا إما عن طريق التحقيق أو أكثر ويفضل أن يكون تسلسل لإصلاح هذه المشكلة. وحتى الآن يمكننا ضمان هذا المفتاح لدينا وسوف تكون فريدة من نوعها. وماذا لو كانت قيمة لدينا مجرد شيء سهلا صحيح كما وكاذبة أن يقول لنا ما إذا كان أو ليس هذا قطعة من المعلومات موجود في بنية؟ A منطقية يمكن أن تكون بسيطة مثل قليلا. واقعيا هو على الأرجح البايت أكثر عرضة من بعض الشيء. ولكن هذا أصغر كثيرا من تخزين ربما سلسلة 50 حرف، على سبيل المثال. لذلك يحاول، على غرار تجزئة الجداول، التي تجمع بين المصفوفات وقائمة مرتبطة، يحاول الجمع بين المصفوفات، الهياكل، ومؤشرات معا لتخزين البيانات في طريقة مثيرة للاهتمام هذا مختلفة جدا من أي شيء رأيناه حتى الآن. ونحن الآن استخدام البيانات بمثابة خارطة الطريق للتنقل هذه البنية البيانات. واذا كنا نستطيع متابعة خارطة الطريق، اذا كنا نستطيع اتبع البيانات من البداية إلى النهاية، وسوف نقوم معرفة ما إذا كانت هذه البيانات موجودة في TRIE. وإذا كنا لا نستطيع تتبع خريطة من معنى ليغلق عند كل شيء، البيانات لا يمكن أن توجد. مرة أخرى، مفاتيح هنا يضمن أن تكون فريدة من نوعها. وذلك خلافا جدول تجزئة، وسوف نقوم أبدا لديك للتعامل مع الاصطدامات هنا. وليس قطعتين من البيانات لدينا بالضبط نفس خارطة الطريق إلا أن البيانات متطابقة. إذا كان لنا أن إدراج جون، ثم نحن نبحث عن جون. هذا هو قطعتين متطابقتين البيانات، والحق، نحن نبحث عن طريق. لكن على خلاف ذلك، أي قطعتين من البيانات مضمونة لدينا خرائط فريدة من نوعها من خلال هذه البنية البيانات. ونحن في طريقنا لنلقي نظرة على البصرية من هذا في مجرد لحظة. سنفعل ذلك من خلال محاولة ل إنشاء بنية البيانات الجديدة، رسم أزواج قيمة المفتاح التالي. في هذه الحالة، نحن لا تنوي استخدام شيء بسيط مثل منطقية. ونحن في الواقع سيتم تخزين السلسلة. وهذه السلسلة هو الذهاب الى يكون اسم الجامعة. والمفتاح سيكون العام عندما تأسست تلك الجامعة. جميع السنوات للجامعات ستكون أربعة أرقام. ولذا فإننا سوف تستخدم هذه الأرقام الأربعة ل التنقل عبر هذه البنية البيانات. وسنرى، مرة أخرى، كيف نفعل ذلك فقط في الثانية. في نهاية المسار، سنرى اسم الجامعة الذي يتوافق لهذا المفتاح، تلك الأرقام الأربعة. الفكرة الأساسية وراء TRIE هو لدينا طريقا المركزي. حتى تفكر في ذلك مثل شجرة. وهذا هو مماثل في الإملاء ومفهوم إلى شجرة. عموما عندما نفكر الأشجار في العالم الحقيقي، لديهم الجذر الذي هو في الأرض وأنها تنمو إلى الأعلى ولها فروع ولديهم الأوراق. وأساسا فكرة وTRIE هو نفسه تماما، إلا يرتكز أن الجذر في مكان ما في السماء. والأوراق في الجزء السفلي. لذلك نوع من مثل أخذ شجرة وعادل التقليب رأسا على عقب. لكن لا تزال هناك فروع. وتلك ستكون مسارات لدينا، تلك ستكون لدينا اتصالات من الجذر إلى الأوراق. في هذه الحالة، تلك مسارات، تلك الفروع وصفت مع الأرقام التي تخبرنا وسيلة للذهاب من حيث نحن. إذا كنا نرى 0، نذهب إلى أسفل هذا الفرع، إذا كان لنا أن نرى 1، ونحن ننزل هذا الفرع، وهكذا وهلم جرا. حسنا، ماذا يعني هذا؟ حسنا، هذا يعني أن في كل نقطة تقاطع وكل عقدة في وسط وكل فرع، هناك 10 ممكن الأماكن التي يمكننا أن نذهب. لذلك هناك 10 مؤشرات من كل مكان. وهذا هو المكان الذي يمكن أن يحاول الحصول على قليلا تخويف لشخص من هو لا يملك الكثير من الخبرة في علوم الكمبيوتر من قبل. ولكن محاولات حقا رهيبة جدا. وإذا كان لديك فرصة للعمل معهم وكنت على استعداد للحفر في وتجربة معهم، انهم حقا مثيرة للاهتمام للغاية هياكل البيانات للعمل مع. إذا كنا نريد لادخال عنصر في TRIE، كل ما عليك القيام به وبناء على المسار الصحيح من الجذر إلى الأوراق. وهنا ما كل خطوة على طول الطريقة قد تبدو. ونحن في طريقنا لتحديد البيانات الجديدة هيكل لعقدة جديدة تسمى TRIE. وداخل تلك البيانات هيكل هناك قطعتين. ونحن في طريقنا لتخزين اسم الجامعة. ونحن في طريقنا للتخزين مجموعة من المؤشرات إلى العقد الأخرى من نفس النوع. لذلك، مرة أخرى، وهذا هو هذا النوع من مفهوم في كل مكان نحن، ونحن في 10 ممكن الأماكن التي يمكن أن تذهب. إذا كنا نرى 0، نذهب إلى أسفل هذا الفرع. إذا كان لنا أن نرى 1، هذا الفرع، وهلم جرا وهلم جرا وهلم جرا. لو قلنا 9، نذهب إلى أسفل هذا الفرع. لذلك عند كل نقطة تقاطع، يمكننا أن نذهب 10 أماكن محتملة. لذلك كل عقدة يجب أن تحتوي على 10 مؤشرات إلى العقد الأخرى، إلى 10 العقد الأخرى. والبيانات نحن تخزين غير مجرد اسم الجامعة. لذلك دعونا بناء TRIE. دعونا إدراج زوجين من العناصر في TRIE لدينا. حتى في أعلى جدا، هذا هو العقدة الجذرية لدينا. هذا من المحتمل ان يكون شيئا وأنت تسير على الصعيد العالمي تعلن. وأنت تسير على الصعيد العالمي المحافظة مؤشر إلى هذه العقدة دائما. كنت سأقول، يساوي الجذر، وكنت الذهاب إلى malloc نفسك عقدة TRIE. وأنت تسير أبدا لمسة الجذر مرة أخرى. في كل مرة تريد بدء التنقل من خلال، قمت بتعيين مؤشر آخر يساوي الجذر، مثل بالسفر، وهو المثال الأول استخدام في العديد من أشرطة الفيديو الخاصة بي هنا على المداخن وطوابير وقوائم الارتباط وهلم جرا. قمت بتعيين مؤشر آخر دعا بالسفر لاجتياز. وكنت تستخدم بالسفر للتنقل من خلال بنية البيانات. لذلك دعونا نرى كيف أن هذا قد يبدو. حتى الآن، ما لا عقدة تبدو وكأنها؟ حسنا، تماما كما بياناتنا وأشار البيان هيكل، لدينا السلسلة، والذي في هذه الحالة فارغ. لا يوجد شيء هنا. ومجموعة من 10 مؤشرات. والآن، ونحن فقط لديك 1 عقدة في هذا TRIE. لا يوجد شيء آخر في ذلك. لذلك كل 10 من هؤلاء نقطة مؤشرات لاغية. وهذا ما يشير إلى الأحمر. دعونا إدراج سلسلة هارفارد. دعونا إدراج جامعة جامعة هارفارد في هذا TRIE، التي تأسست في العام 1636. نحن نريد استخدام المفتاح، 1636، ليقول لنا أين نحن الذهاب لتخزين هارفارد في TRIE. الآن، كيف يمكن لنا أن نفعل ذلك؟ قد تبدو شيئا من هذا القبيل. نبدأ من جذورها. ونحن لدينا هذه 10 أماكن يمكن أن نذهب. الجذر هو تماما مثل أي عقدة أخرى من TRIE. هناك 10 أماكن يمكن أن نذهب من هنا. أين نحن ربما تريد للذهاب إذا كان المفتاح هو 1636؟ هناك حقا الخيارين. الصحيح. يمكننا أن نبني المفتاح من اليمين إلى اليسار وتبدأ 6. أو يمكننا أن نبني المفتاح من من اليسار إلى اليمين وتبدأ 1. هو على الأرجح أكثر بديهية كإنسان لفهم سنقوم اذهبوا اليسار إلى اليمين. وحتى لو كنت تريد إدراج جامعة هارفارد في هذا TRIE، أنا ربما تريد أن تبدأ من خلال البدء في الجذر، أبحث في خياراتي 10 أمامي، وقوله أريد أن أذهب في الطريق 1. حسنا. الآن، 1 مسار باطل حاليا. لذلك إذا كنت تريد أن المضي قدما في هذا الطريق لإدراج هذا العنصر في TRIE، لا بد لي من malloc عقدة جديدة، لديها 1 نقطة هناك، ثم أنا على ما يرام. لذلك أنا في الأساس أنا في حيث نقطة انا واقفة في جذور شجرة أو TRIE وهناك 10 فرعا. ولكن كل فرع لديه بوابة أمامه. الصحيح. لأنه لا يوجد أي شيء آخر هناك. لا ممر آمن. وهذا يعني أن هناك شيء أسفل أي من تلك الفروع. إذا كنت تريد أن تبدأ بناء شيء، أريد أن إزالة البوابة. أريد أن إزالة البوابة أمام عدد 1. وأريد أن السير في هذا. وأريد أن أبني مكان آخر بالنسبة لي للذهاب. وهذا ما قمت به هنا. حتى 1 لم يعد يشير إلى قيمة خالية. قلت انها آمنة للذهاب إلى هنا الآن. لقد بنيت عقدة أخرى. وعندما أحصل على تلك العقدة، وأنا على قرار آخر لجعل. أين أنا ذاهب لنذهب من هنا؟ حسنا، لقد ذهبت بالفعل إلى أسفل 1. أنا حتى الآن ربما تريد أن تذهب إلى أسفل 6. الصحيح. مرة أخرى، ولدي 10 موقعا يمكنني أن تختار. لذلك دعونا نذهب الآن إلى أسفل رقم 6. لذلك أنا مسح البوابة أمام عدد 6. وأنا السير هناك. وأبني عقدة أخرى. ولقد وصلت نقطة تقاطع آخر. مرة أخرى، ولدي 10 الخيارات لتعرف أين يمكنني أن أذهب. لقد انتقلت 1-6. حتى الآن أنا ربما تريد أن تذهب إلى 3. 3، لا يوجد مكان يمكنني أن أذهب. لذلك يجب أن تمهد الطريق وبناء نفسي فضاء جديد. ثم من 3، أين أريد أن أذهب؟ أريد أن أذهب إلى أسفل 6. ومرة أخرى، كان لي ل تمهيد الطريق لتحقيق ذلك. أنا حتى الآن قد استخدمت مفتاح بلدي لادخال خلق العقد والبدء في بناء هذا TRIE. لقد بدأت في جذورها. لقد ذهبت إلى أسفل 1636. والآن أنا في القاع هناك على هذه العقدة. وكنت قد تكون قادرة على رؤيته على الشاشة. إلقاء الضوء عليها باللون الأصفر. هذا هو مكاني حاليا. ويتم مفتاح بلدي. لقد استنفدت كل موقف في مفتاح بلدي. لذلك لا أستطيع أن أذهب إلى أبعد من ذلك. حتى في هذه المرحلة، كل ما تحتاج حقا القيام به هو القول، OK. انها نوع من مثل أبحث إلى الأرض، إذا كنت تتصور نفسك هذا النوع من مسار مع اتصالات مختلفة. نوع من غمط ونوع من رذاذ الطلاء هارفارد على أرض الواقع. هذا هو اسم هذا. أعلم أن هذا ما هو على هذا الموقع. إذا بدأنا في جذور وننزل 1 ثم 6 ثم 3 ثم 6، اين انت؟ حسنا إذا كنا ننظر إلى أسفل ونحن نرى في جامعة هارفارد، ثم ونحن نعلم أن جامعة هارفارد وكان تأسست في عام 1636 على اساس طريقة نحن نقوم بتنفيذ هذه البنية البيانات. بحيث كانت واضحة نأمل. ونحن في طريقنا للقيام اثنين من أكثر الإدراج. ونأمل انها سوف تساعد على نرى هذا عمله مرتين أكثر من ذلك. الآن، دعونا إدراج جامعة أخرى. دعونا إدراج ييل في هذا TRIE. تأسست جامعة ييل عام 1701. لذلك سنبدأ في الجذر، كما نفعل دائما. وضعنا مؤشر اجتياز. ونحن في طريقنا لاستخدام ذلك للتحرك من خلال. أول شيء نريد أن القيام به هو السير في طريق 1. هذا هو الرقم الأول من المفتاح لدينا. لحسن الحظ، على الرغم من أننا لا لديهم للقيام بأي عمل هذا الوقت. وقد تم بالفعل في تمهيد الطريق 1. I مسح عليه في السابق عندما كنت تم إدراج هارفارد في 1636. حتى أتمكن من التحرك بأمان بنسبة 1 ومجرد الذهاب الى هناك. إذا يمكن أن تتحرك إلى أسفل 1. الآن، على الرغم من أنني أريد أن أذهب إلى 7. I مهدت الطريق في 6. وأنا أعلم أنني يمكن بأمان المضي قدما في الطريق 6. ولكني في حاجة إلى المضي قدما على طريق 7. فماذا يجب أن أفعل؟ حسنا، تماما مثل قبل، أنا فقط بحاجة لمسح البوابة، والخروج من الطريق، وبناء عقدة جديدة من مسار 7. تماما مثل هذا. أنا حتى الآن قد انتقلت 1 ثم 7. والآن لاحظت، وأنا الفرز من على هذا فرع ثانوي جديد. الصحيح. كل شيء آخر من 16 على، وأنا لا يهمني. أنا لا أفعل أي شيء 16. أفعله 17 الاشياء. وحتى الآن من 17 يوم، لا بد لي نوع من ارتياد آفاق جديدة هنا. الرقم التالي مفتاحي هو 0. I الواضح أنه لا يمكن الحصول على أي مكان. لقد بنيت فقط هذه العقدة. إذا كنت لا تعرف لا يوجد مسارات قدما من هنا. لذلك يجب أن يجعل واحدة نفسي. لذلك أنا malloc عقدة جديدة ولها 0 نقطة هناك. وبعد ذلك واحدة لمزيد من الوقت، وأنا malloc ل عقدة جديدة ولها نقطة واحدة هناك. مرة أخرى، لقد استنفدت مفتاحي، 1701. لذلك أنا ننظر إلى أسفل وأنا رذاذ الطلاء ييل. هذا هو اسم هذه العقدة. وحتى الآن ما إذا كنت من أي وقت مضى بحاجة إلى معرفة ما إذا كان ييل تم في هذا TRIE، وأبدأ في الجذر، I النزول 1701، وننظر إلى أسفل. وإذا أرى رذاذ ييل رسمت على الأرض، ثم وأنا أعلم ييل موجود في هذا TRIE. دعونا نفعل أكثر واحد. دعونا إدراج دارتموث في هذا TRIE، التي تأسست في عام 1769. تبدأ في الجذر مرة أخرى. أول أرقام نظري مفتاح بلدي هو 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. حسنا، وأبدأ في جذورها. والمقام الأول أريد ليذهب في الطريق 1. هل يمكن ان افعلها؟ نعم استطيع. يمكنني السير في الطريق 7 من هناك؟ نعم استطيع. موجود أيضا. ولكن يمكنني السير في طريق 4 من هنا؟ هذا مثل طرح السؤال، يمكن أنا نسير في هذا الميدان الصغير أنني قد سلط الضوء باللون الأصفر؟ لا يوجد شيء هناك. الصحيح. ليس هناك طريقة للمضي قدما في الطريق (4). إذا كان برينستون في هذا TRIE، أن 4 قد تم تطهيرها بالنسبة لنا بالفعل. وحتى في هذه النقطة لقد وصلت إلى طريق مسدود. لا نستطيع أن نذهب إلى أبعد من ذلك. وهكذا يمكن القول، بصورة نهائية، لا. برينستون غير موجود في هذا TRIE. فماذا يعني كل هذا؟ الصحيح. هناك الكثير مما يجري هنا. هناك مؤشرات في كل مكان. وكما ترون فقط من الرسم البياني، هناك الكثير من العقد التي هي نوع من تحلق حولها. ولكن لاحظ في كل مرة أردنا أن تحقق ما إذا كان شيء ما في TRIE، كان لدينا فقط لجعل 4 التحركات. في كل مرة كنا نريد ل إدراج شيء في TRIE، لدينا لجعل 4 خطوات، وربما mallocing بعض الاشياء على طول الطريق. ولكن كما رأينا عندما أدخلنا دارتموث في TRIE، أحيانا بعض الطريق قد يكون تم مسح بالنسبة لنا. وذلك كما يحصل TRIE لدينا أكبر و أكبر، كنا نفعل عمل أقل في كل مرة لإدراج الأشياء الجديدة لأننا بالفعل بنيت الكثير من وسيطة فروع على طول الطريق. إذا كان لدينا أي وقت مضى إلا أن ننظر 4 أشياء، 4 هو مجرد ثابت. نحن حقا هي نوع من الاقتراب ثابت الإدراج الوقت وبحث مستمر الوقت. المفاضلة، بطبيعة الحال، ويجري ذلك هذا TRIE، كما يمكنك أن أقول ربما، ضخمة. كل واحد من هذه العقد يستغرق الكثير من المساحة. ولكن هذا هو المقايضة. إذا كنا نريد حقا سريعة الإدراج أو الحذف سريع حقا، وبحث سريع حقا، علينا أن لديهم الكثير من البيانات تحلق حولها. علينا أن جانبا الكثير من الفضاء والذاكرة لهذا بنية البيانات في الوجود. وذلك أن المفاضلة. ولكن يبدو أننا ربما وجدت. ونحن قد وجدت أن الكأس المقدسة من هياكل البيانات مع الإدراج السريع، الحذف، والبحث. وربما سيكون هذا هيكل البيانات المناسبة استخدام لأي من المعلومات نحن نحاول أن المخزن. أنا دوغ ويد، وهذا هو cs50.