বাইনারি সার্চ ট্রি পর্ব - ১

প্রোগ্রামিং এর সাথে পথ চলার শুরুর দিকে যখন প্রথম ডাটা স্ট্রাকচারের নাম শুনি তখন কোনো গুরুত্বই দেইনি । তখন মনে হতো , " আরেহ, ডাটাগুলোকে নরমাল আমরা যেভাবে অ্যারেতে রাখি সেভাবে রাখলেইতো হয় । এগুলো নিয়ে এত চিন্তার কী আছে ? " তারপর ধীরে ধীরে এমন কিছু সমস্যা সামনে এসেছিলো যে সেগুলো সমাধান করতে গিয়ে বুঝলাম এগুলো অ্যারেতে যেভাবে ইচ্ছা সেভাবে রাখলেই হবেনা । ডাটাগুলোকে এমনভাবে সাজিয়ে রাখতে হবে যেন খুব দ্রুত ডাটাগুলো আমরা খুঁজে পাই ।

এ জন্য প্রোগ্রামিংয়ে ডাটা স্ট্রাকচার জানা খুব ভালভাবেই প্রয়োজন ।

এই পর্বে আমরা তেমনই একটি  ডাটা স্ট্রাকচারের ইমপ্লিমেন্টেশন শিখবো যার নাম হলো বাইনারি সার্চ ট্রি । কোডিং অংশে বাইনারি সার্চ ট্রি আমরা লিংকড লিস্ট দিয়ে ইমপ্লিমেন্ট করবো । কারো যদি লিংকড লিস্টের ধারণাটি ক্লিয়ার না থাকে তাহলে এখান থেকে ঢুঁ মেরে আসলে আশা করি ধারনাটি ক্লিয়ার হয়ে যাবে ।

ট্রি কী ?

    এবার আমরা কাজের কথায় আসি । প্রথমেই আমাদের মনে প্রশ্ন জাগে ট্রি কী ? যদি আপনাদের চোখের সামনে গাছের প্রতিচ্ছবি ভেসে ওঠে তাহলে ঠিক পথেই এগিয়েছেন । বাস্তবের গাছ আর প্রোগ্রামিংয়ের ট্রি আসলে একই । বাস্তবে গাছের যেমন শিকড় আছে , শাখা-প্রশাখা আছে তেমনি প্রোগ্রামিংয়েও ট্রি এর রুট (শিকড়) আছে , চাইল্ড (শাখা-প্রশাখা) আছে । অর্থাৎ প্রোগ্রামিংয়ে ট্রি হল কিছু নোড এবং এজ এর সমন্বয়ে তৈরি এমন একটি গ্রাফ যেখানে কোন সাইকেল থাকা যাবে না ।

যেমন ঃ

যেহেতু এই গ্রাফটিতে কোন সাইকেল নেই তাই এই গ্রাফটি একটি ট্রি

যেহেতু এই গ্রাফটিতে সাইকেল আছে তাই এই গ্রাফটিকে ট্রি বলা যাবেনা

বাইনারি ট্রি কী ?

    বাইনারি ট্রি হল এমন একটি ট্রি যেখানে প্রতিটি নোড এর সর্বাধিক দুটি চাইল্ড নোড থাকবে । বাম দিকের নোডটি হবে তখন Left Child এবং ডান দিকের নোডটি হবে Right Child ।

যেমন ঃ

চিত্রে আমরা দেখতে পাচ্ছি যে প্রতিটি নোডেরই হয় একটি না হয় দুটি চাইল্ড রয়েছে 

বাইনারি সার্চ ট্রি কী ?

    বাইনারি সার্চ ট্রি তে ট্রি টি এমনভাবে তৈরি করা হয় যেন এটি বাইনারি সার্চ প্রপার্টি মেনে চলে । এই বাইনারি সার্চ প্রপার্টি টি হল ঃ

• একটি নোডের Left Sub-Tree এর প্রতিটি নোডের Value সেই নোডের Value-র সমান বা তার থেকে ছোট হবে ।

• একটি নোডের Right Sub-Tree এর প্রতিটি নোডের Value সেই নোডের Value-র সমান বা তার থেকে বড় হবে ।

যেমন ঃ

