[موسیقی بجانے] ڈوگ لایڈ: تو ہم قریب بڑھ گیا ہے اور قریب ہے کہ اعداد و شمار کے حضور Grail ہم داخل کر سکتے ہیں ڈھانچے، ایک میں، سے خارج، اور دیکھو مسلسل وقت میں. حق. اس مقصد کی طرح ہے. ہم ایسا کرنے کے قابل بننا چاہتا ہوں چیزیں بہت، بہت جلد. 

ہم یہاں جب یہ مل گیا ہے ہم کوشش کرتا ہے کے بارے میں بات کر رہے ہیں؟ ٹھیک ہے، ایک نظر ڈالیں. تو ہم نے کئی دیکھا ہے مختلف اعداد و شمار کے ڈھانچے اس کی تعریفیں ہینڈل کلیدی قدر جوڑوں نام نہاد، ڈیٹا کا کچھ ٹکڑا میپنگ اعداد و شمار کے کسی دوسرے ٹکڑے کرنے کے لئے تو ہم کہاں تلاش کرنے کے لئے جانتے ہیں ساخت میں معلومات. 

تو صف کے لئے، مثال کے طور پر، اہم عنصر انڈیکس یا صف ہے 0 مقام یا سرنی 1 اور اسی طرح. اور قیمت اعداد و شمار ہے کہ اس مقام پر موجود ہے. تو صف 0 محفوظ کیا جاتا ہے؟ کیا صرف بمقابلہ سرنی 1 میں محفوظ کیا جاتا ہے 0 اور 1، چابیاں ہو جائے گا جس. 

ایک ہیش میز کے ساتھ اس کے اسی خیال کی طرح. ایک ہیش ٹیبل کے ساتھ، ہم اس ہیش ہے ہیش کوڈز تیار کرتا ہے کہ تقریب. تو اہم اعداد و شمار کے ہیش کوڈ ہے. اور قیمت، خاص طور پر ہم کے بارے میں بات جکڑا جانا ؟. ہیش ٹیبل پر ویڈیو میں، اعداد و شمار اس سے منسلک فہرست ہے کہ hashcode کرنے hashes کو. حق. ایک اور نقطہ نظر کے بارے میں کیا یہ طریقہ، اگرچہ؟ ایک طریقہ کے بارے میں کیا جہاں اہم، منفرد ہونا کرنے کی ضمانت دی ہے ایک ہیش میز، جہاں ہم کر سکتے تھے کے برعکس اعداد و شمار کے دو ٹکڑے کے ساتھ ختم اسی hashcode ہونے. اور پھر ہم سے نمٹنے کے لئے ہے کہ یا تو کی تحقیقات یا اس سے زیادہ کی طرف سے ترجیحا اس مسئلہ کو حل کرنے جکڑا جانا. 

تو اب ہم اس بات کی ضمانت سکتا ہے کہ ہمارے اہم منفرد ہو جائے گا. اور ہماری قیمت کیا تھا تو آسان طور پر صرف کچھ چاہے ہمیں بتاتا ہے کہ کے طور پر سچ اور جھوٹ معلومات یا نہیں اس ٹکڑے ساخت میں موجود ہے؟ ایک بولین تھوڑا سا کے طور پر آسان ہو سکتا ہے. حقیقت پسندانہ یہ شاید ایک تھوڑا سا زیادہ امکان بائٹ. لیکن اس کے مقابلے میں بہت چھوٹا ہے ایک 50 حروف کی سٹرنگ شاید ذخیرہ، مثال کے طور پر. 

کی کوشش کرتا ہے تو، میزیں ہیش کی طرح، جو جمع arrays اور منسلک فہرست، کی کوشش کرتا ہے arrays کے یکجا، ڈھانچے، اور اشارہ ایک ساتھ مل کر میں ڈیٹا ذخیرہ کرنے کے لئے ہے کہ ایک دلچسپ طریقہ سے خوبصورت مختلف ہم اب تک دیکھا ہے کسی بھی چیز. اب ہم ایک روڈ میپ کے اعداد و شمار کا استعمال کرتے ہیں یہ آنکڑا ڈھانچہ گھومنے پھرنے کے لئے. اور ہم کو فالو کر سکتا ہے روڈ میپ، ہم کر سکتے ہیں سے اعداد و شمار کو فالو کریں ختم کرنے کے لئے شروع، ہم کریں گے کہ اعداد و شمار جاننا trie میں موجود ہیں. 

