[সঙ্গীত বাজাচ্ছি] ডগ লয়েড: সুতরাং আমরা কাছাকাছি inching করে থাকেন এবং কাছাকাছি যে তথ্য পবিত্র ঈপ্সিত বস্তু আমরা প্রবেশ করাতে পারে কাঠামো, এক মধ্যে, থেকে মুছে ফেলা, এবং সন্ধান ধ্রুব সময়. রাইট. যে লক্ষ্য ধরণের. আমরা কাজ করতে সক্ষম হতে চান কিছু খুব, খুব দ্রুত. 

আমরা এখানে যখন এটি পাওয়া যায় নি আমরা চেষ্টা যে বিষয়ে কথা বলছি? ওয়েল, এর কটাক্ষপাত করা যাক. তাই আমরা বিভিন্ন দেখা করেছি বিভিন্ন ডাটা স্ট্রাকচার যে ম্যাপিং হ্যান্ডেল কি-মান জোড়া তথাকথিত, তথ্য কিছু টুকরা ম্যাপিং তথ্য কিছু অন্যান্য টুকরা তাই আমরা যেখানে এটি জানেন কাঠামো তথ্য. 

সুতরাং অ্যারের জন্য, উদাহরণস্বরূপ, মূল উপাদান ইনডেক্স বা অ্যারে পাঁচ 0 বা অ্যারে 1, and so on. আর মান তথ্য যে যে অবস্থানে বিদ্যমান. সুতরাং অ্যারের 0 কি সঞ্চিত হয়? কি শুধু বনাম অ্যারে 1 সংরক্ষণ করা হয় 0 এবং 1, কী হবে, যা. 

একটি হ্যাশ টেবিল সঙ্গে এটা একই ধারণা সাজান. একটি হ্যাশ টেবিল, আমরা এই হ্যাশ আছে হ্যাশ কোড জেনারেট করে যে ফাংশন. তাই কী তথ্য হ্যাশ কোড. এবং মান, বিশেষ করে আমরা chaining সম্পর্কে সায়ীদ হ্যাশ টেবিল ভিডিও, মনে রাখবেন যে ডাটা যুক্ত তালিকা যে হ্যাশকোড করতে হ্যাশ. রাইট. আরেকটি পদ্ধতি সম্পর্কে কি এই পদ্ধতি, যদিও? একটি পদ্ধতি সম্পর্কে কি যেখানে কী, অনন্য হতে নিশ্চিত করা হয় একটি হ্যাশ টেবিল, যেখানে আমরা পারা ভিন্ন তথ্য দুই টুকরা দিয়ে শেষ একই হ্যাশকোড হচ্ছে. এবং তারপর আমরা মোকাবেলা করতে হবে যে হয় নীরিক্ষণ বা আরো দ্বারা বিশেষ যে সমস্যাটি সমাধানের জন্য chaining. 

তাই এখন আমরা গ্যারান্টি পারেন আমাদের কী অনন্য হতে হবে. আর আমাদের মান কত হলে সহজ হিসাবে শুধু কিছু আমাদেরকে বলে কিনা যে সত্য ও মিথ্যা তথ্য বা না যে টুকরা কাঠামো বিদ্যমান? একটি বুলিয়ান একটি বিট হিসাবে হিসাবে সহজ হতে পারে. বাস্তবধর্মী এটা সম্ভবত একটি একটু বেশী সম্ভাবনা বাইট. কিন্তু যে এর চেয়ে অনেক ছোট একটি 50-পংক্তির হয়তো সংরক্ষণকারী, উদাহরণ স্বরূপ. 

চেষ্টা করে, টেবিল হ্যাশ অনুরূপ, যা একত্রিত অ্যারে এবং লিঙ্ক তালিকা, চেষ্টা অ্যারে একত্রিত, কাঠামো, এবং পয়েন্টার একসাথে তথ্য সংরক্ষণ করা যে একটি আকর্ষণীয় উপায় থেকে বেশ ভিন্ন আমরা এখন পর্যন্ত দেখা করেছি কিছু. এখন আমরা একটি রোডম্যাপ হিসেবে তথ্য ব্যবহার এই ডাটা স্ট্রাকচার নেভিগেট. এবং আমরা অনুসরণ করতে পারেন তাহলে রোডম্যাপ, যদি আমরা করতে পারেন থেকে তথ্য অনুসরণ আনুপূর্বিক, আমরা করব যে তথ্য কিনা জানি Trie অস্তিত্ব. 

