সম্পূর্ণ বাইনারি ট্রি বনাম সম্পূর্ণ বাইনারি ট্রি
বাইনারী গাছ হল এমন একটি গাছ যেখানে প্রতিটি নোডের একটি বা দুটি বাচ্চা থাকে। একটি বাইনারি গাছে, একটি নোডে দুটির বেশি সন্তান থাকতে পারে না। একটি বাইনারি গাছে, শিশুদের "বাম" এবং "ডান" শিশু হিসাবে নামকরণ করা হয়। চাইল্ড নোডগুলিতে তাদের পিতামাতার একটি রেফারেন্স রয়েছে। একটি সম্পূর্ণ বাইনারি ট্রি হল একটি বাইনারি ট্রি যাতে বাইনারি গাছের প্রতিটি স্তর শেষ স্তরটি ছাড়া সম্পূর্ণরূপে পূর্ণ হয়। অপূর্ণ স্তরে, নোডগুলি বাম-সর্বাধিক অবস্থান থেকে শুরু করে সংযুক্ত করা হয়। একটি সম্পূর্ণ বাইনারি গাছ হল এমন একটি গাছ যেখানে গাছের প্রতিটি নোডে গাছের পাতা ছাড়া দুটি বাচ্চা থাকে।
পূর্ণ বাইনারি ট্রি কি?
পূর্ণ বাইনারি ট্রি হল একটি বাইনারি গাছ যেখানে গাছের প্রতিটি নোডে ঠিক শূন্য বা দুটি বাচ্চা থাকে। অন্য কথায়, পাতা ছাড়া গাছের প্রতিটি নোডে ঠিক দুটি সন্তান রয়েছে। নীচের চিত্র 1 একটি সম্পূর্ণ বাইনারি গাছ চিত্রিত করে। একটি সম্পূর্ণ বাইনারি ট্রিতে, নোডের সংখ্যা (n), লেভের সংখ্যা (l) এবং অভ্যন্তরীণ নোডের সংখ্যা (i) একটি বিশেষ উপায়ে সম্পর্কিত যাতে আপনি যদি তাদের মধ্যে যেকোন একটি জানেন তবে আপনি অন্য দুটি নির্ধারণ করতে পারেন। নিম্নরূপ মান:
1. যদি একটি পূর্ণ বাইনারি গাছে i অভ্যন্তরীণ নোড থাকে:
– পাতার সংখ্যা l=i+1
– মোট নোডের সংখ্যা n=2i+1
2. যদি একটি পূর্ণ বাইনারি গাছের এন নোড থাকে:
– অভ্যন্তরীণ নোডের সংখ্যা i=(n-1)/2
– পাতার সংখ্যা l=(n+1)/2
৩. যদি একটি পূর্ণ বাইনারি গাছের পাতা থাকে:
– মোট নোডের সংখ্যা n=2l-1
– অভ্যন্তরীণ নোডের সংখ্যা i=l-1
সম্পূর্ণ বাইনারি ট্রি কি?
চিত্র 2-এ দেখানো হিসাবে, একটি সম্পূর্ণ বাইনারি গাছ হল একটি বাইনারি গাছ যেখানে শেষ স্তরটি ছাড়া গাছের প্রতিটি স্তর সম্পূর্ণরূপে পূর্ণ হয়। এছাড়াও, শেষ স্তরে, নোডগুলি সবচেয়ে বাম অবস্থান থেকে শুরু করে সংযুক্ত করা উচিত। h উচ্চতার একটি সম্পূর্ণ বাইনারি গাছ নিম্নলিখিত শর্তগুলি পূরণ করে:
– রুট নোড থেকে, শেষ স্তরের উপরের স্তরটি h-1 উচ্চতার একটি সম্পূর্ণ বাইনারি ট্রি প্রতিনিধিত্ব করে
– শেষ স্তরের এক বা একাধিক নোডে 0 বা 1 সন্তান থাকতে পারে
– যদি a, b শেষ স্তরের উপরে স্তরে দুটি নোড হয়, তাহলে a-এর চেয়ে b এর চেয়ে বেশি সন্তান থাকে এবং শুধুমাত্র a যদি b এর বামে অবস্থিত হয়
সম্পূর্ণ বাইনারি ট্রি এবং সম্পূর্ণ বাইনারি ট্রির মধ্যে পার্থক্য কী?
সম্পূর্ণ বাইনারি গাছ এবং সম্পূর্ণ বাইনারি গাছের মধ্যে স্পষ্ট পার্থক্য রয়েছে। একটি পূর্ণ বাইনারি গাছ একটি বাইনারি গাছ যেখানে প্রতিটি নোডে শূন্য বা দুটি সন্তান থাকে, একটি সম্পূর্ণ বাইনারি গাছ হল একটি বাইনারি গাছ যেখানে শেষ স্তরটি ছাড়া বাইনারি গাছের প্রতিটি স্তর সম্পূর্ণরূপে পূর্ণ হয়। কিছু বিশেষ ডেটা স্ট্রাকচার যেমন হিপসকে সম্পূর্ণ বাইনারি ট্রি হতে হবে যখন সেগুলিকে সম্পূর্ণ বাইনারি ট্রি হতে হবে না। একটি সম্পূর্ণ বাইনারি গাছে, আপনি যদি মোট নোডের সংখ্যা বা লেভের সংখ্যা বা অভ্যন্তরীণ নোডের সংখ্যা জানেন তবে আপনি অন্য দুটি খুব সহজেই খুঁজে পেতে পারেন। কিন্তু একটি সম্পূর্ণ বাইনারি গাছের থিসিস তিনটি বৈশিষ্ট্য সম্পর্কিত কোনো বিশেষ সম্পত্তি থাকে না।
