কেভিন Schmid: কখনও কখনও, নির্মাণের সময় একটি প্রোগ্রাম, আপনি ব্যবহার করতে পারেন একটি একটি অভিধান হিসাবে পরিচিত ডাটা স্ট্রাকচার. যা একটি অভিধান মানচিত্র নির্দেশক, সাধারণত স্ট্রিং, মান, ints, অক্ষর, কিছু বস্তুর একটি পয়েন্টার, আমরা চাই যাই হোক না কেন. এটা শুধু সাধারণ অভিধান মত সংজ্ঞা মাধ্যমে যে মানচিত্র শব্দ. 

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

কিন্তু, আমরা একটি অ্যারে ব্যবহার করতে পারে যে আমরা পরিবর্তনশীল পুনরায় আকার বা আমরা একটি ব্যবহার করতে পারেন লিঙ্ক তালিকা, হ্যাশ টেবিল অথবা একটি বাইনারি ট্রি. কিন্তু আমরা চয়ন যাই হোক না কেন, আমরা উচিত দক্ষতা সম্পর্কে সচেতন থাকুন হতে হবে এবং বাস্তবায়ন পারফরম্যান্স. আমরা ব্যবহার এলগরিদম সম্পর্কে চিন্তা করা উচিত ঢুকিয়ে মধ্যে আইটেম সন্ধান আমাদের ডাটা স্ট্রাকচার. 

এখন জন্য, এর যে আমরা অনুমান করা যাক নির্দেশক হিসাবে স্ট্রিং ব্যবহার করতে চান. এর এক সম্ভাবনা সম্পর্কে কথা বলা যাক, একটি ডাটা স্ট্রাকচার একটি trie বলা. তাই এখানে একটি দৃশ্যগত উপস্থাপনা করেন একটি trie এর. 

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

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

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

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

, বৃহত্তর চিত্রটি মধ্যে উল্লেখ্য, যখন আমরা অন্য নোডের একটি পয়েন্টার আঁকা, এটা না ব্যাপার যেখানে শর অন্যান্য নোড পূরণ করে. আমাদের নমুনা অভিধান trie রয়েছে দুটি শব্দ, যে এবং জুম. এর একটি উদাহরণ দিয়ে হেটে যাক একটি কি 'র জন্য তথ্য খুঁজছেন আপ. 

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

আমরা তারপর দ্বিতীয় সূচী তাকান করব সাধারণভাবে বি জন্য সূচক এক,, যদি আমরা কিছু বর্ণানুক্রমিক অক্ষর সি আমরা আছে সংশ্লিষ্ট স্পট নির্ধারণ পারে ব্যবহার করে শিশুদের অ্যারের মধ্যে ভালো একটি হিসাব. আমরা একটি বৃহত্তর শিশুদের ব্যবহৃত হতে পারে আমরা বর্ণন আপ এর প্রস্তাব চেয়েছিলেন অ্যারে যদি অক্ষরের একটি ব্যাপকতর পরিসীমা সঙ্গে কি, যেমন সমগ্র হিসাবে হওয়া ASCII অক্ষর সেট. 

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

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

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

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

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

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

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

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

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

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

আমরা এই ধৃষ্টতা করতে না করেন যে কি দ্বারা একটি নির্দিষ্ট দ্বারা bounded হয় ধ্রুব তারপর সন্নিবেশ এবং সন্ধান, সবচেয়ে খারাপ ক্ষেত্রে, মধ্যে রৈখিক হয় কি 'র দ্বারা. আইটেম সংখ্যা সঞ্চিত যে লক্ষ্য করুন trie মধ্যে বর্ণন আপ প্রভাবিত করে না বা সন্নিবেশ সময়. এটা শুধুমাত্র দ্বারা প্রভাবিত হচ্ছে কি 'র দ্বারা. 

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

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

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

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

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

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

আহ, এই শুরুতে পতন. আমি দুঃখিত. দুঃখিত. দুঃখিত. দুঃখিত. 

চার স্ট্রাইক. আমি বাইরে আছি. দুঃখিত. দুঃখিত. দুঃখিত. ব্যক্তি তৈরীর জন্য দুঃখিত যারা এই ছবি যান সম্পাদনা করার আছে. 

দুঃখিত. দুঃখিত. দুঃখিত. দুঃখিত. 

বক্তা 1: ভালো করেছেন. যে সত্যিই ভাল কাজ হয়.