বাইনারি গাছের প্রকারভেদ


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় Delhivery ইনফোসিস ম্যাক
তত্ত্ব গাছ

আমরা এগিয়ে যাওয়ার আগে আমরা প্রথমে জানতে পারি বিটি আসলে কী? বাইনারি ট্রি এক প্রকারের তথ্য কাঠামো এটি প্রকৃতির শ্রেণিবিন্যাস। একটি বিটি নোড দ্বারা প্রতিনিধিত্ব করা হয় যেখানে প্রতিটি নোড বামে থাকে, একটি ডান পয়েন্টার এবং নোডের ওজন হিসাবে ডেটা। প্রতিটি নোডে সর্বাধিক 2 শিশু থাকতে পারে যা পিতামাতার নোডের বাম এবং ডান সন্তানের উল্লেখ করে।

বাইনারি গাছের প্রকারভেদ

আমাদের বাইনারি ট্রি দরকার কেন? | কেন আমরা বাইনারি গাছ ব্যবহার করি?

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

বাইনারি গাছের বৈশিষ্ট্য

  1. যে কোনও স্তরে নোডের সর্বাধিক সংখ্যা: 2 ^ এল যেখানে এল হ'ল সংখ্যার স্তর (0 <= এল <= এইচ)।
  2. উচ্চতার বিটি-তে ন্যূনতম এবং সর্বাধিক সংখ্যক নোড: ন্যূনতম- এইচ + 1 এবং সর্বোচ্চ- 2 ^ (এইচ + 1) - 1 যেখানে স্তর 0 উচ্চতা হিসাবে।
  3. প্রদত্ত বিটি-এর নোড থাকা ন্যূনতম সম্ভাব্য উচ্চতা: লগ 2 (এন + 1) -1 যেখানে স্তর 0 উচ্চতা হিসাবে।
  4. পাতার নোডের মোট সংখ্যা: 2 শিশু +1 সহ মোট নোড।
  5. এল পাতার নোডযুক্ত বিটি স্তরের সর্বনিম্ন সংখ্যার সংখ্যা: (লগ 2 এল) +1.

বাইনারি গাছের প্রকারভেদ

সম্পূর্ণ বাইনারি গাছ

একটি বাইনারি ট্রি যার মূল এবং মধ্যবর্তী নোডগুলিতে 2 টি শিশু নোড রয়েছে। অন্য কথায়, আমরা এটিও বলতে পারি যে লিফ নোড ব্যতীত প্রতিটি নোডে দুটি শিশু নোড থাকে।

বিঃদ্রঃ: একটি পূর্ণ বাইনারি গাছে পাতার নোডের সংখ্যা: অভ্যন্তরীণ নোডের সংখ্যা +1.

সম্পূর্ণ বাইনারি গাছ

সম্পূর্ণ বাইনারি ট্রি

একটি বাইনারি ট্রি যার শেষ স্তর ব্যতীত সমস্ত স্তর সম্পূর্ণরূপে পূর্ণ এবং সমস্ত নোড বাম থেকে ডানে ভরাট

বিঃদ্রঃ: বাইনারি হিপ একটি সম্পূর্ণ বাইনারি গাছের উদাহরণ।

সম্পূর্ণ বাইনারি ট্রি

পারফেক্ট বাইনারি ট্রি

একটি বাইনারি ট্রি যার অভ্যন্তরীণ নোড এবং মূল নোডে 2 টি শিশু এবং একই স্তরে সমস্ত পাতা থাকে।

বিঃদ্রঃ: নিখুঁত বাইনারি গাছের নোডের মোট সংখ্যা: 2 ^ এইচ -1 যেখানে এইচটি বিটির উচ্চতা।

পারফেক্ট বাইনারি ট্রি

ভারসাম্য বাইনারি গাছ

একটি বাইনারি ট্রি যার বাম সাবট্রি উচ্চতা h1 এবং ডান সাবট্রি উচ্চতা h2 এর পরে XNUMX | এইচ 1-এইচ 2 | <= 1.

বিঃদ্রঃ: এভিএল এবং আরবি ট্রি একটি ভারসাম্য বাইনারি গাছ বজায় রাখে।

ভারসাম্য বাইনারি গাছ

প্যাথলজিকাল বাইনারি ট্রি (স্কেউড) বিটি / ডিজেনারেট বিটি)

একটি বাইনারি ট্রি যার সমস্ত অভ্যন্তরীণ নোডগুলিতে কেবল একটি শিশু বাম শিশু হতে পারে বা এটি একটি সঠিক শিশু হতে পারে।

বিঃদ্রঃ: প্যাথোলজিকাল বিটি উচ্চতা: নোডের সংখ্যা -১.

প্যাথোলজিকাল বাইনারি ট্রি

 

উল্লেখ সাক্ষাৎকার প্রশ্ন