আর আমরা মানচিত্র অনুসরণ করতে পারে না যদি সব সময়ে শেষ করতে অর্থ থেকে, তথ্য উপস্থিত হতে পারে না. আবার, কী এখানে আছেন অনন্য হতে গ্যারান্টিযুক্ত. তাই একটি হ্যাশ টেবিল থেকে ভিন্ন, আমরা কখনও হবে এখানে দুর্ঘটনায় সঙ্গে মোকাবেলা করতে হবে. এবং তথ্য কোন দুই টুকরা ঠিক একই রোডম্যাপ আছে তবে যে তথ্য অভিন্ন. 

আমরা জন, তারপর প্রবেশ করাতে হলে আমরা জন অনুসন্ধান. যে দুটি অভিন্ন টুকরা তথ্য, ঠিক আছে, আমরা মাধ্যমে খুঁজছেন. কিন্তু অন্যথায়, কোন তথ্য দুই টুকরা অনন্য পথনকশা আছে নিশ্চিত এই ডাটা স্ট্রাকচার মাধ্যমে. আর আমরা কটাক্ষপাত চলুন মাত্র কয়েক মিনিটের মধ্যে এই একটি চাক্ষুষ. 

আমরা চেষ্টা করে এই কাজ করব একটি নতুন ডাটা স্ট্রাকচার নির্মাণ, নিম্নলিখিত কী মান জোড়া ম্যাপিং. এই ক্ষেত্রে, আমরা ব্যবহার করতে যাচ্ছেন না একটি বুলিয়ান হিসাবে সহজ হিসাবে কিছু. আমরা আসলে স্ট্রিং সংরক্ষণ করবে. এবং যে স্ট্রিং যাচ্ছে একটি বিশ্ববিদ্যালয়ের নাম হতে. 

আর কী বছর হতে যাচ্ছে যে বিশ্ববিদ্যালয় প্রতিষ্ঠিত হয়েছিল যখন. বিশ্ববিদ্যালয় জন্য সব বছর চার ডিজিটের হতে যাচ্ছি. আর তাই আমরা যারা চার ডিজিটের ব্যবহার করব এই ডাটা স্ট্রাকচার চলাচল. এবং আমরা আবার, দেখতে পাবেন, কিভাবে আমরা শুধু এই একটি দ্বিতীয় মধ্যে তা করতে. 

পথ শেষে, আমরা নাম দেখতে পাবেন অনুরূপ যে বিশ্ববিদ্যালয়ের যে কী, ঐ চার ডিজিটের. একটি trie পিছনে উপজীব্য আমরা একটি মধ্য রুট আছে. সুতরাং একটি গাছের মত এটা আমার মনে হয়. আর এই বানান একই হয় এবং একটি গাছ থেকে ধারণার. সাধারনত আমরা সম্পর্কে চিন্তা করার সময় বাস্তব জগতে গাছ, তারা যে এর একটি রুট আছে মাটিতে তারা উর্ধ্বগামী হত্তয়া এবং তারা শাখা আছে এবং তারা পাতার আছে. আর মূলত ধারণা একটি trie, ঠিক একই যে রুট প্রভুভক্ত হয় ছাড়া আকাশে কোথাও. এবং পাতার নীচে হয়. 

সুতরাং এটি একটি বৃক্ষ নেওয়ার মত কোন ধরনের এবং শুধু এটি উলটাইয়া আলোকসম্পাতের. কিন্তু এখনও শাখা আছে. আর যারা আমাদের পথ হবে, যারা আমাদের সংযোগ হতে হবে পাতার জন্য root থেকে. এই ক্ষেত্রে, যারা পাথ, যারা শাখা আমাদের বলুন যে সংখ্যার সাথে লেবেলযুক্ত কমনে আমরা কোথায় থেকে যেতে. 

