২২-১ঃ Complete Binary Tree কী

গত মডিউলে আমরা জেনেছি , Binary Tree সম্পর্কে জেনেছি। Binary Tree এর একটি প্রকারভেদ হলো Complete Binary Tree.

Complete Binary Tree হলো এমন একটি Binary Tree যেখানে ঐ ট্রি এর শেষ লেভেল এর আগের লেভেল এ যত সংখ্যক Node থাকা দরকার তত সংখ্যক Node থাকবে এবং শেষ লেভেল এ সব Child পরিপূর্ণ থাকবে , বা পরিপূর্ণ না থাকলেও বাম দিক থেকে ফিলাপ হতে থাকবে।

খুবই সিম্পল একটি থিওরি। আসুন , কিছু Example এর সাহায্যে বিষয়টি ক্লিয়ার করে নেয়া যাক । Example 1 :

উপরের চিত্রে Binary Tree টির ৩ টি লেভেল। এখানে দেখা যাচ্ছে , প্রতিটি লেভেল এ যত সংখ্যক Node থাকা দরকার তা দিয়ে পরিপূর্ণ আছে। সুতারাং উক্ত Binary Tree টি একটি Complete Binary Tree.

Example 2:

উপরের চিত্রে Binary Tree এর ৩ টি লেভেল । এখানে শেষ লেভেল এর আগের লেভেল এর পর্যন্ত পুরোপুরি পরিপূর্ণ আছে। এইবার আসা যাক , শেষ লেভেলে। থিওরি অনুযায়ী , শেষ লেভেল এ যদি পরিপূর্ণ না থাকে , তবে শেষ লেভেল এ যে Node আছে তা বাম দিক থেকে পরিপূর্ণ হয়ে আসতে হবে । এ ক্ষেত্রে আমরা দেখতে পাচ্ছি , বাম দিক থেকে পরিপূর্ণ হয়ে Children গুলো ডান দিকে পূর্ণ হচ্ছে। সুতারাং উক্ত Binary Tree টি একটি Complete Binary Tree.

Example 3:

উপরের চিত্রে , শেষ লেভেল এর আগ পর্যন্ত Tree টি সম্পূর্ণ পরিপূর্ণ আছে। এখন দেখা যাক , শেষ লেভেল এ। থিওরি অনুযায়ী , শেষ লেভেল সম্পূর্ণ পরিপূর্ণ বা আংশিক পরিপূর্ণ থাকবে। আংশিক পরিপূর্ণ থাকলে , বাম দিক থেকে Tree টি পরিপূর্ণ হয়ে আসতে হবে। উক্ত Tree এর বাম দিকে দুটি Node যুক্ত হলেও , এর পরের Node টি Tree এর বাম দিকে যুক্ত না হয়ে , ডান দিকে যুক্ত হয়েছে। তাই উক্ত Tree টি একটি Complete Binary Tree নয়।