اور ہم نقشہ پر عمل نہیں کر سکتے تو بالکل ختم کرنے کے لئے کا مطلب ہے کی طرف سے، ڈیٹا موجود نہیں کر سکتے. ایک بار پھر، چابیاں یہاں ہیں منفرد ہونا کرنے کی ضمانت دی. تو ایک ہیش میز کے برعکس، ہم کبھی نہیں کروں گا یہاں collisions کے ساتھ نمٹنے کے لئے ہے. اور اعداد و شمار کا کوئی دو ٹکڑے بالکل اسی روڈ میپ ہے جب تک کہ اعداد و شمار ایک جیسی ہے. 

ہم جان، اس کے بعد داخل ہیں تو ہم جان کے لئے تلاش. اس کے دو ایک جیسی ٹکڑوں ہے ڈیٹا، ٹھیک ہے، ہم کے ذریعے کر رہے ہیں. لیکن دوسری صورت میں، کسی بھی اعداد و شمار کے دو ٹکڑے ہیں منفرد رہنما ہے کی ضمانت دی یہ آنکڑا ڈھانچہ کے ذریعے. اور ہم پر ایک نظر لینے کے لئے جا رہے ہیں صرف ایک لمحے میں اس کے ایک بصری. 

ہم کرنے کی کوشش کی طرف سے یہ کروں گا ایک نیا آنکڑا ڈھانچہ تشکیل دے، مندرجہ ذیل کلیدی قدر جوڑوں میپنگ. اس صورت میں، ہم استعمال کرتے ہیں کے لئے نہیں جا رہے ہیں ایک بولین کے طور پر آسان کچھ. ہم اصل میں سٹرنگ محفوظ کرے گا. اور اس سٹرنگ کی جا رہی ہے ایک یونیورسٹی کا نام. 

اور اہم سال ہونے جا رہا ہے کہ یونیورسٹی قائم کیا گیا تھا جب. یونیورسٹیوں کے تمام سال چار ہندسے ہونے جا رہے ہیں. اور اس طرح ہم ان لوگوں کو چار ہندسے استعمال کریں گے یہ آنکڑا ڈھانچہ کے ذریعے تشریف لے. اور ہم ایک بار پھر، دیکھیں گے، کس طرح ہم صرف ایک سیکنڈ میں ایسا. 

راستے کے اختتام پر، ہم نام کو دیکھ لیں گے مساوی ہے کہ یونیورسٹی کے اس کی چابی سے، ان چار ہندسوں. ایک trie کے پیچھے بنیادی خیال ہم ایک مرکزی راستہ ہے ہے. تو ایک درخت کی طرح اس کے بارے میں سوچنا. اور یہ ہجوں میں اسی طرح ہے اور ایک درخت کے تصور میں. عام طور پر ہم کے بارے میں لگتا ہے کہ جب حقیقی دنیا میں درخت، وہ میں ہے کہ ایک جڑ ہے زمین اور وہ اضافہ اضافہ اور وہ شاخیں ہیں اور وہ پتے. اور بنیادی طور پر خیال ایک trie، بالکل ایک ہی ہے کہ جڑ anchored ہے سوائے آسمان میں کہیں. اور پتیوں سے نیچے دیئے گئے ہیں. 

تو یہ ایک درخت لینے کی طرح قسم کی ہے اور صرف اسے الٹا flipping کی. لیکن پھر بھی شاخیں موجود ہیں. اور وہ ہمارے راستے ہو جائے گا، لوگ ہمارے کنکشن ہو جائے گا پتے جڑ سے. اس صورت میں، ان راستے، ان شاخوں ہمیں بتائیں کہ ہندسوں کے ساتھ لیبل لگا رہے ہیں جس طرح ہم کہاں ہیں سے جانے کے لئے. 

ہم 0 دیکھیں تو ہم اس شاخ نیچے جاؤ، ہم 1 دیکھیں تو ہم اس شاخ نیچے جاؤ، اور تو اور تو پر. ویسے، اس کا کیا مطلب ہے؟ ٹھیک ہے، اس کا مطلب ہے کہ ہر جنکشن نقطہ پر اور میں ہر نوڈ مڈل اور ہر شاخ، ممکن 10 وہاں ہو ہم جا سکتے ہیں کہ مقامات. 10 اشارہ وہاں ہو ہر جگہ سے. 