আমরা একটি 0 যদি দেখেন, আমরা এই শাখা নামা, আমরা একটি 1 দেখুন, আমরা এই শাখা নামা, এবং তাই এবং তাই. ওয়েল, এই কি মানে? ওয়েল, যে মানে ভাষার জংশন সময়ে এবং প্রতিটি নোডের মধ্যম এবং প্রতিটি শাখায়, সম্ভব 10 আছে আমরা যেতে পারেন যে জায়গা. সুতরাং 10 পয়েন্টার আছে প্রতি পাঁচ থেকে. 

চেষ্টা একটি পেতে পারেন এবং এই হল যেখানে কারো জন্য ভয় দেখিয়ে অল্প কে অনেক নেই আগে কম্পিউটার বিজ্ঞান মধ্যে অভিজ্ঞতা. কিন্তু চেষ্টা সত্যিই বেশ ভালো. আর আপনি যদি তাদের সঙ্গে কাজ করার সুযোগ এবং আপনি খনন ইন করতে ইচ্ছুক হন এবং তাদের সঙ্গে পরীক্ষা, তারা সত্যিই বেশ আকর্ষণীয় আছেন ডাটা স্ট্রাকচার সঙ্গে কাজ করতে. আমরা একটি উপাদান প্রবেশ করাতে চান Trie মধ্যে, সব আমরা যা করতে হবে সঠিক পথ নির্মাণ করা হয় পাতার জন্য root থেকে. এখানে কি ধাপে ধাপে বরাবর এর উপায় অনুরূপ হতে পারে. আমরা একটি নতুন তথ্য সংজ্ঞায়িত করতে যাচ্ছেন একটি নতুন নোডের জন্য কাঠামো একটি trie বলা. 

এবং যে তথ্য ভিতরে কাঠামো দুই টুকরা আছে. আমরা ধারণ করতে যাচ্ছেন একটি বিশ্ববিদ্যালয়ের নাম. এবং আমরা দোকান চলুন পয়েন্টার একটি অ্যারে একই ধরনের অন্যান্য নোড. সুতরাং, আবার, এই যে কেমন হয় সর্বত্র ধারণার আমরা 10 সম্ভব এ, হয় আমরা যেতে পারেন জায়গা. আমরা একটি 0 যদি দেখেন, আমরা এই শাখা নামা. আমরা একটি 1 দেখুন, এই শাখা, এবং তাই এবং তাই এবং তাই. আমরা 9 ​​যদি বলি, আমরা এই শাখা নামা. প্রতি জংশন পয়েন্টে আমরা 10 সম্ভাব্য জায়গা যেতে পারেন. সুতরাং প্রতিটি নোডের 10 পয়েন্টার থাকতে হবে 10 অন্যান্য নোড অন্যান্য নোড, এর সাথে. 

আর আমরা সংরক্ষণ করছেন তথ্য বিশ্ববিদ্যালয়ের শুধু নাম. সুতরাং আসুন একটি trie গড়ে তুলি. এর কয়েক সন্নিবেশ করা যাক আমাদের trie মধ্যে আইটেম. খুব উপরের তাই এই আমাদের রুট নোড হয়. এটি সম্ভবত কিছু হতে যাচ্ছে তোমরা প্রকাশ বিশ্বব্যাপী করতে যাচ্ছেন. আর আপনি বজায় বিশ্বব্যাপী করতে যাচ্ছেন সবসময় এই নোডের একটি পয়েন্টার. 

আপনি, বলে যাচ্ছেন রুট সমান, এবং আপনি আছেন নিজেকে Trie নোডের malloc যাচ্ছে. এবং আপনি কখনও যাচ্ছেন আবার রুট স্পর্শ করতে. আপনি করতে চান প্রতিটি সময় মাধ্যমে নেভিগেট শুরু, আপনি অন্য পয়েন্টার সেট যেমন trav হিসাবে, রুট সমান, যা যেমন আমি আমার অনেক ভিডিও ব্যবহার এখানে stacks এবং সারির উপর এবং লিঙ্ক তালিকায়, and so on. 

আপনি অন্য পয়েন্টার সেট ট্র্যাভেরসাল জন্য trav বলা. এবং আপনি নেভিগেট করতে trav ব্যবহার ডাটা স্ট্রাকচার মাধ্যমে. তাই আসুন এই চেহারা হতে পারে কিভাবে দেখতে দিন. তাই এই মুহূর্তে, কি একটি নোড কেমন হয়েছে? ওয়েল, শুধু আমাদের তথ্য হিসাবে কাঠামো ঘোষণা, নির্দেশিত আমরা একটি স্ট্রিং, আছে যা এই ক্ষেত্রে খালি. এখানে কিছুই নেই. 

