ডেটা স্ট্রাকচারে বাইনারি ট্রি রিপ্রেজেন্টেশন

এখানে আমরা দেখব কিভাবে কম্পিউটারের মেমরিতে একটি বাইনারি ট্রি রিপ্রেজেন্ট করতে হয়। এজন্য দুটি ভিন্ন মেথড রয়েছে। এগুলো হল অ্যারে ব্যবহার করে এবং লিংকড লিস্ট ব্যবহার করে।

ধরা যাক আমাদের একটা ট্রি আছে এরকম -

অ্যারে রিপ্রেজেন্টেশন ট্রি ডেটা লেভেল অর্ডার ফ্যাশনে স্ক্যান করে স্টোর করে। তাই এটি লেভেল বাই লেভেল নোড স্টোর করে। যদি কিছু এলিমেন্ট মিসিং থাকে, তবে সেটির জন্য ব্ল্যাঙ্ক স্পেস রেখে দেয়। উপরের ট্রির রিপ্রেজেন্টেশন নিচের মত -

ইন্ডেক্স ১ রুট ধারণ করে, এর দুটি চাইল্ড ৫ এবং ১৬, যেগুলো লোকেশন ২ এবং ৩-এ প্লেস করা হয়েছে। কিছু চাইল্ড মিসিং, তাই তাদের জায়গা খালি রেখে দেওয়া হয়েছে।

এই রিপ্রেজেন্টেশনে আমরা সহজে একটি নোডের দুটি চাইল্ডের পজিশন এই সূত্র দিয়ে পেতে পারি -

$$child_{1}=2*parent$$

$$child_{2}=(2*parent)+1$$

চাইল্ড থেকে প্যারেন্ট ইন্ডেক্স পেতে এই সূত্র ফলো করতে হয় -

$$parent=\lfloor\frac{child}{2}\rfloor$$

এই পদ্ধতিটি ভালো, এবং সহজে প্যারেন্ট ও চাইল্ডের ইন্ডেক্স পাওয়া যায়, কিন্তু এটি মেমরি ইফিশিয়েন্ট নয়। এটি অনেক স্পেস घেরে যা কোনো কাজে লাগে না। এই রিপ্রেজেন্টেশন কমপ্লিট বাইনারি ট্রি বা ফুল বাইনারি ট্রির জন্য ভালো।

অন্য পদ্ধতি হল লিংকড লিস্ট ব্যবহার করে। আমরা প্রতিটি এলিমেন্টের জন্য নোড তৈরি করি। এটি নিচের মত দেখাবে -