کوشش کرتا ہے حاصل کر سکتے ہیں جہاں یہ ہے کسی کے لئے دھمکی تھوڑا سا کون ہے کی ایک بہت نہیں ہے پہلے کمپیوٹر سائنس میں تجربہ. لیکن کوشش کرتا ہے واقعی بہت خوفناک ہیں. اور اگر آپ کے پاس ان کے ساتھ کام کرنے کا موقع اور آپ کو کھودنے میں کے لئے تیار ہیں اور ان کے ساتھ تجربہ، وہ واقعی بہت دلچسپ ہیں ڈیٹا ڈھانچے کے ساتھ کام کرنے. ہم ایک عنصر داخل کرنا چاہتے ہیں تو trie کے میں، ہم سب کرنے کی ضرورت ہے صحیح راستہ تعمیر کیا جاتا ہے پتی جڑ سے. یہاں کیا ہر قدم کے ساتھ ہے طرح نظر ہو سکتا ہے. ہم نے ایک نئے اعداد و شمار کی وضاحت کرنے کے لئے جا رہے ہیں ایک نیا نوڈ کے لئے ڈھانچہ ایک trie بلایا. 

اور یہ کہ اعداد و شمار کے اندر ساخت دو ٹکڑے ہیں. ہم ذخیرہ کرنے کے لئے جا رہے ہیں ایک یونیورسٹی کے نام سے. اور ہم ذخیرہ کرنے کے لئے جا رہے ہیں اشارہ کی ایک صف اسی قسم کے دوسرے نوڈس. تو، ایک بار پھر، یہ اس طرح ہے ہر جگہ کے تصور کی ہم 10 ممکن میں، ہیں ہم جا سکتے ہیں مقامات. ہم 0 دیکھیں تو ہم اس شاخ نیچے جاؤ. ہم 1 نظر آتا ہے تو، اس شاخ، اور تو اور تو اور تو پر. ہم 9 کہتے ہیں، ہم اس شاخ نیچے جاؤ. ، ہر جنکشن نقطہ پر تو ہم 10 ممکن مقامات پر جا سکتے ہیں. تو ہر نوڈ 10 اشارہ پر مشتمل ہے 10 دیگر نوڈس دوسرے نوڈس، کرنے کے لئے. 

اور ہم ذخیرہ کرنے کر رہے اعداد و شمار ہے یونیورسٹی کے صرف نام. تو ایک trie تعمیر. کی ایک جوڑے داخل ہیں ہمارے trie کے میں اشیاء کی. ، سب سے اوپر تو یہ ہماری جڑ نوڈ ہے. شاید یہ کچھ ہونے جا رہا ہے آپ کا اعلان عالمی سطح پر جا رہے ہیں. اور عالمی سطح پر آپ کو برقرار رکھنے کے لئے جا رہے ہیں ہمیشہ اس نوڈ پوائنٹر. 

آپ کہتے ہیں، کرنے کے لئے جا رہے ہیں جڑ کے برابر ہے، اور تم اپنے trie کے نوڈ malloc جا. اور آپ کبھی نہیں جا رہے ہیں پھر جڑ چھونا. آپ کرنا چاہتے ہیں ہر بار کے ذریعے گشت شروع، آپ کو ایک پوائنٹر قائم اس طرح سے Trav طور پر، جڑ کے برابر، جس کی مثال میں ہے میری ویڈیوز کے بہت سے میں استعمال یہاں پوٹ اور قطار پر اور لنک کی فہرست اور اسی طرح کی. 

آپ کو ایک پوائنٹر قائم traversal کے لئے سے Trav بلایا. اور آپ تشریف لے کرنے سے Trav استعمال آنکڑا ڈھانچہ کے ذریعے. تو یہ نظر ہو سکتا ہے کہ کس طرح دیکھتے ہیں. تو اب، کیا ایک نوڈ کی طرح لگتی ہے؟ ٹھیک ہے، صرف ہمارے اعداد و شمار کے طور پر ساخت اعلان، اس بات کا اشارہ ہم ایک تار، ہے جس اس صورت میں خالی ہے. یہاں کچھ بھی نہیں ہے. 