আর 10 পয়েন্টার একটি অ্যারে. এবং এই মুহূর্তে, আমরা শুধুমাত্র এই trie বিভিন্ন 1 নোড আছে. এটা অন্য কিছুই নেই. তাই ঐ সব 10 বিন্দু পয়েন্টার নাল. যে লাল ইঙ্গিত কি. 

এর স্ট্রিং হার্ভার্ড ঢোকান. এর বিশ্ববিদ্যালয় সন্নিবেশ করা যাক এই Trie মধ্যে হার্ভার্ড, যা বছর 1636 সালে প্রতিষ্ঠিত হয়. আমরা কী ব্যবহার করতে চান, 1636, আমরা যেখানে আমাদের জানাতে trie বিভিন্ন হার্ভার্ড সংরক্ষণ করে যাচ্ছে. এখন, আমরা যে কি হতে পারে? 

এটা ভালো কিছু চেহারা হতে পারে. আমরা root- এ শুরু. আর আমরা যেতে পারেন এই 10 টি স্থান আছে. রুট ঠিক কোন ভালো হয় Trie অন্য নোড. আমরা এখানে থেকে যেতে পারেন 10 জায়গা আছে. 

কোথায় আমরা সম্ভবত চান না কী 1636 হয় তাহলে যেতে? সত্যিই দুটি অপশন আছে. রাইট. আমরা থেকে কী নির্মাণ করতে পারেন বাম এবং ডান 6 দিয়ে শুরু করতে. অথবা আমরা থেকে কী নির্মান করতে পারে ডানে বামে এবং 1 দিয়ে শুরু. 

এটা সম্ভবত আরো একটি মানুষের হিসাবে স্বজ্ঞাত আমরা করব বুঝতে শুধু ডানে বামে যেতে. আর তাই আমি সন্নিবেশ করতে চান তাহলে এই Trie মধ্যে হার্ভার্ড, আমি সম্ভবত শুরু করতে চান root- এ শুরু করে, আমার 10 অপশন এ খুঁজছেন আমার সামনে, এবং বলার অপেক্ষা রাখে না আমি 1 পাথ নিচে যেতে চাই. ঠিক আছে. 

এখন, 1 পাথ বর্তমানে নাল. তাই আমি যে পথ নিচে এগিয়ে যেতে চান তাহলে Trie মধ্যে এই উপাদান প্রবেশ করাতে, আমি 1 আছে, একটি নতুন নোডের malloc আছে সেখানে নির্দেশ, এবং তারপর আমি যেতে ভাল আছি. 

তাই আমি আসলে একজন am- এ বিন্দু যেখানে আমি দাঁড়িয়ে আছি গাছ বা মূলে Trie এবং 10 টি শাখা আছে. কিন্তু প্রতিটি শাখা আছে একটি এটি সামনে গেট. রাইট. কিছুই নেই, কারণ অন্য আছে. কোন নিরাপদ উত্তরণ. যে কিছুই নেই যে মানে ঐ শাখার কোনো নিচে. আমি বিল্ডিং শুরু করতে চান তাহলে কিছু আছে, আমি গেট সরাতে চান. আমি গেট সরাতে চান সংখ্যা 1 এর সামনে. আর আমি যে হেঁটে নিচে চান. আর আমি গড়ে তুলতে চাই আমার জন্য অন্য জায়গায় যেতে. 

এবং আমি এখানে সম্পন্ন করেছি কি. সুতরাং 1 আর নাল স্থানটিকে. আমি কি এখন এটি এখানে নামা নিরাপদ বলেন করেছি. আমি অন্য একটি নোড নির্মিত. আর আমি যে নোডের পেতে হলে, আমি করা অন্য সিদ্ধান্ত আছে. কোথায় আমি এখানে থেকে যেতে যাচ্ছি? 