একই রকম Value-র ক্ষেত্রে যেকোন একদিকে Value-টি রাখলেই হবে  অর্থাৎ 19 যদি দুবার থাকতো তাহলে 19 কে 19 এর যেকোন একপাশে রাখলেই হতো

কোডিং অংশে আমরা বাইনারি সার্চ ট্রি এর কিছু অপারেশন ইমপ্লিমেন্ট করবো ঃ

1. বাইনারি সার্চ ট্রি তৈরি করা ।
2. বাইনারি সার্চ ট্রি তে কোন একটি Element খোঁজা ।
3. বাইনারি সার্চ ট্রি তে কোন একটি Element ইনসার্ট করা ।
4. বাইনারি সার্চ ট্রি থেকে কোন একটি Element ডিলেট করা ।
5. বাইনারি সার্চ ট্রি ট্রাভার্স করা । বাইনারি সার্চ ট্রি তে ট্রাভার্স প্রক্রিয়া তিন রকমের ঃ Pre-Order , In-Order এবং Post-Order ট্রাভার্সাল ।

কেন বাইনারি সার্চ ট্রি ?

    ধরে নিই আমাদের কাছে একটি  অ্যারে আছে এরকম ঃ 

Index	1	2	3	4	5	6	7	8	9
Value	8	3	1	10	14	6	4	7	13

এখন আমাদেরকে যদি এই অ্যারেতে 13 কে খুঁজতে বলা হয় তাহলে আমরা কি করবো ? আমরা সচরাচর যা করি তাই করবো । প্রথম ইনডেক্স থেকে খোঁজা শুরু করবো এবং যতক্ষণ না 13 কে খুঁজে পাই ততক্ষণ এক এক করে পরের ইনডেক্সে যেতে যেতে শেষ পর্যন্ত যাবো । এখানে আমরা দেখছি যে 13 , ইনডেক্স 9 এ আছে । এভাবে খুঁজলে 13 কে খুঁজে পেতে আমাদের ৯ বার খোঁজা লাগবে । এখন উপরোক্ত ডাটাগুলো দিয়ে বাইনারি সার্চ ট্রি প্রপার্টি মেনে চলে এমন একটি ট্রি যদি আমরা তৈরি করি তাহলে এটি দেখতে এরকম হবে ঃ

অ্যারের মানগুলো দিয়ে বাইনারি সার্চ ট্রি বানানো হয়েছে

এখন আমরা মাত্র ৪ বার খুঁজলেই ১৩ কে আমরা পেয়ে যাবো । কিভাবে ? আমাদের রুট হল ৮ । এখন দেখবো এটিই ১৩ কিনা । যেহেতু না এবং ৮ এর চেয়ে ১৩ বড় তাই আমরা ৮ এর রাইট চাইল্ডে যাবো । ৮ এর রাইটে আছে ১০ , এটিও না এবং ১৩ , ১০ এর চেয়ে বড় । এখন ১০ এর রাইট চাইল্ডে যাবো । এখানে আছে ১৪ । ১৪ এর থেকে ১৩ ছোট বিধায় ১৪ এর লেফট চাইল্ডে যাবো । ফাইনালি আমরা এখানে ১৩ পেয়ে গিয়েছি । অর্থাৎ বাইনারি সার্চ ট্রি - ডাটা স্ট্রাকচারটি ব্যবহার করে ১৩ কে আমরা চার বার খুঁজেই পেয়ে গিয়েছি । এক্ষেত্রে সার্চিং প্রক্রিয়াটি অনেক ইফিশিয়েন্ট হয়েছে । তা ছাড়া নরমাল অ্যারেতে আমরা যদি কোন ভ্যালু অ্যাড করতে চাই এবং সেটি যদি হয় মাঝের কোন ইনডেক্স তাহলে বাকি ভ্যালু গুলোকে ইনডেক্সিং করতে গেলে যেমন বেশ ঝামেলায় পড়তে হবে তেমনি প্রক্রিয়াটিও খুব একটা ইফিশিয়েন্ট হবে না । ভ্যালু ডিলিটের ক্ষেত্রেও একই রকম ঝামেলা হবে ।

পরের পর্বে আমরা কোডিংয়ের মাধ্যমে বাইনারি সার্চ ট্রি এর উপরোক্ত অপারেশনগুলো ইমপ্লিমেন্ট করবো ইনশাল্লাহ ।