اور 10 اشارہ کی ایک صف. اور اب، ہم صرف اس trie میں 1 نوڈ ہے. اس میں اور کچھ نہیں ہے. لہذا ان کے تمام 10 پوائنٹ اشارہ شہوت انگیز null. وہ لال کی طرف اشارہ کرتا ہے. 

تار کی ہارورڈ داخل ہیں. کی یونیورسٹی داخل ہیں اس trie کے میں ہارورڈ، جس سال 1636 میں قائم کیا گیا تھا. ہم کلید کا استعمال کرنا چاہتے ہیں، 1636، ہم ہیں جہاں ہمیں بتانا trie میں ہارورڈ ذخیرہ کرنے کے لئے جا رہا. اب، ہم کس طرح کر سکتا ہے؟ 

یہ کچھ اس طرح نظر ہو سکتا ہے. ہم جڑ میں شروع. اور ہم جا سکتے ہیں ان 10 مقامات ہیں. جڑ صرف کسی بھی طرح ہے trie کی دیگر نوڈ. ہم یہاں سے جا سکتے ہیں 10 مقامات پر موجود ہیں. 

ہم کہاں شاید چاہتے ہیں اہم 1636 ہے تو جانے کے لئے؟ واقعی دو اختیارات نہیں ہے. حق. ہم سے اہم تعمیر کر سکتے ہیں بائیں اور دائیں 6 کے ساتھ شروع کرنے. یا ہم سے اہم تعمیر کر سکتے ہیں بائیں سے دائیں اور 1 کے ساتھ شروع. 

شاید یہ زیادہ ہے ایک انسان کے طور پر بدیہی ہم کریں گے سمجھنے کے لئے صرف بائیں سے دائیں جانا. اور اس میں شامل کرنے کے لئے چاہتے ہیں تو اس trie کے میں ہارورڈ، میں شاید شروع کرنا چاہتے ہیں جڑ میں شروع کرنے کی طرف، میری 10 کے اختیارات کو دیکھ کر میرے سامنے، اور کہہ رہے ہیں 1 راستہ نیچے جانے کے لئے چاہتے ہیں. ٹھیک ہے. 

اب، 1 راہ فی الحال خالی ہے. تو میں نے اس راستے پر آگے بڑھنے کے لئے چاہتے ہیں تو trie کے میں اس عنصر شامل کرنے کے لئے، میں 1، ایک نیا نوڈ malloc کرنا پڑے کی طرف اشارہ کریں، اور پھر میں نے جانا اچھا ہوں. 

تو میں بنیادی طور پر ایک میں ہوں نقطہ جہاں میں کھڑا ہوں درخت یا کی جڑ میں trie کے اور 10 شاخیں موجود ہیں. لیکن ہر شاخ ایک اس کے سامنے کے دروازے. حق. کچھ بھی نہیں ہے کیونکہ اور وہاں ہے. کوئی محفوظ گزرنے. کہ کچھ بھی نہیں کا مطلب ہے کہ ان شاخوں میں سے کسی کو. میں عمارت شروع کرنا چاہتے ہیں کچھ، میں دروازے کو خارج کرنا چاہتے. میں دروازے کو خارج کرنا چاہتے نمبر 1 کے سامنے. اور میں اس میں چلنے کے لئے چاہتے ہیں. اور میں تعمیر کرنا چاہتے ہیں میرے لئے دوسری جگہ جانے کے لئے. 

اور یہ کہ میں یہاں کیا ہے کیا ہے. تو 1 اب کوئی شہوت انگیز null کی طرف اشارہ ہے. میں اب یہ یہاں نیچے جانے کے لئے محفوظ ہے کہا ہے. میں ایک نوڈ کی تعمیر. اور میں اس نوڈ جب، میں بنانے کے لئے ایک فیصلہ ہے. کہاں میں یہاں سے جانے کے لئے جا رہا ہوں؟ 

ویسے، میں نے پہلے ہی 1 نیچے چلا گیا ہے. تو اب میں شاید 6 نیچے جانے کے لئے چاہتے ہیں. حق. ایک بار پھر، میں منتخب کر سکتے ہیں 10 مقامات پر ہے. تو اب تعداد 6 نیچے جانے. تو میں نے دروازے کو صاف نمبر 6 کے سامنے. اور میں وہاں نیچے چلنا. اور میں ایک نوڈ کی تعمیر. اور میں نے ایک جنکشن نقطہ تک پہنچ گئے ہیں. 