ওয়েল, আমি ইতিমধ্যে 1 অস্তমিত থাকেন. তাই এখন আমি সম্ভবত 6 নিচে যেতে চাই. রাইট. আবার, আমি বেছে নিতে পারেন 10 অবস্থানে আছে. তাই আসুন এখন সংখ্যা 6 নেমে যাক. তাই আমি গেট পরিষ্কার সংখ্যা 6 সামনে. এবং আমি নিচে সেখানে হেঁটে. আর আমি অন্য একটি নোড নির্মাণ. আর আমি অন্য জংশন পয়েন্ট পৌঁছে গেছেন. 

আবার, আমি 10 গ্রেপ্তার আছে আমি যেখানে যেতে পারেন জন্য. আমি 1 থেকে 6 স্থানান্তরিত করেছি. তাই এখন আমি সম্ভবত 3 যেতে চান. 3, কোথাও আমি যেতে পারেন আছে. তাই আমি পথ পরিষ্কার আছে এবং নিজেকে একটি নতুন স্থান নির্মাণ. এবং তারপর আমি যেতে চাই না যেখানে 3 থেকে? আমি নিচে 6 যেতে চান. 

আর, আবার আমি ফিরে আসা এটা করতে পথ পরিষ্কার. তাই এখন আমি তৈরি সন্নিবেশ করতে আমার কী ব্যবহার করেছি নোড এই Trie নির্মাণ শুরু এবং. আমি root- এ শুরু করেছি. আমি 1636 অস্তমিত থাকেন. আর এখন আমি নীচে আছি সেখানে যে নোড. এবং আপনি করতে সক্ষম হতে পারে আপনার পর্দায় এটি দেখতে. 

এটি হলুদ হাইলাইট করা হয়. আমি বর্তমানে am যে যেখানে. আমার কী করা হয়. আমি আমার কী প্রত্যেক অবস্থান ফেলেছেন. তাই আমি বেশি দূর যাওয়া যাবে না. এই সময়ে, সব আমি তাই সত্যিই ঠিক আছে, বলে হয় না প্রয়োজন. এটা কোন ধরনের খুঁজছেন মত মাঠে নেমে, আপনি envisioning করছি নিজেকে পাথ এই সাজানোর হিসাবে বিভিন্ন সংযোগ. সাজান নিচে এবং সাজানোর খুঁজছেন মাটিতে হার্ভার্ড পেইন্টিং স্প্রে. যে এই নাম. যে এই অবস্থানে কি জানি. আমরা root- এ শুরু এবং আমরা নিচে যান 1 এবং তারপর 6 এবং তারপর 3 এবং তারপর 6, আমরা কোথায়? আচ্ছা আমরা নিচে দেখুন তাহলে এবং আমরা তখন হার্ভার্ড দেখতে আমরা হার্ভার্ড হওয়ার একটা ধান্দা খুজছি পথে ভিত্তিক 1636 সালে প্রতিষ্ঠিত আমরা এই তথ্য কাঠামো বাস্তবায়ন করছি. যাতে আশা করছি সহজবোধ্য ছিল. আমরা আরো দুটি সন্নিবেশ করতে যাচ্ছেন. এবং আশা করি এটি সাহায্য করব দেখতে এই দুইবার আরো কাজ. 

এখন, এর অন্য বিশ্ববিদ্যালয়ের ঢুকিয়ে দেওয়া. এর এই Trie মধ্যে ইয়েল ঢোকান. ইয়েল 1701 সালে প্রতিষ্ঠিত হয়. তাই আমরা এ শুরু করব root পরিচয়ে, আমরা সবসময় হিসাবে. আর আমরা একটি ট্র্যাভেরসাল পয়েন্টার সেট. আমরা মাধ্যমে সরাতে যে ব্যবহার করতে যাচ্ছেন. আমরা চাই প্রথম জিনিস না 1 পাথ নামা হয়. যে আমাদের কী প্রথম ডাক আছে. সৌভাগ্যবসত, যদিও, আমরা না কোন কাজ এই সময় কি আছে. 1 ইতিমধ্যে পথ সাফ করা হয়েছে. আমি পূর্বে যখন আমি এটা সাফ 1636 এ হার্ভার্ড ঢোকাতে হয়. তাই আমি নিরাপদে স্থানান্তর করতে পারেন 1 নিচে এবং ঠিক আছে যান. 1 নিচে স্থানান্তর করতে পারেন. 

