[Powered by Google Translate] একটি কম্পিউটারে কিভাবে আপনি আপনার পরিবারের সদস্যদের উপস্থাপনের? আমরা কেবল একটি তালিকা ব্যবহার করতে পারেন, কিন্তু এখানে আছে একটি অনুক্রমের স্পষ্ট. 

চলুন শুরু করা যাক বলতে আমরা আপনার মহান-নানী, এলিস সঙ্গে আরম্ভ করেছি. তিনি 2 পুত্র, বব আছে এবং আপনার পিতামহের চার্লি. চার্লি 3 শিশু রয়েছে, আপনার চাচা, ডেভ, আপনার পিসি, ইভ, এবং আপনার বাবা, ফ্রেড. আপনি ফ্রেড এর একমাত্র সন্তান. 

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

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

একটি নোডের মধ্যে গাছের পাতা এক হয় যে কোনো শিশু নেই উপর গাছ বাইরে প্রান্ত. ট্রি আগ নোড, রুট নোড, কোনো ঊর্ধ্বতন আছে. 

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

আমাদের পরিবার গাছ, তথ্য যুক্ত ছিল প্রতিটি ব্যক্তির নাম. এটা এখানে কোন int, যদিও এটা কোন কিছুই হতে পারে. হিসাবে এটি সক্রিয় আউট, একটি বাইনারি ট্রি একটি পরিবারের জন্য একটি ভাল উপস্থাপনা হবে না, থেকে ঘন ঘন জনের অধিক 2 সন্তান আছে. 

একটি বাইনারি অনুসন্ধান বৃক্ষ একটি বিশেষ, বাইনারি ট্রি ক্রমাঙ্কিত টাইপ যা আমাদের দ্রুত মান তাকান করতে পারবেন. আপনি খেয়াল করে থাকতে পারে যে একটি ট্রি রুট নীচের প্রত্যেক নোডের অন্য ট্রি রুট, যাকে বলা হয় 'subtree.' এখানে, ট্রি রুট হল 6, এবং তার সন্তান, 2, একটি subtree রুট. 

ইন একটি বাইনারি অনুসন্ধান বৃক্ষ নোডের মধ্যে সমস্ত মান ঠিক subtree নোড হল এর চেয়ে বেশী. এখানে: 6. ওয়েল, একটি নোড এর বাম subtree মান হয় নোড এর মান কম. যদি আমরা ডুপ্লিকেট মান হ্যান্ডেল প্রয়োজন, আমরা একটি শিথিল বৈষম্য পরিবর্তন হয় যারা করতে পারেন, অর্থাত অভিন্ন মান বাম বা ডান হয় পড়তে পারে, যতদিন আমরা সারা হল এটি সম্পর্কে সামঞ্জস্যপূর্ণ. এই ট্রি একটি বাইনারি অনুসন্ধান বৃক্ষ কারণ এটি এই নিয়ম অনুসরণ করে. 

এটি কিভাবে এটা যদি আমরা সি structs মধ্যে সমস্ত নোড পরিণত দেখাবে. উল্লেখ্য যে যদি একটি সন্তান হারিয়েছে, নাল পয়েন্টার হয়. কিভাবে আমরা যদি 7 গাছ হয় পরীক্ষা? আমরা root-এ শুরু. সাত 6 তুলনায়, তাই যদি এটি গাছ আছে, এটা সঠিক হতে হবে. তারপর, এটা 8 তুলনায় কম, তাই এটি বাম করা আবশ্যক. এখানে, আমরা 7 পাওয়া গিয়েছে. এখন, আমরা 5 জন্য চেক করব. পাঁচ হয় 6 কম, তাই এটি বাম হতে হবে. পাঁচ 2 হয় তার চেয়ে অনেক বেশী, তাই এটি সঠিক হতে হবে, এবং এটি 4 তার চেয়ে অনেক বেশী, তাই এটি আবার অধিকার থাকা আবশ্যক. যাইহোক, এখানে নেই কোন শিশু. নাল পয়েন্টার হয়. মানে এই যে, আমাদের 5 গাছ হয় না. 

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

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

কিভাবে দ্রুত হয় একটি বাইনারি সার্চ ট্রি অপারেশন? মনে রাখবেন যে Bigohnotation একটি ঊর্ধ্বসীমামান প্রদান কামনা. ইন লক, আমাদের গাছ কেবল একটি তালিকা সংযুক্ত করতে পারে যে সন্নিবেশ, মুছে যাওয়া, এবং যার অর্থ অনুসন্ধান সময় আনুপাতিক গাছ বিভিন্ন নোডের সংখ্যা ব্যয় হতে পারে. এটি O (n). 

উদাহরণস্বরূপ, নিম্নলিখিত একটি বৈধ বাইনারি অনুসন্ধান বৃক্ষ. তবে, যদি আমরা 9 ​​খুঁজতে চেষ্টা, আমরা প্রত্যেক নোডের, তর্ক আছে. এটি একটি লিঙ্ক তালিকা চেয়ে ভাল. মূলত, আমরা প্রত্যেক নোডের চায় আমাদের বাইনারি অনুসন্ধান বৃক্ষ 2 শিশুদের আছে. এই পথ, নিবেশ, অপসারণের সিদ্ধান্ত এবং অনুসন্ধান O (n log-) সময়, নাহয়, নিতে হবে. আগে থেকে গাছ আরো সুষম হতে পারে, ভালো লেগেছে. এখন, খুঁজছি কোনো মান আপ খুব বেশি সময় লাগে,, 3 পদক্ষেপ. এই ট্রি একটি সুষম, অর্থ যে একটি সংক্ষিপ্ত গভীরতা আছে আপেক্ষিক যাও নোড সংখ্যা. 

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

আমার নাম Bannus Van Der Kloot. এটি CS50.