ایک بار پھر، میں نے 10 اختیارات ہیں میں جا سکتے ہیں جہاں کے لئے. میں 1 سے 6 تک منتقل کر دیا گیا. تو اب میں شاید 3 میں جانا چاہتا ہوں. 3، کہیں میں جا سکتا ہے. تو میں راستہ صاف کرنے کے لئے ہے اور اپنے آپ کو ایک نئی جگہ کی تعمیر. اور پھر میں نے جانا چاہتے ہیں جہاں 3، سے؟ میں نیچے 6 جانا چاہتا ہوں. 

اور، ایک بار پھر، مجھے کرنا پڑا ایسا کرنے کے لئے راستہ صاف. تو اب میں پیدا کرنے کے لئے میری چابی کا استعمال کیا ہے نوڈس اس trie کے تعمیر کرنے کے لئے شروع کریں اور. میں جڑ میں شروع کر دیا ہے. میں 1636 نیچے چلا گیا ہے. اور اب میں نچلے حصے میں ہوں وہاں اس نوڈ پر. اور آپ کو کرنے کے قابل ہو سکتا ہے آپ کی سکرین پر دیکھ. 

یہ پیلے رنگ میں روشنی ڈالی ہے. میں اس وقت کہاں ہوں ہے. میری چابی کیا جاتا ہے. میں اپنے اہم میں ہر پوزیشن تھک گئے ہیں. لہذا میں نے مزید کسی جانے نہیں کر سکتے ہیں. اس نقطہ پر، مجھے تو واقعی ٹھیک ہے، کا کہنا ہے کہ کرنے کی ضرورت ہے. یہ قسم کی تلاش کر رہے پسند ہے زمین میں نیچے، آپ تصور کر رہے ہیں تو اپنے راستے کے اس طرح کے طور پر مختلف کنکشن کے ساتھ. ترتیب دیں نیچے اور قسم کے لئے تلاش کر رہے زمین پر ہارورڈ پینٹنگ چھڑکیں. کہ اس کا نام ہے. اس مقام پر کیا ہے جانتے ہیں. ہم جڑ میں شروع کریں اور اگر ہم جاتے ہیں 1 اور پھر 6 اور پھر 3 اور پھر 6، ہم کہاں ہیں؟ ویسے ہم نیچے نظر آتے ہیں تو اور پھر ہم، ہارورڈ دیکھیں ہم نے ہارورڈ تھا کہ جانتے ہیں طریقہ کی بنیاد پر 1636 میں قائم کیا گیا ہم اس آنکڑا ڈھانچہ پر عمل درآمد کر رہے ہیں. تو امید ہے کہ براہ راست تھا. ہم نے دو مزید اضافے کرنے جا رہے ہیں. اور امید ہے کہ اس کی مدد کریں گے دیکھیں یہ دو بار زیادہ کیا. 

اب، ایک یونیورسٹی داخل کرنے کی اجازت. اس سے Trie میں ییل داخل ہیں. ییل 1701 میں قائم کیا گیا تھا. تو ہم شروع کریں گے جڑ، ہم ہمیشہ کرتے ہیں. اور ہم ایک traversal پوائنٹر قائم. ہم کے ذریعے منتقل کرنے کے لئے استعمال کرنے کے لئے جا رہے ہیں. ہم چاہتے ہیں سب سے پہلی چیز ایسا 1 راستے نیچے جانا ہے. یہ ہمارے کلید کے پہلی ہندسوں ہے. خوش قسمتی سے، اگرچہ، ہم ایسا نہیں کرتے کوئی کام اس وقت کیا کرنا ہے. 1 راستہ پہلے ہی منظوری دے دی گئی ہے. میں نے پہلے جب میں اس کی منظوری دے دی 1636 میں ہارورڈ داخل کیا گیا تھا. تو میں محفوظ طریقے سے منتقل کر سکتے ہیں 1 نیچے اور صرف وہاں جانا. 1 نیچے منتقل کر سکتے ہیں. 