এখন, যদিও, আমি 7 যেতে চান. আমি 6 এ পথ সাফ. আমি নিরাপদে পারেন জানেন 6 পথ নিচে এগিয়ে যান. কিন্তু আমি 7 পাথ উপর এগিয়ে যাওয়া প্রয়োজন. তাই আমি কি করতে হবে? ওয়েল, ঠিক আগের মতই, আমি শুধু প্রয়োজন গেট পরিষ্কার, পথে নামা, এবং 7 পথ থেকে একটি নতুন নোড নির্মাণ. ঠিক এই রকম. 

তাই এখন আমি 1 এবং তারপর 7 সরিয়েছেন. এবং এখন, বিজ্ঞপ্তি আমি সাজান আছি এই নতুন উপশাখা উপর. রাইট. 16 থেকে অন্য সব কিছুর দেখো, আমি যত্নশীল না. আমি 16 কিছু করছি না. আমি 17 স্টাফ করছি. 

তাই এখন 17 থেকে, আমি আছে সাজান এখানে নতুন গ্রামাঞ্চলে ভ্রমণ শনাক্ত. পরবর্তী ডাক আমার কী হল 0. আমি পরিষ্কারভাবে কোথাও পাওয়া যাবে না. আমি শুধু এই নোড নির্মিত. তাই আমি কোন আছে জানি এগিয়ে এখান থেকে পাথ. তাই আমি এক নিজেকে করতে হবে. 

তাই আমি একটি নতুন নোডের malloc এবং সেখানে 0 পয়েন্ট আছে. এবং তারপর আরো একটি সময়, আমি malloc একটি নতুন নোডের এবং সেখানে এক বিন্দু আছে. আবার, আমি আমার কী, 1701 ফেলেছেন. তাই আমি নিচে দেখুন এবং আমি ইয়েল রং স্প্রে. যে এই নোডের নাম. 

তাই এখন আমি কি ইয়েল কিনা দেখতে প্রয়োজন হলে এই trie, আমি root- এ শুরু হয়, আমি 1701 নামা, এবং নিচে দেখুন. আর আমি ইয়েল স্প্রে দেখতে হলে তারপর, স্থল সম্মুখের আঁকা আমি ইয়েল এই trie বিভিন্ন বিদ্যমান জানি. এর আরও একটি কাজ করা যাক. এর এই মধ্যে ডারমাউথ সন্নিবেশ করা যাক 1769 সালে প্রতিষ্ঠিত হয়েছিল যা Trie,. 

আবার root- এ শুরু. আমার কী আমার প্রথম ডাক 1 হয়. আমি নিরাপদে যে পথ নিচে স্থানান্তর করতে পারেন. যে আগে থেকেই আছে. আমার কী পরবর্তী ডাক 7. আমি নিরাপদে যে পথ নিচে স্থানান্তর করতে পারেন. এটা পাশাপাশি বিদ্যমান. 

আমার পরবর্তী 6. এখান থেকে আমি বর্তমানে আছি যেখানে থেকে যে মাঝখানে নোড সেখানে হলুদ, 6 বর্তমানে বন্ধ লক করা আছে. আমি যে পথ নিচে যেতে চান আমি নিজেকে গড়ে তুলতে হবে. তাই আমি একটি নতুন নোডের malloc করব সেখানে 6 পয়েন্ট আছে. আর তারপর আবার, আমি আছি এখানে নতুন গন্গনে গ্রামাঞ্চলে ভ্রমণ. 

তাই আমি একটি নতুন নোডের malloc থেকে যাতে এখন তাহলে যে নোড পাথ সংখ্যা 9-- ও আমি 1769 ভ্রমণ, এবং আমি নিচে একটু খেয়াল করেন. কিছুই বর্তমানে নেই সেখানে আঁকা স্প্রে. আমি ডারমাউথ লিখতে পারেন. আর আমি ঢোকানো থাকেন Trie মধ্যে Dartmouth. 

সুতরাং যে ঢোকাতে Trie মধ্যে জিনিষ. এখন আমরা কিছু জন্য অনুসন্ধান করতে চান. কিভাবে আমরা trie বিভিন্ন জিনিষ অনুসন্ধান করেন? ওয়েল, এটা অনেক সুন্দর একই ধারণা. এখন আমরা শুধু কী সংখ্যা ব্যবহার আমরা রুট থেকে নেভিগেট করতে পারেন কিনা দেখতে আমরা trie বিভিন্ন যেতে চান যেখানে. 

