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

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

ধরুন আমাদের এইরকম একটি গাছ আছে -

অ্যারে উপস্থাপনা লেভেল অর্ডার ফ্যাশন ব্যবহার করে উপাদান স্ক্যান করে গাছের ডেটা সঞ্চয় করে। তাই এটি নোড সংরক্ষণ করে স্তর দ্বারা স্তর. যদি কিছু উপাদান অনুপস্থিত থাকে, তবে এটি তার জন্য ফাঁকা স্থান ছেড়ে দেয়। উপরের গাছের উপস্থাপনা নিচের মত -

সূচী 1 রুট ধরে আছে, এটির দুটি সন্তান রয়েছে 5 এবং 16, তাদের অবস্থান 2 এবং 3 এ রাখা হয়েছে। কিছু শিশু অনুপস্থিত, তাই তাদের স্থান ফাঁকা রাখা হয়েছে।

এই উপস্থাপনায় আমরা এই সূত্রটি ব্যবহার করে সহজেই একটি নোডের দুটি সন্তানের অবস্থান পেতে পারি −

$$child__{1}=2*পিতামাতা$$

$$child_{2}=\lgroup2*অভিভাবক\rgroup+1$$

সন্তানের কাছ থেকে পিতামাতার সূচক পেতে আমাদের এই সূত্রটি অনুসরণ করতে হবে −

$$parent=\begin{bmatrix}\frac{child}{2} \end{bmatrix}$$

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

আরেকটি পদ্ধতি হল লিঙ্ক করা তালিকা ব্যবহার করে। আমরা প্রতিটি উপাদানের জন্য নোড তৈরি করি। এটি নিচের মত হবে −