اب، اگرچہ، میں نے 7 میں جانا چاہتا ہوں. میں نے 6 میں راستہ صاف. میں محفوظ طریقے سے کر سکتے ہیں جانتے ہیں 6 راستہ نیچے آگے بڑھنے. لیکن میں 7 راستے پر آگے بڑھنے کی ضرورت. تو مجھے کیا کرنا کی ضرورت ہے؟ ٹھیک ہے، صرف پہلے کی طرح، میں صرف کی ضرورت ہے دروازے کو صاف کرنے، راستے سے باہر حاصل، اور 7 راستے سے ایک نیا نوڈ کی تعمیر. بس اس طرح. 

تو اب میں 1 اور 7 منتقل کر دیا گیا. اور اب، نوٹس میں قسم ہوں کے اس نئے subbranch پر. حق. 16 سے سب کچھ پر، کے بارے میں پرواہ نہیں کرتے. میں 16 کچھ بھی نہیں کر رہا ہوں. میں 17 چیزیں کر رہا ہوں. 

تو اب 17 سے، میں ہے قسم کے یہاں نئے ٹریلس بلیز. اگلے عددی میری چابی ہے 0. میں واضح طور پر کہیں بھی حاصل نہیں کر سکتے. میں نے صرف اس نوڈ کی تعمیر. لہذا مجھے کوئی وہاں ہے مستقبل کے حوالے سے یہاں سے راستے. تو میں ایک خود بنانے کے لئے ہے. 

تو میں نے ایک نیا نوڈ malloc اور وہاں 0 نقطہ ہے. اور پھر ایک بار، میں malloc ایک نیا نوڈ اور وہاں ایک نقطہ ہے. ایک بار پھر، میں نے اپنے اہم، 1701 ختم ہو گئے ہیں. تو میں نیچے دیکھو اور میں ییل سپرے پینٹ. کہ اس نوڈ کا نام ہے. 

اور اس طرح اب میں نے کبھی ییل تو دیکھنے کے لئے کی ضرورت ہے تو اس trie میں، میں جڑ سے شروع ہے، میں 1701 نیچے جاؤ، اور نیچے دیکھو. اور میں ییل سپرے دیکھیں تو پھر، زمین پر پینٹ میں ییل اس trie میں موجود ہے جانتے ہیں. کی ایک زیادہ کرتے ہیں. اس میں ڈارٹماؤت داخل ہیں 1769 میں قائم کیا گیا تھا جس سے Trie،. 

پھر جڑ میں شروع. میری چابی میری پہلی ہندسوں ہے 1. میں محفوظ طریقے سے اس راستے کو منتقل کر سکتے ہیں. یہ پہلے سے موجود ہے. میری چابی کی اگلی عددی 7. میں محفوظ طریقے سے اس راستے کو منتقل کر سکتے ہیں. اس کے ساتھ ساتھ موجود. 

میری اگلی 6. یہاں سے، میں فی الحال ہوں جہاں سے کہ مشرق نوڈ میں پیلے رنگ میں، 6 فی الحال بند کر بند کر دیا ہے. میں اس راستے پر جانے کے لئے چاہتے ہیں تو، میں نے خود تعمیر کرنا پڑے. تو میں نے ایک نیا نوڈ malloc گے اور وہاں 6 نقطہ ہے. اور پھر، ایک بار پھر، میں ہوں یہاں نئے چل چلاتی ٹریلس. 

تو میں نے ایک نیا نوڈ malloc سے تاکہ اب تو اس راہ node-- تعداد 9-- اور میں 1769 سفر، اور میں نیچے نظر آتے ہیں تو. نہیں فی الحال نہیں ہے وہاں پینٹ سپرے. میں ڈارٹماؤت لکھ سکتے ہیں. اور میں داخل ہے trie کے میں ڈارٹماؤت. 

تاکہ داخل ہے trie کے میں چیزیں. اب ہم چیزوں کے لئے تلاش کرنا چاہتے ہیں. ہم کس طرح trie میں چیزوں کے لئے تلاش کرتے ہیں؟ ٹھیک ہے، یہ بہت ایک ہی خیال ہے. اب ہم صرف چابی کے ہندسے استعمال ہم جڑ سے تشریف لے کر سکتے ہیں دیکھنے کے لئے ہم trie میں کہاں جانا چاہتے ہیں کرنے کے لئے. 