আমরা তখন, যে কোনো স্থানে একটি কানাগলি আঘাত আমরা যে উপাদান বিদ্যমান করতে পারবে না বা অন্য যে পথ would ইতিমধ্যেই সাফ হয়েছে. আমরা এটা সব পথ করতে হলে শেষ, সব আমরা যা করতে হবে ঘৃণা এবং যে কিনা দেখতে হয় আমরা খুঁজছেন উপাদান. এটা, বিজয় হয়. এটি যদি না থাকে, ব্যর্থ. 

তাই এর জন্য অনুসন্ধান করা যাক এই trie বিভিন্ন হার্ভার্ড. আমরা root- এ শুরু. আর, আবার আমরা চলুন একটি ট্র্যাভেরসাল পয়েন্টার তৈরি আমাদের জন্য আমাদের প্যাচসমূহ করতে. রুট থেকে আমরা জানি যে আমরা যেতে হবে প্রথমেই, 1 আমরা তা করতে পারে? হ্যাঁ আমরা পারি. যদি নিরাপদে বিদ্যমান. আমরা সেখানে যেতে পারেন. 

এখন, আমরা যেতে হবে পরের জায়গায় 6. 6 পাথ এখানে থেকে কি অস্তিত্ব আছে? হ্যা, এটা আছে. আমরা 6 পথ নিচে যেতে পারেন. আর আমরা এখানে শেষ. 

আমরা এখান থেকে 3 পাথ নিচে যেতে পারে? ওয়েল, হিসাবে এটি সক্রিয় আউট, হ্যাঁ, যে খুব বিদ্যমান. আর আমরা এখানে থেকে 6 পথে পেতে পারেন? হ্যাঁ আমরা পারি. 

আমরা বেশ সাড়া দেয়নি এখনো প্রশ্ন. আরও এখনও নেই এখন যা ধাপে, আমরা নিচে তাকান প্রয়োজন এবং যে আসলে কিনা দেখতে আমরা হার্ভার্ড জন্য বেরাচ্ছেন, যে হয় আমরা কী ক্ষয় পরে আমরা তা খুঁজে? উদাহরণস্বরূপ আমরা এখানে ব্যবহার করছি, বছর সবসময় চার ডিজিটের হয়. কিন্তু আপনি যেমন যেখানে ব্যবহার করা যেতে পারে আপনি শব্দের একটি অভিধান সংরক্ষণকারী. 

আর তাই এর পরিবর্তে 10 পয়েন্টার হচ্ছে আমার অবস্থান, আপনি 26 থাকতে পারে. বর্ণমালার প্রতিটি অক্ষরের জন্য একটি করে. ব্যাটিংয়ের মত কিছু শব্দ আছে, যা উদাহরণস্বরূপ ব্যাচ একটি উপসেট হয়. এবং আপনি পেতে তাই, এমনকি যদি কি শেষে এবং আপনি নিচে দেখুন, আপনি কি দেখতে পারে না আপনি খুজছেন. 

তাই আপনি সর্বদা তর্ক আছে সম্পূর্ণ পাথ ও তারপর আপনি সফলভাবে সক্ষম হয় তাহলে সম্পূর্ণ পাথ, তর্ক করতে, ঘৃণা এবং এক চূড়ান্ত অনুমোদনের না. যে আমি চাই কি? ওয়েল, আমি শুরু করার পর নিচে দেখুন উপরের এবং 1636 যাচ্ছে. আমি নিচে দেখুন. আমি হার্ভার্ড দেখতে. তাই, হ্যাঁ, আমি সফল. কেমন হয়, যদি তা আমি চাই যদিও, trie বিভিন্ন নয়. আমি প্রিন্সটন চাই কি তাহলে, যা 1746 সালে প্রতিষ্ঠিত হয়. আর তাই 1746 আমার কী হয়ে trie মাধ্যমে নেভিগেট. ওয়েল, আমি root- এ শুরু. এবং আমি চাই প্রথম স্থান 1 পাথ নিচে চলে যায়. আমি কি এটা করতে পারি? হ্যা আমি পারবো. 

আমি সেখান থেকে 7 পাথ নিচে যেতে পারে? হ্যাঁ আমি পারবো. যে খুব বিদ্যমান. কিন্তু আমি এখানে থেকে 4 পাথ নিচে যেতে পারে? যে, প্রশ্ন জিজ্ঞাসা মত আমি সামান্য বর্গ যে ডাউন এগিয়ে যে আমি হলুদ হাইলাইট করেছি? সেখানে কিছুই নেই. রাইট. 

কোন ভাবে এগিয়ে 4 পাথ নিচে আছে. প্রিন্সটন, এই trie বিভিন্ন ছিল 4 যে যদি ইতিমধ্যে আমাদের জন্য সাফ হয়ে যেত. আর তাই এই সময়ে তদ্দ্বারা মৃত শেষে পৌঁছে গেছেন. আমরা বেশি দূর যাওয়া যাবে না. আর তাই আমরা কোন, নিশ্চিতভাবেই, বলতে পারেন. প্রিন্সটন এই trie বিভিন্ন অস্তিত্ব নেই. 

তাহলে এই সবের কী মানে? রাইট. এখানে যাওয়া অনেক আছে. সব জায়গায় বেশি পয়েন্টার আছে. আর, হিসাবে আপনি দেখতে পারেন শুধু, ডায়াগ্রাম থেকে নোড অনেক আছে যে ধরনের চারপাশে উড়ন্ত. কিন্তু আমরা চেয়েছিলেন প্রতি সময় লক্ষ্য কিছু Trie ছিল কিনা তা যাচাই, আমরা মাত্র 4 প্যাচসমূহ করতে ছিল. 

আমরা চেয়েছিলেন প্রতি সময় trie বিভিন্ন কিছু সন্নিবেশ, আমরা সম্ভবত, 4 প্যাচসমূহ করতে হবে পথ ধরে কিছু কাপড় mallocing. আমরা ঢোকানো কিন্তু যখন আমরা দেখেছি Trie মধ্যে Dartmouth, কখনও কখনও পাথ কিছু ইতিমধ্যে আমাদের জন্য সাফ করা যেতে পারে. আর তাই আমাদের trie পায় হিসাবে বড় এবং বড়, আমরা কম কাজ প্রত্যেক সময় কি আছে নতুন জিনিস সন্নিবেশ করতে আমরা ইতিমধ্যে করেছি কারণ অন্তর্বর্তী অনেক বিল্ট পথ ধরে শাখা. আমরা শুধুমাত্র কখনও তাকান থাকে 4 টি জিনিস, 4 শুধু একটি ধ্রুবক. আমরা সত্যিই ধরনের সমীপবর্তী হয় ধ্রুব সময় সন্নিবেশ এবং ধ্রুব সময় লুকআপ. নির্ধারণ, অবশ্যই, যে হচ্ছে এই Trie, হিসাবে আপনি সম্ভবত, বলতে পারেন বিপুল. এই নোডের মধ্যে প্রতিটি এক স্থান অনেক আপ নেয়. 

কিন্তু যে tradeoff. আমরা সত্যিই দ্রুত চান সন্নিবেশ, সত্যিই দ্রুত অপসারণের, এবং সত্যিই দ্রুত লুকআপ, আমরা আছে তথ্য অনেক কাছাকাছি উড়ন্ত আছে. আমরা স্থান অনেক সরাইয়া সেট করা আছে এবং যে তথ্য কাঠামো জন্য মেমরি অস্তিত্ব. 

আর তাই যে tradeoff. কিন্তু এটা আমরা দেখে মনে হচ্ছে এটা পাওয়া যায় পারে. আমরা যে পাওয়া যায় পারে ডাটা স্ট্রাকচার পবিত্র ঈপ্সিত বস্তু দ্রুত সন্নিবেশ সঙ্গে, অপসারণ, এবং লুকআপ. এবং হয়ত এই একটি হতে হবে উপযুক্ত তথ্য কাঠামো যাই হোক না কেন তথ্যের জন্য ব্যবহার করতে আমরা দোকান থেকে চেষ্টা করছি. আমি ডগ লয়েড আছি, এই CS50 হয়.