تو ہم، کسی بھی موڑ پر ایک مردہ آخر مارا تو ہم اس عنصر موجود نہیں کر سکتے ہیں جانتے ہیں کہ یا کسی اور کہ راستہ گے پہلے سے منظوری دے دی ہے. ہم یہ سب طریقے سے کرتے ہیں تو آخر، ہم ایسا کرنے کی ضرورت نیچے دیکھو اور یہ کہ ہے تو دیکھنے کے ہے ہم کے لئے تلاش کر رہے ہیں عنصر. یہ کامیابی ہے. اگر یہ نہیں ہے، میں ناکام رہتے ہیں. 

تو کے لئے تلاش کرتے ہیں اس trie میں ہارورڈ. ہم جڑ میں شروع. اور، ایک بار پھر، ہم جا رہے ہیں ایک traversal پوائنٹر پیدا ہمارے اقدامات کرنا. جڑ سے ہم جانتے ہیں کہ ہم جانے کے لئے کی ضرورت ہے سب سے پہلے جگہ، 1 ہے ہم ایسا کر سکتے ہیں؟ ہاں ہم کر سکتے ہیں. تو محفوظ طریقے سے موجود. ہم وہاں جا سکتے ہیں. 

اب، ہم جانے کی ضرورت ہے اگلے جگہ ہے 6. 6 راستہ یہاں سے موجود ہے؟ جی ہاں، یہ کرتا ہے. ہم نے 6 راستے نیچے جا سکتے ہیں. اور ہم یہاں ختم. 

ہم یہاں سے 3 راستہ نیچے جا سکتے ہیں؟ ٹھیک ہے، یہ باہر کر دیتا ہے کے طور پر، جی ہاں، وہ بھی موجود ہے. اور ہم یہاں سے 6 راستے پر حاصل کر سکتے ہیں؟ ہاں ہم کر سکتے ہیں. 

ہم بہت جواب نہیں دیا ابھی تک سوال. ایک وہاں اب بھی ہے ہے جس کے قدم، ہم نیچے ملاحظہ کرنے کے ضرورت ہے اور کہ واقعی میں ہے تو دیکھنے کے ہم نے ہارورڈ کے لئے تلاش کر رہے ہیں تو، یہ ہے کہ ہم اہم ختم کے بعد ہم نے تلاش کیا؟ مثال میں ہم یہاں استعمال کر رہے ہیں، سال ہمیشہ چار ہندسے ہیں. لیکن آپ کو مثال کے طور پر جہاں استعمال کر رہے ہیں کیا جا سکتا ہے آپ الفاظ کی ایک ڈکشنری ذخیرہ کرنے ہیں. 

اور اس کی بجائے 10 اشارہ ہونے میرے محل وقوع کے لئے، آپ کو 26 ہو سکتا ہے. حروف تہجی کے ہر خط کے لئے ایک. اور بیٹ کی طرح کچھ الفاظ نہیں ہیں، جو مثال کے طور پر بیچ کی ایک اپسمچی ہے. اور آپ کو حاصل کرنے یہاں تک کہ اگر کلید کے آخر میں اور آپ نیچے دیکھو، تم کیا دیکھتے نہیں ہو سکتا آپ کے لئے تلاش کر رہے ہیں. 

لہذا آپ کو ہمیشہ سے گزرنا ہے پورے راستے اور اس کے بعد آپ نے کامیابی کے قابل تھے تو پورے راستے سے گزرنا، نیچے نظر آتے ہیں اور ایک حتمی توثیق کرتے. کہ میں دیکھ رہا ہوں کیا ہے؟ ٹھیک ہے، میں شروع کرنے کے بعد نیچے دیکھو سب سے اوپر اور 1636 جا. میں نیچے دیکھو. میں نے ہارورڈ دیکھیں. تو، جی ہاں، میں کامیاب. کیا تو کیا میں دیکھ رہا ہوں اگرچہ، trie میں نہیں ہے. میں پرنسٹن کے لئے تلاش کر رہا ہوں تو، جو 1746 میں قائم کیا گیا تھا. اور اس طرح 1746 میری اہم ہو جاتا ہے trie کے ذریعے گھومنے پھرنے کے لئے. ویسے، میں جڑ میں شروع. اور میں چاہتا ہوں سب سے پہلے جگہ 1 راستہ نیچے جاتا ہے. میں ایسا کر سکتا ہوں؟ ہاں میں کر سکتا ہوں. 

میں وہاں سے 7 راستے نیچے جا سکتے ہیں؟ جی ہاں، میں کر سکتا ہوں. وہ بھی موجود ہے. لیکن میں یہاں سے 4 راستہ نیچے جا سکتے ہیں؟ کر سکتے ہیں کہ، سوال پوچھ کی طرح ہے میں چھوٹا سا مربع نیچے کارروائی کہ میں پیلے رنگ میں روشنی ڈالی ہے؟ وہاں کچھ بھی نہیں ہے. حق. 

کوئی راستہ آگے 4 راستہ نیچے ہے. پرنسٹن، اس trie میں تھا 4 کہ اگر پہلے سے ہی ہمارے لئے منظوری دے دی ہے گا. اور اس طرح اس نقطہ پر ہم ایک مردہ آخر تک پہنچ گئے ہیں. ہم مزید کوئی نہیں جا سکتا. اور اس طرح ہم نہیں، حتمی، کہہ سکتے ہیں. پرنسٹن اس trie میں کوئی وجود نہیں ہے. 

تو یہ سب کا کیا مطلب ہے؟ حق. یہاں کیا ہو رہا ایک بہت ہے. سب جگہ اشارہ ہے. اور، کے طور پر آپ کو دیکھ سکتے ہیں صرف، آریھ سے مراکز کی ایک بہت ہے کہ وہاں قسم کے ارد گرد اڑ رہے ہیں. لیکن ہم کرنا چاہتے تھے ہر وقت محسوس کچھ trie میں تھا چاہے وہ چیک کریں، ہم صرف 4 اقدامات کرنے کے لئے تھا. 

ہم کرنا چاہتے تھے ہر وقت trie میں کچھ داخل، ہم ممکنہ طور پر، 4 اقدامات کرنے کے لئے ہے راستے میں کچھ چیزیں mallocing. ہم ڈالا لیکن جب ہم نے دیکھا کے طور پر trie کے میں ڈارٹماؤت، کبھی کبھی راستے میں سے کچھ پہلے سے ہی ہمارے لئے منظوری دے دی ہو سکتا ہے. اور اس طرح ہمارے trie کے ہو جاتا ہے کے طور پر بڑا اور بڑا، ہم کم کام ہر وقت کرتے ہیں نئی چیزیں کرنے کے لئے ہم نے پہلے ہی ہے کیونکہ انٹرمیڈیٹ کی ایک بہت بنایا راستے میں شاخیں. ہم صرف کبھی کو دیکھنے کے لئے ہیں، تو 4 چیزیں، 4 صرف ایک مسلسل جاری ہے. ہم واقعی میں اس قسم کے قریب ہیں مسلسل وقت اندراج اور مسلسل وقت نظر دوڑائیں. tradeoff کے، کورس کے، کیا جا رہا ہے اس trie کے، کے طور پر آپ کو شاید بتا سکتے ہیں، بہت بڑا ہے. ان مراکز میں سے ہر ایک جگہ کی ایک بہت لیتا ہے. 

لیکن اس tradeoff ہے. ہم واقعی چاہتے ہیں تو فوری اندراج، واقعی میں فوری منسوخی، اور واقعی فوری نظر دوڑائیں، ہم کرنا پڑے اعداد و شمار کے ایک بہت کے ارد گرد پرواز ہے. ہم نے خلا کی ایک بہت مقرر کرنے کے لئے ہے اور اس آنکڑا ڈھانچہ کے لئے میموری وجود. 

اور تو ہے کہ tradeoff ہے. لیکن یہ ہم کی طرح لگتا ہے یہ پتہ چلا ہے ہو سکتا ہے. ہم پتہ چلا ہے کہ ہو سکتا ہے ڈیٹا ڈھانچے کے مقدس grail فوری اندراج کے ساتھ، منسوخی، اور تلاش. اور شاید یہ ایک ہو جائے گا مناسب آنکڑا ڈھانچہ جو بھی معلومات کے لئے استعمال کرنا ہم اسٹور کرنے کی کوشش کر رہے ہیں. میں ڈوگ لایڈ ہوں، یہ CS50 ہے.