ডেটা স্ট্রাকচার

 

ডেটা স্ট্রাকচার কী?

ডাটা নিয়ে পরবতীতে কাজ করার জন্য লজিক্যাল বা ম্যাথমেটিক্যাল উপস্থাপন করার কৌশলকে ডাটা স্ট্রাকচার বলে।

Schaum’s Outline Series এর Data Structures বইয়ের সংজ্ঞা অনুযায়ী বলা যায়, ডেটাকে অনেক ভাবেই সাজিয়ে রাখা যায়। ডেটা স্ট্রাকচার হচ্ছে ডেটাগুলোকে নির্দিষ্ট পদ্ধতিতে সাজিয়ে রাখার লজিক্যাল বা ম্যাথমেটিক্যাল মডেল।

 

অর্থাৎ ডেটাকে কম্পিউটার মেমরিতে সংরক্ষণ ও সেগুলোকে নিয়ে প্রসেস করার জন্য efficient পদ্ধতিতে ডেটাগুলোকে organize করার নামই ডেটা স্ট্রাকচার। কোন একটা ডেটা স্ট্রাকচার নিয়ে কাজ করার ক্ষেত্রে দুইটা জিনিস মাথায় রাখতে হয়। প্রথমত, ডেটাগুলোর মধ্যে পারস্পরিক সম্পর্ক বুঝানোর জন্য স্ট্রাকচারের দিক দিয়ে যথেষ্ট সমৃদ্ধ হতে হবে। দ্বিতীয়ত, এটাকে হতে হবে খুব সিম্পল, যেন দরকারের সময় effectively ডেটাগুলোকে নিয়ে কাজ করা যায়।

ডেটা স্ট্রাকচার কেন শেখা প্রয়োজন?

কোন একটা কাজ যদি লজিক্যাল বা ম্যাথমেটিক্যালি করা হয় এতে যেকোন কাজ অনেক effective ও efficiently করা যায়,

 

যেমন- কোন ক্লাশে ৩ জন স্টুডেন্ট আছে এদের নাম করিম, রহিম, সোহেল। পরিক্ষার ফলাফল বের হয়েছে, এখন যদি বলা হয় এদের প্রাপ্ত মোট নম্বর কত? তাহলে আমরা চিন্তা করব, করিম নম্বর পেয়েছে – ৮২, রহিম নম্বর পেয়েছে – ৮০, সোহেল নম্বর পেয়েছে – ৮৮, মোট= ২৫০

এরমানে প্রোগ্রামিং এ যদি করি তিনটা ভেরিয়েবল নিতে পারি x,y,z, এদের নম্বরগুলি ক্রমান্বয়ে ভেরিয়েবলে রাখতে পারি

X=82;

Y=80;

Z=88

Total=x+y+z=250;

কিন্তু  এখন যদি বলা হয় এই ক্লাসে স্টুডেন্ট আছে ৯০ জন, এই ৯০ জন স্টুডেন্ট এর মোট নম্বর বের করতে হবে।  তাহলে আমরা কি এমন চিন্তা করব যে, আমরা ৯০ টা ভেরিয়েবল নিব, দেন ৯০ টা ভেরিয়েবলের মান এসাইন করব, তারপর ৯০ টা ভেরিয়েবল যোগ করে ফলাফল বের করব, যদি চিন্তাটা এমন হয় তাহলে সেই চিন্তাটা ভালে তবে খুব ভালো না, আমরা কাজটা ডাটা স্ট্রাকচার ব্যবহার করে অনেক সহজে করতে পারি, এখানে ডাটা স্ট্রাকচার হিসেবে যদি একটা Array নেওয়া হয়, আর ৯০ জন স্টুডেন্টের জন্য এ্যারে সাইজ যদি নিধারন করা হয়-৯০ তাতে বার বার ৯০ টা ভেরিয়েবল ডিক্লিয়ার করতে হবে না, সময়, কম বাচবে, পাশাপাশি কাজটা অনেক স্মাটলি করা যাবে।

এরমানে সময় সেভ করা ও ইফিসিয়েন্টলি কাজ করার জন্য ডেটা স্ট্রাকচারের বিকল্প নাই।

ধর তোমার কোম্পানী তোমাকে কোন একটা ব্যাংকের সার্ভিস সেন্টারের অটোমেশন সফটওয়্যারের কাজ দিল। যেখানে কাস্টমাররা ব্যাংকে ঢুকেই একটা বুথ থেকে তার টোকেন প্রিন্ট করবে। এরপর ৫-৬ বুথ থেকে কাস্টমারদেরকে ডাকবে সার্ভিস দেয়ার জন্য। তাহলে ১৫ জনের পরে যার টোকেন নাম্বার, তাকে ডাকা হবে এই ১৫ জনের পরেই। তার মানে এখানে Queue Data Structure ইমপ্লিমেন্ট করা হচ্ছে। কোন নতুন কাস্টমার টোকেন প্রিন্ট করলেই তার নাম্বারটা কিউতে ফেলে দেয়া হবে। প্রতিটা বুথ থেকে যখনই কাউকে ডাকা হবে এই কিউয়ের সামনে থেকে ডাকা হবে। অর্থাৎ যে আগে আসবে সে কিউয়ের সামনের দিকে থাকবে।

 

 

ডেটা স্ট্রাকচার দুই ধরনের

১) লিনিয়ার ডেটা স্ট্রাকচার(Linear data structure)

• Array
• Stack
• Queue
• Priority Queue
• Linked List

2) নন লিনিয়ার ডেটা স্ট্রাকচার (Non Linear data structure)

• Tree
• Trie
• Heap
• Hash Table

Array: A Linear Data Structure

অ্যারে হচ্ছে এক জাতীয় একই ধরনের ডাটার সমাহার,যেখানে শুধুমাত্র এক ধরণের ডেটাই সংরক্ষণ করা যায়। অর্থাৎ অ্যারের একটা নির্দিষ্ট সাইজ থাকবে।

লিনিয়ার ডেটা স্ট্রাকচার হচ্ছে এমন এক ধরণের স্ট্রাকচার যা মেমরিতে sequence অনুযায়ী স্টোর হয়। এই স্ট্রাকচারের ডেটাগুলো একটার পর একটা সিরিয়াল্যি সাজানো থাকে। এই লিনিয়ার ডেটা স্ট্রাকচারের দুই ধরনের representation রয়েছে। একটা হচ্ছে Array. সোজা সাপটা ভাবে একই ডেটা টাইপের (int, float, double, char) ডেটাগুলো লাইন ধরে সাজানো থাকে অ্যারের মধ্যে। আরেকটা রিপ্রেজেন্টেশন হচ্ছে, লিস্টের element-গুলোর মধ্যকার সম্পর্ক। এর উদাহরন হচ্ছে Linked List.

অ্যারেকে এক কথায় সংজ্ঞায়িত করতে চাইলে এভাবে বলা যায়, নির্দিষ্ট সংখ্যক ডেটা স্টোর করার জন্য একটা স্ট্রাকচার যেখানে শুধুমাত্র এক ধরণের ডেটাই সংরক্ষণ করা যায়। অর্থাৎ অ্যারের একটা নির্দিষ্ট সাইজ থাকবে। এই সাইজের চেয়ে বেশি ডেটা কোন অ্যারে স্টোর করতে পারবে না। আর একই ধরণের ডেটাই স্টোর করতে হবে। int type ডেটা স্টোর করতে চাইলে সেই অ্যারেতে শুধুমাত্র int type এর ডেটাই স্টোর করা যাবে। সেখানে int, float, double, char ইত্যাদি মিক্স করে স্টোর করা যাবে না। যদি int type একটা ১০০ সাইজের অ্যারে ডিক্লেয়ার করি তাহলে এই অ্যারেতে সর্বোচ্চ ১০০ টা int-ই স্টোর করা যাবে।

যে কোন ডেটা স্ট্রাকচারেই data insert, traverse, update, delete, searching, sorting এর মত ব্যাসিক কিছু কাজ থাকে। এই পোস্টে অ্যারের Declaration, Insertion, Traverse এই অপারেশনগুলো দেখানোর চেষ্টা করা হবে।

Array Declaration

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

সর্বোচ্চ ১০০ জন ছাত্রের বয়স যদি আমাদের স্টোর করে প্রসেস করার দরকার হয় সেক্ষেত্রে আমরা অ্যারেটা ডিক্লেয়ার করতে পারি নিচের মত করেঃ

Array Declaration in C

int age[100];

int হচ্ছে ডেটা টাইপ। ধরে নিলাম বয়স হিসেবে শুধু পূর্ণ সংখ্যাই ইনপুট দেয়া হবে। তাই এখানে int টাইপের অ্যারে নিয়েছি। যদি ভগ্নাংশ নিয়ে কাজ করার দরকার হয় সেক্ষেত্রে float বা double ডেটা টাইপের অ্যারে ডিক্লেয়ার করতে হবে। এই অ্যারেতে সর্বোচ্চ ১০০ টি পূর্ণ সংখ্যা স্টোর করা যাবে।

Array Representation. Photo Credit: www.java67.com/

Array Initialization (insert)

প্রথমত দেখি যদি কিছু ফিক্সড ভ্যালু অ্যারেতে স্টোর করতে চাই তাহলে কিভাবে করা যায়।

Assign Value into Array in C

age[0] = 45; age[1] = 17; . . .

উপরে দেখা যাচ্ছে age নামক অ্যারের প্রথম ইন্ডেক্সে একটা ভ্যালু (45) assign করা হয়েছে। age[0] অ্যারেটির প্রথম ইন্ডেক্স। সব ল্যাঙ্গুয়েজেই অ্যারের ইন্ডেক্সিং শুরু হয় শূণ্য থেকে। সি ল্যাঙ্গুয়েজে অ্যারের প্রতিটা ইন্ডেক্স অ্যাক্সেস করতে হয় অ্যারের নাম দিয়ে এরপর 3rd bracket এর ভিতরে ইন্ডেক্সের নাম্বার লিখে। age অ্যারের সর্বশেষ ইন্ডেক্স হচ্ছে ৯৯। সর্বশেষ ইন্ডেক্স বা অ্যারের সর্বশেষ খোপে যদি কোন মান অ্যাসাইন করতে চাই তাহলে লিখতে হবে এভাবেঃ age[99] = 65;

একটা বিষয় লক্ষ্যনীয়, অ্যারের ইন্ডেক্স নাম্বার আর অ্যারের ইন্ডেক্সের ভ্যালু কিন্তু ভিন্ন জিনিস। age[1] = 17; বলতে বুঝায় age নামক অ্যারেতে যতগুলো ইন্ডেক্স বা খোপ আছে তাদের মধ্য থেকে ১ নাম্বার খোপে ১৭ মানটা বসিয়ে দাও। ১ হচ্ছে খোপের নাম্বার। এই নাম্বারিং এর মাধ্যমেই কিন্তু আমরা লিনিয়ার অ্যারে ইমপ্লিমেন্ট করতে পারছি। ০, ১, ২, ৩, … এভাবে এই খোপের সংখ্যাগুলো বাড়ছে। আর ১৭ হচ্ছে ছাত্রের বয়স। যেটা অরিজিনাল ডেটা বা ভ্যালু। এক কথায় বললে ১৭ ভ্যালুটাকে age অ্যারের 1 নাম্বার ইন্ডেক্সে বসানোর জন্য age[1] = 17; লিখতে হবে। আশা করি ইন্ডেক্স নাম্বার আর ইন্ডেক্স ভ্যালু গুলিয়ে ফেলবে না আর।

এখন দেখব সি ল্যাঙ্গুয়েজ দিয়ে একটা অ্যারেতে কিভাবে ইনপুট নিতে হয়। অ্যারে নিয়ে কাজ করতে গেলে Loop এর পরিষ্কার ধারণা থাকতে হবে। যদি লুপের মধ্যে ঝামেলা থাকে তাহলে উচিত হবে লুপটা একটু রিভাইস দিয়ে এসে বাকি লেখাটা পড়া।

তোমরা চাইলে ম্যারাথন স্টাইলে ইনপুট নিতে পারো কোন রকমের লুপের ইউজ ছাড়াই।

Array input in C

scanf(“%d”, &age[0]); scanf(“%d”, &age[1]); scanf(“%d”, &age[2]); . .

কিন্তু উপরের সিসটেমে কেউ অ্যারেতে ইনপুট করে না। লুপের মাধ্যমেই ইনপুট করতে হয়। আমরা নিচে নির্দিষ্ট সংখ্যক ছাত্রের বয়স ইনপুট দেয়ার জন্য কোড লিখব। number_of_student একটি int type variable. এতে ইনপুট নেয়া হচ্ছে কতজন ছাত্রের বয়স ইনপুট নেয়া হবে।

Array input using Loop in C

scanf(“%d” &number_of_student); for(i = 0; i<number_of_student; i++) {     scanf(“%d”, &age[i]); }

উপরের কোডে লুপের ভিতর ইনপুট নেয়ার কাজ চলতে থাকবে। একদম শুরুতে অ্যারের প্রথম ইন্ডেক্স 0-তে ইনপুট হবে। এরপর 1, 2, … (number_of_student-1) পর্যন্ত সবগুলো ইন্ডেক্সে ইনপুট হবে।

সব সময় যে সিরিয়াল্যি সবগুলো ইন্ডেক্সেই মান ইনপুট নিতে হবে এমন না। তুমি চাইলে এক ঘর বাদ দিয়ে দিয়েও ইনপুট নিতে পারো। যেমনঃ age[0], age[2], age[4]… এগুলোতে ইনপুট নিবে, কিন্তু বাকিগুলোতে নিবে না। এখানে তোমাকে ইনপুট নেয়া শেখানো হল। পরবর্তীতে কখন কিভাবে কী কাজে লাগাতে হবে সেটা তুমি সিদ্ধান্ত নিবা।

Array Traversing

তুমি ১০০ সাইজের একটা অ্যারে ডিক্লেয়ার করলা। এরপর তাতে কিছু ডেটা রাখলা এরপর কাজ কী? এরপর হয় তোমাকে সেই ডেটাগুলো প্রিন্ট করতে হবে, বা নির্দিষ্ট কোন ডেটার উপর নির্দিষ্ট কোন কাজ করা লাগতে পারে। কোন একটা ডেটা সার্চ করার দরকার হতে পারে অথবা কোন একটা শর্ত অনুযায়ী ডেটাগুলোকে সাজানো লাগতে পারে। এর মানে হচ্ছে তোমার মেমরি সংরক্ষিত ডেটাগুলোতে তুমি অ্যাক্সেস করবে বা ডেটাগুলোর উপর তুমি ভ্রমণ (traverse) করবে।

যেভাবে লুপ চালিয়ে প্রতিটা ইন্ডেক্সে ইনপুট নিয়েছিলাম, একই ভাবে লুপ চালিয়ে প্রতিটা ইন্ডেক্সে ট্রাভার্স করতে পারি। এই ট্রাভার্সের মাধ্যমে চাইলে কোন ডেটা প্রিন্ট করতে পারি, কোন ডেটার সাথে অ্যারিথমেটিক কোন অপারেশন ঘটাতে পারি। কোন ডেটা মুছে দিতে পারি ইত্যাদি।

এখন সবগুলো ইন্ডেক্সের ভ্যালুগুলো একেকটা লাইনে প্রিন্ট করতে চাইলে নিচের কোডটা লিখা যায়ঃ

Array output using Loop in C

for(i = 0; i<number_of_student; i++) {     printf(“%d\n”, age[i]); }

তাহলে age অ্যারের 0-তম ইন্ডেক্স থেকে (number_of_student – 1)-তম ইন্ডেক্স পর্যন্ত সবগুলো ইন্ডেক্সের ভ্যালু পরপর লাইনে প্রিন্ট করে দিবে। যদি শেষ থেকে শুরুর element-গুলো প্রিন্ট করতে চাও তাহলে লুপটাকে একটু মডিফাই করলেই কাজ করবে। যথাঃ for(i = number_of_student – 1; i>=0; i–){}. অর্থাৎ অ্যারের শেষ ইন্ডেক্স থেকে প্রথম ইন্ডেক্সের সবগুলো মান প্রিন্ট হবে।

তুমি ইচ্ছা করলে নির্দিষ্ট একটা ইন্ডেক্সের ভ্যালুও ইন্ডেক্স নাম্বারের সাহায্যে প্রিন্ট করতে পারোঃ

Print a value using Array index number in C

 

printf("%d", age[3]);

উপরের কোডে age array এর 3 নাম্বার ইন্ডেক্সের মানটা প্রিন্ট হবে।

কখনো যদি এমন হয় যে ইউজার লুপ ঘুরিয়ে ১০ টি ইন্ডেক্সের নাম্বার ইনপুট দিবে। যেই ইন্ডেক্সের নাম্বার ইনপুট দিবে সেই ইন্ডেক্সের ভ্যালু প্রিন্ট করতে হবে। তাহলে কী করবা?

Print value of an Array by index in C

for(i = 1; i<=10; i++) {     scanf(“%d”, &index);          printf(“%d”, age[index]); }

উপরের কোডে প্রতিবার একটা ইন্ডেক্সের মান ইনপুট নেয়া হচ্ছে। পরের লাইনে সেই ইন্ডেক্স এর ভ্যালু প্রিন্ট করা হচ্ছে।

সব ছাত্রের বয়সের গড় বের করতে চাইলে কী করতে হবে? ধরো প্রথমে অ্যারেতে ইনপুট নেয়া হল। এরপর অ্যারেতে লুপ চালিয়ে ট্রাভার্স করব। প্রতিটা ইন্ডেক্সের ভ্যালু যোগ করব এরপর number_of_student দিয়ে ভাগ করব।

Summation and average using Array in C

for(i = 0; i<number_of_student; i++) {     sum = sum + age[i]; } average = sum/number_of_student; printf(“%d”, average);

দীর্ঘ এই পোস্টের মাধ্যমে অ্যারে ডিক্লেয়ার করা, তাতে ভ্যালু অ্যাসাইন বা ইনপুট করা ও ভ্যালুগুলোতে ট্রাভার্স করার ব্যাপারে বিস্তারিত আলোচনা করার চেষ্টা করেছি। পরের পর্বে আলোচনা করব অ্যারের ভ্যালু আপডেট, ডিলেট, সার্চ, সর্ট ইত্যাদি নিয়ে।

 

Deletion an Element of Array

স্টোর করা ডেটাগুলো প্রয়োজনে ডিলেট করার দরকার হতে পারে। অ্যারেতে সিকোয়েন্স অনুযায়ী ডেটা স্টোর করা থাকে। age নামক অ্যারের সাইজ ১০ হলে তার ইন্ডেক্স নাম্বার হবে ০ থেকে ৯। আমরা যদি age[6] এর ডেটাকে অ্যারে থেকে মুছে ফেলতে চাই তাহলে age[7] এর ভ্যালুকে অ্যাসাইন করতে হবে age[6] এ। age[8] এর ভ্যালুকে অ্যাসাইন করতে হবে age[7] এ। age[9] এর ভ্যালু অ্যাসাইন করতে হবে age[8] এ। তারমানে age[7] থেকে age[9] পর্যন্ত সবগুলো ভ্যালুকে আমরা ১ ঘর করে বাম দিকে সরিয়ে দিলাম। কোডটা দেখলে আরো ক্লিয়ার হবেঃ

Array Delete operation in C

#include<stdio.h>   int main() {     int arr_size = 5, index, i, j;     int age[arr_size];       //array input     printf("Input 5 elements: ");     for(i =0; i<arr_size; i++)         scanf("%d", &age[i]);       //input zero based index number for deletion     printf("Input index number (0 to 4): ");     scanf("%d", &index);       //deletion by replacing     j = index;     while(j<arr_size-1)     {         age[j] = age[j+1];         j++;     }       arr_size = arr_size - 1;       for(i = 0; i<arr_size; i++)         printf("%d ", age[i]);       return 0; }

১৯ নাম্বার লাইনের while loop এর ভিতরে মূল রিপ্লেসিং এর কাজটা হচ্ছে। এখানে কন্ডিশন দেয়া আছে (j<arr_size-1). কারণ আমরা অ্যারের index-তম ইন্ডেক্সকে রিপ্লেস করছি (index+1)-তম ইন্ডেক্সের ভ্যালু দিয়ে। অ্যারের সাইজ যদি হয় ৫ তাহলে সর্বশেষ রিপ্লেসিং এর কাজটা হবেঃ age[3] = age[4]; কারণ 4-ই অ্যারের লাস্ট ইন্ডেক্স। লুপের ভিতরে j এর মান ১ করে বাড়ছে। while এর কন্ডিশনে (j<arr_size-1) দেয়ার মানে হচ্ছে লুপের ভিতরের কাজ চলতে থাকবে যতক্ষণ পর্যন্ত j এর মান array’র শেষ ইন্ডেক্সের চেয়ে ছোট হবে। এই প্রোগ্রামের ক্ষেত্রে শেষ ইন্ডেক্স হচ্ছে চার। তাই j এর মান ৩ হলেও লুপের ভিতরে ঢুকবে। তখন age[3] = age[4] এই কাজটা হবে। এটা করার পর j++ করা হচ্ছে। ফলে j  এর মান বেড়ে দাঁড়াবে 4. যা অ্যারের লাস্ট ইন্ডেক্স 4 এর চেয়ে ছোট নয়। তাই আর লুপের ভিতরে ঢুকবে না। বের হয়ে এসে অ্যারের সাইজ রাখা হয়েছে যেই ভ্যারিয়েবলে (arr_size) তার মান ১ কমিয়ে দিবে। এরপর FOR Loop দিয়ে প্রিন্ট করা হল আপডেটেড অ্যারেটা। এখন ৫টার বদলে চারটা এলিমেন্ট প্রিন্ট হল।

খেয়াল করে দেখো, অ্যারের শেষ ইন্ডেক্সে কিন্তু এখনো মান আছে। ম্যানুয়াল্যি age[4] প্রিন্ট করলে তোমার ইনপুট করা সর্বশেষ সংখ্যাটা প্রিন্ট হবে। arr_size ভ্যারিয়েবলের মাধ্যমে আমরা জাস্ট অ্যারের length-টা কনট্রোল করছি।

User defined function এর ধারণা থাকলে তুমি চাইলে এই deletion এর কোডটুকু দিয়ে একটা ফাংশন লিখে ফেলতে পারো। যেখানে ফাংশনের প্যারামিটার হিসেবে পাঠাবে ইন্ডেক্সের ভ্যালু। ঐ ফাংশনটা ডিলেটের কাজ করে দিবে।

Searching

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

Sorting

অ্যারের ডেটাগুলোকে একটি নির্দিষ্ট অর্ডারে সাজানোর নামই সর্ট করা। ছোট থেকে বড় বা বড় থেকে ছোট আকারে অ্যারের ইলিমেন্টগুলোকে সাজানোর জন্য অনেকগুলো অ্যালগরিদম রয়েছে। একেকটা অ্যালগরিদমের একেকটা সুবিধা ও অসুবিধা রয়েছে।

 

স্ট্যাক (Stack) ডাটা স্ট্রাকচার

স্ট্যাক (Stack) ডাটা স্ট্রাকচারে ডাটাগুলো রাখা হয় এমনভাবে যেন নতুন কোনো ডাটা সেখানে রাখতে হলে সবচাইতে উপরে রাখতে হয়, এবং নেয়ার সময়ও সবসময় প্রথমে উপরের ডাটাটাকে নিতে হবে। তারমানে স্ট্যাকে তুমি যাই করো না কেন, সেটা হতে হবে সবচাইতে উপরের ডাটাতে। আমরা কোনো ডাটা রাখতে হলে সেটাকে রাখবো আগের গুলোর ওপরে, আর নেয়ার সময়ও নিতে হবে সবার উপরেরটা। 

জিনিসটা হবে এরকম-

 

 

স্ট্যাকে ডাটা রাখাকে বলা হয় Push আর ডাটা তুলে নেয়াকে বলা হয় Pop ।

 

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

আসলে পুরো ব্যাপারটা এভাবে বলা হয় জিনিসটা বোঝার সুবিধার্থে, তাতে করে ব্যাপারটা সহজে মাথায় ঢোকে।

তারমানে আসলে যেটা হয় সেটা হলো, আমরা সবার শেষে যেটাকে রাখবো, আমাদের লিস্টে, তুলতে হলে সেটাকেই প্রথমে তুলতে হবে, শেষেরটা না তুলে অন্য কোনোটা তোলা যাবে না। আর মাঝখানে হুট করে কোনো ডাটাও রাখা যাবে না (যেমনটা অ্যারে আর লিংকড লিস্টে করা যায়)।

এই পদ্ধতিকে সুন্দর করে বলা হয় "Last In First Out (LIFO)" । মানে যাই করো না কেন সেটা হতে হবে সবার শেষে। খেয়াল করে দেখো তো আমরা আমাদের বাস্তব জীবনে কি এরকম কোনো পদ্ধতি ব্যবহার করি?? 

আচ্ছা, আমরা যখন খাবার প্লেট সাজিয়ে রাখি, সেটা কিভাবে রাখি? আমরা যখন সিডি বক্সে সিডি রাখি সেটা কি আমরা অ্যারের মত করে রাখি না কি অন্য কোনোভাবে রাখি?

 

এতক্ষণে নিশ্চয়ই বোঝা হয়ে গেছে, স্ট্যাক বলতে আসলে কি বোঝাচ্ছে??

 

আচ্ছা, এবার আসি কিভাবে স্ট্যাক কোড করা যায়। এ্যারে আর লিংকড লিষ্ট দুইটা দিয়েই স্ট্যাক কোড করা যায়। 

প্রথমে বলি, এ্যারে দিয়ে কিভাবে কোড করা যায়।

যেহেতু আমরা সবসময় শেষ পজিশনে ডাটা রাখবো এবং সেখান থেকে ডাটা উঠিয়ে নিবো, তার মানে আমরা প্রথমে একটা এ্যারে নিয়ে নিবো ডাটা রাখার জন্য আর একটা ভ্যারিয়েবল top নিবো যেটা দিয়ে আমরা বুঝতে পারবো এ্যারের শেষ কোন পজিশন পর্যন্ত ডাটা রাখা হয়েছে।

এরকম-

#include<stdio.h> 

#define sz 100   

int arr[sz],top=0;

এখন আমাদের ডাটা Push করার জন্য একটা ফাংশন হবে এরকম-

void push(int val)

{

    if(top>=sz)

        printf("No more space on Stack.\n");

    else

        arr[top++]=val;

}

যেহেতু আমাদের এ্যারের সাইজ নির্দিষ্ট, এজন্য আমাদের একটা চেকিং রাখতে হচ্ছে যাতে করে আমাদের এ্যারেতে জায়গা শেষ হয়ে গেলে আমরা আর ডাটা insert করবো না। তানাহলে arr তে ডাটা রাখবো আর top কে increase করবো।

আর pop করার জন্য ফাংশনটা হবে এরকম-

void pop()

{

    if(top<=0)

    {

        printf("Stack is empty\n");

    }

    else

    {

        top--;

        printf("Popped element: %d\n",arr[top]);

    }

}

এখানেও একটা চেকিং রাখতে হচ্ছে, যখন স্ট্যাকে আর কোন ডাটা থাকবে না তখনকার জন্য। 

লক্ষ্য করার বিষয় হলো, যেহেতু আমাদের top সব সময় এক ঘর এগিয়ে থাকে, মানে এমন জায়গায় থাকে যেখানে ডাটা বসিয়ে top পরের ঘরে চলে যায় যেখানে এখনো ডাটা ইনসার্ট করা হয়নি, তাই আমরা pop করার সময় প্রথমে top কে একঘর আগে নিয়ে আসি, যেখানে শেষ ডাটাটা আছে। তারপর সেখান থেকে ডাটাটা নিয়ে নেই।

আর তারপর যদি দেখতে চাই আমাদের স্ট্যাকে কি কি ভ্যালু আছে তাহলে এভাবে দেখে নিতে পারি-

void printlist()

{

    int i;

    for(i=0;i<top;i++)

        printf("%d ",arr[i]);

    puts("");

}

ব্যস, এভাবেই আমাদের স্ট্যাকের কোডিং করা হয়ে গেলো। 

স্ট্যাকের অপারেশনটা দেখতে হয় এরকম-

 

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

 

স্ট্রাকচার(Structure) এবং ইউনিয়ন(Union)

স্ট্রাকচার(Structure) এবং ইউনিয়ন(Union) দুইটাই সি প্রোগ্রামিং ল্যাংগুয়েজের ইউজার ডিফাইন্ড(User Defined) ডাটা টাইপ। ইউজার ডিফাইন্ড ডাটা টাইপ হচ্ছে এমন একটা ডাটা টাইপ যেটার টাইপ কি হবে সেটা ইউজার অর্থাৎ প্রোগ্রামার ঠিক করে দেবে। অনেক সময় আমাদের এমন কিছু জটিল প্রোগ্রাম করার প্রয়োজন হতে পারে যখন বেসিক ডাটা টাইপ ব্যবহার করা কষ্টসাধ্য। এসব ক্ষেত্রে আমরা এই স্ট্রাকচার এবং ইউনিয়ন ব্যবহার করে কাজগুলোকে অনেক সহজ করে নিতে পারি। এখন আমরা এই দুইটা ডাটা টাইপের গঠন ও ব্যবহার সম্পর্কে জানব –

স্ট্রাকচার(Structure)

স্ট্রাকচার ডিফাইন করতে struct কিওয়ার্ড(Keyword) টি ব্যবহার করতে হয়। তারপর স্ট্রাকচারের নাম অর্থাৎ আমাদের কাঙ্খিত ভেরিয়েবলের নাম। এখন আমরা একটি স্ট্রাকচার তৈরি করব এবং এর বিভিন্ন অংশ সম্পর্কে জানব –

#include <stdio.h> #include <string.h> struct Student{     unsigned long int roll;     char name[20];     char dept[10]; }; int main() {     struct Student s1,s2;         s1.roll=100120;     strcpy(s1.name,"Shahinur");     strcpy(s1.dept,"CSE");     printf("Roll:%d\nName:%s\nDepartment:%s\n",s1.roll,s1.name,s1.dept);         printf("The memory size is: %d",sizeof(s1));     return 0; }

৯ নম্বর লাইনে আমরা একটা স্ট্রাকচার ডিক্লেয়ার করেছি। struct কিওয়ার্ড এর পরে আমরা একটা নাম দিয়েছি Student, এর এটাই আমাদের ডিফাইন করা ভেরিয়েবলের নাম। তারপর আমরা আমাদের প্রয়োজনমত মৌলিক ডাটা টাইপ দিয়ে সাজিয়েছি। ব্রাকেটের শেষে একটা সেমিকোলন দিয়ে স্ট্রাকচারটি শেষ হয়েছে।

১৬ নম্বর লাইনে আমরা Student নামের স্ট্রাকচার টাইপের একটা ভেরিয়েবল s1 এবং s2 ডিক্লেয়ার করেছি। সংক্ষিপ্ত কোডের জন্য আমরা এখানে শুধু s1 ভেরিয়েবল টাই ব্যবহার করেছি।

স্ট্রাকচারের কোন নির্দিষ্ট এলিমেন্ট কে এক্সেস করতে হলে ডট(.) অপারেটর ব্যবহার করতে হয়। ১৮ নম্বর লাইনে আমরা s1.roll দিয়ে আমরা s1 এর roll এলিমেন্টটাকে এক্সেস করেছি এবং সেখানে একটা ভ্যালু এসাইন করেছি একেবারে সাধারন ভেরিয়েবলে এসাইন করার মত। বাকিগুলোও একই রকম। এখানে মনে রাখা দরকার, আমরা কিন্তু s1 ভেরিয়েবলের এলিমেন্টগুলো ব্যবহার করেছি। এর প্রভাব s2 তে পড়বেনা। s2 কে ব্যবহার করতে গেলেও একইভাবে ডট অপারেটর দিয়ে এক্সেস করেতে হবে।

আমার এখানে উপরের কোডটির আউটপুট নিম্নরুপঃ

Roll:100120

Name:Shahinur

Department:CSE

The memory size is: 40

এখানে লক্ষ্যনীয় যে আমাদের s1 ভেরিয়েবলটি মেমরিতে ৪০ বাইট জায়গা নিয়েছে। একটু হিসাব করি।

আমরা জানি, সাধারণ int মেমরিতে ২ বাইট জায়গা রাখে। কিন্তু আমরা এখানে unsigned long int ব্যবহার করেছি, আর এই unsigned long int মেমরিতে ৮ বাইট জায়গা দখল করে। অন্যদিকে আমরা জানি char টাইপ, মেমরিতে ১ বাইট জায়গা দখল করে। সেই হিসাবে মেমরি সাইজ = ৮+২০+১০ = ৩৮ বাইট। মনে হয়তো খটকা লেগে গেল যে আমাদের প্রোগ্রামে তো মেমরি সাইজ ৪০ দেখাচ্ছে তাহলে হিসাবে ৩৮ কেন আসল? এর কারণ হচ্ছে বাকি ২ বাইট প্যাডিং এর জন্য ব্যবহৃত হয়েছে।

ইউনিয়ন(Union)

ইউনিয়ন এবং স্ট্রাকচার একই ধরনের কাজ করে। শুধুমাত্র মেমরি হিসাবটা আলাদা। স্ট্রাকচারের মেমরি সাইজ হয় যে বেসিক ডাটাটাইপগুলো ব্যবহার করা হয়েছে সেই মেমরির যোগফলের সমস্টি বা তার থেকে বেশি। কিন্তু ইউনিয়নের ক্ষেত্রে একটু ভিন্ন। ইউনিয়নের মেমরি সাইজ হয় ঐ ইউনিয়নে ব্যবহৃত সবচেয়ে বড় ডাটা টাইপের সাইজের সমান বা বড়। উপরের কোডটা যদি আমরা ইউনিয়নের কোড দিয়ে রিপ্লেস করি তাহলে হবে –

/* #include <stdio.h> #include <string.h> union Student{     unsigned long int roll;     char name[20];     char dept[10]; }; int main() {     union Student s1,s2;     s1.roll=100120;     strcpy(s1.name,"Shahinur");     strcpy(s1.dept,"CSE");     printf("Roll:%d\nName:%s\nDepartment:%s\n",s1.roll,s1.name,s1.dept);     printf("The memory size is: %d",sizeof(s1));     return 0; }

লক্ষ্য করবেন এখানে শুধু struct কে union দিয়ে রিপ্লেস করা হয়েছে। আমার এখানে মেমরি সাইজ এসেছে ২৪। অর্থাৎ সর্বোচ্চ সাইজ name এর সাথে প্যাডিং যোগ করে ২৪ হয়েছে।

কিউ ডেটা স্ট্রাকচার – Queue Data Structure

স্ট্যাকের (Stack) মতই আরেকটি লিনিয়ার (Linear) ডাটা স্ট্রাকচার হল কিউ (Queue)। লিনিয়ার ডাটা স্ট্রাকচার বলতে বুঝায় যেখানে আইটেমগুলো ধারাবাহিকভাবে রয়েছে, যেমন: স্ট্যাক, কিউ, লিংকড (Linked) লিস্ট। বাংলায় কিউকে আমরা সারি বলতে পারি। তবে বুঝানোর সুবিধার্থে আমরা কিউ বলেই আপাতত চালিয়ে নেব।

কিউ হল কতগুলো আইটেমের এমন এক ধারাবাহিক সংগ্রহশালা (কালেকশন - collection) যেখানে নতুন আইটেমের সংযোজন (এনকিউ – enqueue) সংগ্রহশালার এক প্রান্তে আর পুরনো আইটেমের অপসারণ (ডিকিউ - dequeue) ঠিক তার বিপরীত প্রান্তে হয়। বোঝার সুবিধার্থে, যে প্রান্তে নতুন আইটেমের সংযোজন হয় সে প্রান্তকে আমরা পিছনের অংশ বা রিয়ার (rear) অথবা টেইল (tail - লেজ) বলতে পারি। আর যে প্রান্তে পুরনো আইটেমের অপসারণ হয় সে প্রান্তকে আমরা সামনের অংশ বা ফ্রন্ট (front) অথবা হেড (head - মাথা) বলতে পারি। বেশ গোলমেলে ব্যাপার-স্যাপার, তাই না? দুশ্চিন্তা করার কোন কারণ নেই। একটা গল্প বললেই বিষয়টা পরিষ্কার হয়ে যাবে।

 

একটা কিউয়ের একদম শুরুতে যেই ডেটা থাকে তাকে বলা হয় front. স্বাভাবিক ভাবেই শেষের জনকে বলা হয় back/rear. তো ফ্রন্ট থেকে কোন একজন কাস্টমারকে সার্ভিস দেয়ার জন্য ডাকলে এই ডাকার প্রসেসটাকে বলা হয় dequeue. কিউয়ের বৈশিষ্ট্য হচ্ছে dequeue করে front এর ডেটাকে প্রসেস করে তাকে কিউ থেকে বের করে দিবে (Stack এর pop এর মত)। b কাউন্টার খালি হলে সে আবার কিউয়ের front-কে ডাকবে (dequeue)। তাকে সার্ভিস দিয়ে বের করে দিবে। Queue এর দুইটা অপারেশন উল্লেখ করা যেতে পারে। Dequeue এর মধ্যে ফ্রন্ট ডেটাকে অ্যাক্সেস করা ও সেটাকে রিমুভ করা, উভয় অপারেশনই হ্যান্ডেল করা হচ্ছে। তুমি চাইলে কোডে ৩টা ফাংশন রাখতে পারো ৩ টা কাজের জন্য।

• Enqueue – কিউয়ের back এ কোন data অ্যাড করা
• Dequeue – কিউয়ের front এর data-কে প্রসেস করে কিউ থেকে বের করে দেয়া

Enqueue/Push Operation of Queue Data Structure

C++ এর STL ব্যবহার করে সহজেই কিউয়ের অপারেশনগুলো করা যায়। স্ট্যাকের মত কিউয়ের হেডার ফাইল অ্যাড করে কাজ করতে হবে।

1.0  Enqueue/Push in Queue Data Structure in C++ STL

#include<queue> using namespace std;   int main(){       queue<int> myQueue;       myQueue.push(419);     myQueue.push(420);   }

যদি সি ল্যাঙ্গুয়েজ ব্যবহার করে করতে চাই তাহলে এই কাজের জন্য একটা ফাংশন লিখে ফেলিঃ

1.1 Enqueue/Push operation of Queue Data Structure in C

 

#define queueSize 100 int myQueue[queueSize], front = 0, rear = -1, dataCounter = 0; //Global data void enqueue(int value) {     if(rear==queueSize)         printf("Queue is Full. Cannot push any data");     else     {         myQueue[++rear] = value;         dataCounter++;     } }

অ্যারে দিয়ে কিউ ইমপ্লিমেন্ট করার সময় দুইটা data pointer রাখা হয়। front ভেরিয়েবল দিয়ে কিউয়ের ফ্রন্ট ভ্যালুকে অ্যাক্সেস করা হয়। আর rear ভেরিয়েবল দিয়ে কিউয়ের back বা শেষের ভেরিয়েবলের পজিশন ম্যানেজ করা হয়। স্ট্যাকের ক্ষেত্রে দুইটা ভেরিয়েবল দরকার হয় নাই। কারণ একই পথে স্ট্যাকের ডেটা ঢুকতো ও বের হতো। তাই সেখানে শুধু top নামের একটা ভেরিয়েবল দিয়েই কাজ সেরে ফেলা গেছে। কিন্তু কিউয়ের পথ কিন্তু দুইটা। ডেটা insert হয় কিউয়ের ব্যাক সাইড দিয়ে, আর ডেটা প্রসেসিং/রিমুভ হয় সামনের দিক দিয়ে।

ফাংশনের ভিতরে প্রথমেই চেক করা হয়েছে rear বা শেষের ভ্যালুকে এক্সেস করার পয়েন্টারের মান কিউয়ের সাইজের সমান হয়ে গিয়েছে কিনা। যদি সমান হয়ে যায় তার মানে হচ্ছে কিউতে আর কোন জায়গা নাই। Overflow হয়ে গিয়েছে। কিন্তু যদি কিউতে ফাঁকা জায়গা থাকে তাহলে ++rear করে value-টা কিউতে ঢুকিয়ে দেয়া হচ্ছে। rear এর মান গ্লোবাল্যি -1 দেয়া হয়েছিল। অ্যারেতে -1 নামের কোন ইন্ডেক্স নাই, ইন্ডেক্স শুরু হয় ০ থেকে। তাই preincrement operator (++rear) ব্যবহার করা হয়েছে। একই সাথে dataCounter এর মানও ১ বাড়িয়ে দেয়া হয়েছে। এটা দিয়ে আমরা হিসাব রাখব এই কিউতে কতগুলো ডেটা আছে।

Dequeue/Pop Operation of Queue Data Structure

Dequeue এর কাজ আগেই বলা হয়ে গেছে। কিউয়ের front ডেটাকে প্রসেসিং/রিমুভ করার অপারেশন এটা। সি++ এর কোড হতে পারে এরকমঃ

1.2 Dequeue operation of Queue Data Structure in C++

if(myQueue.empty() != true) {     int frontValue = myQueue.front(); //return front value     myQueue.pop(); //remove front value from Queue   }

উপরের কোডটা সি দিয়ে করা যায় এভাবেঃ

1.3 Dequeue of Queue Data Structure in C

void dequeue() {     if(front==queueSize)          printf("Queue is Empty!");     else     {          printf("%d\n", myQueue[front++];          dataCounter--;     }   }

প্রথমে চেক করা হয়েছে কিউটা খালি কিনা। খালি হলে তো আর কোন ডেটাকে প্রসেস করা বা সেটাকে রিমুভ করা যাবে না। যদি খালি না হয়ে থাকে তাহলে mySqueue এর front-তম ইন্ডেক্সের মানটা প্রিন্ট করা হয়েছে। এরপর front এর মান বাড়িয়ে দেয়া হয়েছে। পরে আবারো dequeue() কল করা হলে অ্যারের পরের ইন্ডেক্সের মান প্রিন্ট করা হবে। অ্যারেতে ভ্যালু থেকেই যাচ্ছে, কিন্তু front ভেরিয়েবলের মাধ্যমে কিউয়ের শুরুর পয়েন্টটা আমরা কন্ট্রোল করছি। front++ করার মানেই আমরা ধরে নিচ্ছি ফ্রন্টের ভ্যালুটা কিউ থেকে বের করে দেয়া হয়েছে। আর যেহেতু একটা ডেটা কমে গেল তাই dataCounter এর মানও এক কমিয়ে দেয়া হয়েছে।

FIFO – First in First Out এই মূলনীতির উপর ভিত্তি করে কিউ ডেটা স্ট্রাকচার কাজ করে। তোমরা জানো যে একটা কিউতে নতুন কোন ডেটা ইনসার্ট করতে হলে কিউয়ের শেষে ইনসার্ট করতে হয়। আর কোন ডেটা বের করে নিতে হলে বা প্রসেস করতে হলে কিউয়ের শুরু থেকে বের করতে হয়।

Double-end Queue এর ক্ষেত্রে উপরের কাজগুলো করা যায়, সাথে আরো বাড়তি কিছু সুবিধা পাওয়া যায়। নাম দেখেই বুঝা যাচ্ছে এই কিউয়ের বৈশিষ্ট্য। Deque ব্যবহার করে তুমি কিউয়ের শুরু ও শেষ দুই দিকেই ডেটা ইনসার্ট করতে পারবা এবং দুই দিক দিয়েই ডেটা বের করতে পারবা। C++ এর STL ব্যবহার করে খুব সহজে deque ইমপ্লিমেন্ট করা যায়। চাইলে একটু খাটাখাটনি করে সাধারণ অ্যারে দিয়েও এটা ইমপ্লিমেন্ট করতে পারো।

Deque এর কয়েকটা সাধারণ ফাংশনালিটি দেখব এই পোস্টেঃ

1. push_front() – কিউয়ের শুরুতে ডেটা ইনসার্ট করতে
2. push_back() – কিয়ের শেষে ডেটা ইনসার্ট করতে
3. pop_front() – কিউয়ের সামনে থেকে ডেটা pop করতে
4. pop_back() – কিউয়ের শেষ থেকে ডেটা pop করতে
5. front() – কিউয়ের সামনের ডেটা অ্যাক্সেস করতে
6. back() – কিউয়ের শেষের ডেটা অ্যাক্সেস করতে
7. clear() – কিউয়ের সকল ডেটা মুছে ফেলতে

একটা প্রোগ্রাম লিখব যাতে উপরের ক্রম অনুসারে ডিকিউ দিয়ে এই অপারেশনগুলো সম্পন্ন করা যায়। অর্থাৎ, 1 ইনপুট দিলে push_front() কাজ করবে। 4 ইনপুট দিলে pop_back() করবে। অনুরূপ ভাবে 7 ইনপুট দিলে সকল ডেটা মুছে ফেলা হবে।

কাজের সুবিধার্তে আরো দুইটা নতুন অপশন যোগ করি। 8 ইনপুট দিলে পুরো কিউটার আউটপুট দেখাবে। 9 ইনপুট দিলে প্রোগ্রাম exit করবে।

Deque - Double-ended Queue in C++

 

#include<bits/stdc++.h>   using namespace std;   int main() {     int choise, data;     deque<int> myDeque;     deque<int>::iterator it;       while(true)     {         cout<<"\n\nChoose anyone:\n";         cout<<"1. push_front()\t2. push_back()\t3. pop_front()\t 4. pop_back()\n";         cout<<"5. front()\t 6. back()\t 7. clear()\t 8. show all elements\t 9. exit\n\n";           cin>>choise;         if(choise==1)         {             cout<<"Enter an integer to push it front\n";             cin>>data;             myDeque.push_front(data);         }         else if(choise==2)         {             cout<<"Enter an integer to push it back\n";             cin>>data;             myDeque.push_back(data);         }         else if(choise==3)         {             if(!myDeque.empty())                 myDeque.pop_front();             else                 cout<<"Deque is empty!\n";         }         else if(choise==4)         {             if(!myDeque.empty())                 myDeque.pop_back();             else                 cout<<"Deque is empty!\n";         }         else if(choise==5)         {             cout<<"Top front element is: "<<myDeque.front();         }         else if(choise==6)         {             cout<<"Top back element is: "<<myDeque.back();         }         else if(choise==7)         {             myDeque.clear();             cout<<"Deque is clear now!\n";         }         else if(choise==8)         {             if(!myDeque.empty())             {                 cout<<endl<<"Full Deque is:\n";                 for(it=myDeque.begin(); it != myDeque.end(); it++)                     cout<<*it<<endl;                 cout<<endl;             }             else                 cout<<"Deque is empty!\n";           }         else if(choise==9)             break;         else             cout<<"Invalid input!\n";       }         return 0; }

কিউয়ের আগের পর্ব পড়ে বুঝে থাকলে এই পর্ব বুঝতে কোনই সমস্যা হবার কথা নয়। তাই প্রতিটা মেথডের বিস্তারিত আলোচনা আর করলাম না। আশা করি ডিকিউ (আসলে উচ্চারণটা হবে ডেক্‌) বুঝা হয়ে গেছে। কোথাও কনফিউশন থাকলে কমেন্ট করতে ভুলো না। ও হ্যাঁ! আরেকটা কথা… deque-কে অনেক সময় head-tail linked list-ও বলা হয়ে থাকে।

 

 

 

লিঙ্ক লিস্ট : লিঙ্ক লিস্ট অত্যন্ত গুরুত্বপূর্ণ ডাটা স্ট্রাকচার । লিঙ্ক লিস্ট অনেকগুল node এর সমন্বয়ে গঠিত। যেখানে প্রতিটি node কিছু সংখ্যক ডাটা এবং পয়েন্টার নিয়ে গঠিত হয় । পয়েন্টার এর কাজ হল পরবর্তী node কে পয়েন্ট করা ।
লিঙ্ক লিস্ট কয়েক প্রকারের হতে পারে । যেমন –
1. Singly linked list
2. Doubly linked list
3. Multiply linked list
4. Circular list
আমরা এখানে Singly linked list নিয়ে আলোচনা করব ।

লিঙ্ক লিস্ট ব্যবহারের সুবিধা –

লিঙ্ক লিস্ট ব্যবহার করে আমরা লিস্ট এর যে কোন জায়গায় খুব সহজেই ডাটা insert অথবা delete করতে পারি । জেটা array তে করা খুবই সময় সাপেক্ষ এবং অনেক জটিল ও বটে ।
ডায়নামিক মেমোরী এ্যালোকেশনের ক্ষেত্রে লিঙ্ক লিস্টই হচ্ছে সবচেয়ে শক্তিশালী উপাদান। অন্যান্য ডাটা স্ট্রাকচার যেমন স্ট্যাক , কিউ, ট্রি, গ্রাফ ইত্যাদি তৈরী করতেও লিঙ্ক লিস্ট ব্যবহার করা হয়।

যেভাবে শুরু করব :

লিঙ্ক লিস্ট শুরু করার আগে প্রথম কাজ হবে স্ট্রাকচার এবং পয়েন্টার এর ব্যবহার পুরাপুরিভাবে শিখে নেওয়া । স্ট্রাকচার আমরা তৈরি করি নতুন ডাটা টাইপ প্রস্তুত করার জন্য । যেরকম int a , float b ।এখানে int এবং float হল ডাটা টাইপ । একটা উদাহরন দিয়ে দেখি আমরা –

#include <cstdio>
struct node {
int info ;
double data ;
};

int main(void)
{
struct node a , *p ;
a.info = 10 ;
a.data = 10.34 ;

p->info = 100 ;
p->data = 100.34;

printf (“%d %lf\n”,a.info,a.data);
printf (“%d %lf\n”,p->info,p->data);
return 0 ;
}

 

উপরিউক্ত উদাহরণে আমরা a এবং *p নামে দুইটা node টাইপ এর ডাটা তৈরি করেছি । node ডাটা টাইপ একটা ইন্টেজার এবং একটা ফ্ল্যট নিয়ে তৈরি হয়েছে । পয়েন্টার নিয়ে কাজ করার সময় আমরা ডট “.” চিহ্ন এর পরিবর্তে “->” একটা তীর চিহ্ন ব্যাবহার করেছি ।

যেভাবে লিঙ্ক লিস্ট তৈরি করব :

Array এর মত লিঙ্ক লিস্টও ক্ষুদ্র ক্ষুদ্র মেমরি ব্লক এর সমন্বয়ে গঠিত । লিঙ্ক লিস্ট এর সুবিধা হল এখানে এক একটা মেমরি আলাদা আলাদা করে ফেলা যায় । প্রতিটি মেমরি ব্লকে দুইটা ফিল্ড (field ) থাকে । একটা ফিল্ড এ যে কোন ডাটা রাখার ব্যবস্থা থাকে এবং অন্য ফিল্ড এ পরের মেমরি ব্লককে রেফারেন্স করার জন্য থাকে একটা পয়েন্টার (pointer) ।
এই দুই ফিল্ড নিয়ে গঠিত মেমরি ব্লক’কে বলা হয় “ linked list element” অথবা “node”। এরকম ফিল্ড তৈরি করতে আমরা Structure এর সাহায্য নিব । Structure দিয়ে এমন একটা ডাটা টাইপ তৈরি করব যেখানে কিছু ডাটা থাকতে পারবে এবং সাথে থাকবে একটা পয়েন্টার । এটুকু তৈরি করা শিখে ফেলি …
struct node {
int info ;
struct node *link;
};

এখানে আমরা একটা node তৈরি করেছি যেখানে একটা int টাইপ ডাটা রাখার ব্যাবস্থা আছে ( int info ) , সাথে আছে পরবর্তী node কে পয়েন্ট করার জন্য একটা পয়েন্টার (struct node *link) । খেয়াল কর , আমরা node ডাটা টাইপ এর পয়েন্টার ডিক্লেয়ার করেছি । কেন ? কারণটা সহজ । int টাইপ এর ডাটা পয়েন্ট করার জন্য আমরা int টাইপ এর পয়েন্টার ইউজ করি , float টাইপ এর জন্য float টাইপ পয়েন্টার , তেমনি পরবর্তী node টাইপ এর মেমরি পয়েন্ট করার জন্য আমাদের লাগবে node টাইপ এর পয়েন্টার।

পরবর্তী নতুন মেমরি তৈরি করতে আমরা malloc () ফাংশনটার সাহায্য নিব । এটা এমন একটা ফাংশন , যে ক্ষুদ্র ক্ষুদ্র মেমরি ব্লক তৈরি করতে পারে । এই কাজটুকুর জন্য …
struct node *tmp ;
tmp = (struct node*) malloc (sizeof(struct node)) ;

এখানে tmp হল এমন একটা পয়েন্টার জেটা নতুন তৈরি হওয়া একটা মেমরি কে পয়েন্ট বা রেফারেন্স করছে । অন্য কথায় tmp হল নতুন মেমরি ।

এক নজরে পুরো কোড :

#include <cstdio>

#include <cstdlib>

struct node {
int info ;
struct node *link;
}*start = NULL;

void print (struct node *q) {
while (q->link!=NULL) {
printf (“%d “,q->info);
q = q->link ;
}
printf (“%d”,q->info);
}

int main (void) {

int n , l ,item ;
struct node *tmp,*q;
printf(“Enter the number of elements in the list : “);

scanf(“%d”, &n);

for(l=0; l<n; l++) {
printf(“Enter element %d : “,l+1);
scanf(“%d”,&item); tmp = (struct node*) malloc (sizeof(struct node)) ;
tmp->info=item;
tmp->link=NULL;

if(start==NULL)
start=tmp;
else {
q=start;
while(q->link!=NULL)
q=q->link;
q->link=tmp;
}
}
print (start) ;
return 0 ;
}

যেভাবে লিঙ্ক গঠন করব :

প্রতিটি লিঙ্ক লিস্ট এ একটা “head pointer” থাকে । জেটা লিঙ্ক লিস্ট এর প্রথম node কে পয়েন্ট করে থাকে । লিস্ট এর প্রথম node এর পয়েন্টার দ্বিতীয় node কে পয়েন্ট করবে , দ্বিতীয় node এর পয়েন্টার তৃতীয় node কে পয়েন্ট করবে , এভাবে চলতে থাকবে এবং শেষ node এর পয়েন্টার কাউকে পয়েন্ট করবে না । এখানে আমরা একটা NULL সেট করে রাখব ( কোন node পয়েন্টার এ NULL পাওয়া গেলে আমরা বুঝব ,হুম , আমরা লিস্ট এর শেষ প্রান্তে চলে এসেছি  ) । চিত্র :

কোড এ লক্ষ্য করি …
struct node {
int info ;
struct node *link;
}*start = NULL;

এখানে *start পয়েন্টার আমরা “head pointer” হিসেবে ইউজ করেছি ।

মেইন মেথড এর ভিতরে চলে আসি …

tmp = (struct node*) malloc (sizeof(struct node)) ;
tmp->info=item;
tmp->link=NULL;

if(start==NULL)
start=tmp;

এখানে আমরা লিস্ট এর প্রথম node (tmp) তৈরি করে ফেলেছি । tmp node এর ভিতরে ইউজার এর কাছ থেকে নেওয়া ডাটা রাখা হয়েছে এবং সাথে সাথে node এর পয়েন্টার এ NULL সেট করা হয়েছে ।
 ) চিত্র :Jপরবর্তীতে head node (*start) কে লিঙ্ক করা হয়েছে নতুন tmp node এর সাথে । (খেয়াল কর , head node/*start এবং new node/*tmp এখন একই এড্রেসকে রেফারেন্স করছে

দ্বিতীয় node এর ক্ষেত্রে,
লুপ ঘুরে আবার নতুন node বা দ্বিতীয় node তৈরি হবে আগের মতই । নতুন node আবারো tmp নামে চিহ্নিত করা হল । যেহেতু head node এর লিঙ্ক করার কাজ শেষ , সেহেতু এবার …
else {
1. q=start;
2. while(q->link!=NULL)
q=q->link;
3. q->link=tmp;
}

এখানে,
statement no 1 :
q = start ;
কাজের সুবিধার্থে ১ম নোড কে নতুন একটা পয়েন্টার q  দ্বারা পয়েন্ট করা হল , অর্থাৎ , q হল প্রথম node .
statement no 2 :
while(q->link!=NULL)
q=q->link;
পরবর্তী নোড এ যাবার জন্য আমরা while loop এর q= q->link ; ইউজ করছি ।
statement no 3 :
q->link=tmp;
নতুন নোড এর সাথে পূর্ববর্তী নোড এর লিঙ্ক করছি  ( এক্ষেত্রে , ২য় নোড এর সাথে ১ম নোড এর লিঙ্ক হইছে ) ।  খেয়াল কর , q->link মানে হল q নোডের পয়েন্টার । q->link=tmp মানে হল q node এর পয়েন্টার tmp node কে পয়েন্ট করছে । চিত্র :

 তৃতীয় node এর ক্ষেত্রে ,

while লুপ এর q=q->link দিয়ে সর্বশেষ node এ যাব , এরপর নতুন node এর সাথে সর্বশেষ node এর লিঙ্ক গঠন করব । এভাবে চলতে থাকবে এবং লিঙ্ক লিস্ট তৈরি হয়ে যাবে :D।
আর ,সবগুল নোডের এলিমেন্ট প্রিন্ট করাটা আশা করি নিজেরাই শিখে নিবে …

পুনশ্চ :

 

ট্রি ডেটা স্ট্রাকচার

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

Windows operating system file structure

উপরের চিত্রটা দেখ। কী চেনা চেনা লাগে? ধরো একদম উপরের বক্সটা তোমার পিসির “My Computer”. পিসি ওপেন করেই তুমি এই আইকনে ডাবল ক্লিক করো। এরপর C, D, E ও F নামের চারটা ড্রাইভ দেখতে পাও। একেকটা ড্রাইভের মধ্যে একেক টাইপের ডেটা আছে। যেমন D drive এ দেখা যাচ্ছে চারটা ফোল্ডার। টিউটোরিয়াল নামের ফোল্ডারের ভিতরে তিনটা ফোল্ডার আছে এবং একটা ফাইল আছে। java নামক ফোল্ডারে ডাবল ক্লিক করলে এই ফোল্ডারটা ওপেন হবে। ভিতরে হয়ত আরো ফোল্ডার বা ফাইল দেখতে পাওয়া যাবে। কিন্তু Java.pdf নামক যেই ফাইলটা আছে সেটাতে ডাবল ক্লিক করলে কী ঘটবে? এটা যেহেতু ফাইল তাই এটা নির্দিষ্ট অ্যাপ্লিকেশনের মাধ্যমে ওপেন করা যাবে। এটা ওপেন হয়ে কিন্তু আরো কোনো ফোল্ডার/ফাইল পাওয়ার কোনো সম্ভাবনা নাই। অর্থাৎ ফাইলগুলোকে ধরা যায় একেকটা end point হিসেবে। এর পরে আর যাওয়ার রাস্তা নাই।

Fig: 1. Binary Tree. Credit: Wikipedia

এতক্ষণ আমরা কথা বললাম My Computer>D Drive>Tutorial এই লোকেশনের ফাইল/ফোল্ডার নিয়ে। একই রকম ভাবে অন্যান্য সকল ফোল্ডারের ভিতরেই এরকম ফাইল/ফোল্ডার পাওয়া যাবে। এই ফাইল ফোল্ডার একটার পরে একটা কিভাবে সাজানো আছে এটা বুঝে গিয়ে থাকলে তোমার ট্রি ডেটা স্ট্রাকচারের ব্যাসিক বুঝা হয়ে গেছে।

এইবার এক
টু বইয়ের ভাষায় কথা বলা যাক। ট্রি হচ্ছে কিছু নোডের সমন্বয়ে গঠিত একটা নন-লিনিয়ার এবং Hierarchical Data Structure. যেখানে নোডগুলো একে অপরের সাথে যুক্ত থাকবে কিন্তু কোনো সাইকেল তৈরি করবে না। যেমন পাশের ছবিটি (Fig:1. Binary Tree) একটি ট্রি ডেটা স্ট্রাকচারের উদাহরণ। যেখানে ৯ টি নোড যুক্ত হয়ে একটা স্ট্রাকচার তৈরি করেছে এবং নোডগুলোর মধ্যে কোনো সাইকেল তৈরি হয় নি।

 

আরো কয়েকটি উদাহরণ দেখানো হলোঃ

Not a tree: cycle B→C→E→D→B. B has more than one parent (inbound edge). 

Not a tree: undirected cycle 1-2-4-3. 4 has more than one parent (inbound edge). 

Not a tree: two non-connected parts, A→B and C→D→E. There is more than one 

Not a tree: cycle A→A. A is the root but it also has a parent. Credit: Wikipedia

 

  

 

Each linear list is trivially a tree. 

 বাস্তবে একটা গাছ বা ট্রি এর মূল বা রুট থাকে নিচে আর শাখা-প্রশাখা, পাতা থাকে উপরের দিকে। কিন্তু কম্পিউটার সায়েন্সের ক্ষেত্রে ব্যাপারটা উল্টা! :P. একদম শুরুর Tree এর উদাহরনের দিকে তাকাও। যেই ছবিটা দেয়া আছে সেটাকে ১৮০ ডিগ্রি অ্যাঙ্গেলে উল্টায় দিলে কিন্তু দেখতে সত্যিকারের গাছের মতই লাগবে। ছবির একদম উপরে My Computer হচ্ছে এই গাছের বা ট্রি এর root (মূল)। Java.pdf হচ্ছে এই ট্রি এর অন্যতম একটা পাতা (leaf). এরকম আরো অনেক পাতা থাকতে পারে এই ট্রি এর মধ্যে। একটা ট্রি এর কোন অংশকে কী বলা হয় সেই বিষয়গুলো এখন দেখব।

Root: একটা Tree এর একদম top node-কে বলা হয় রুট। রুট নোডকে অন্য কোন নোড পয়েন্ট করে না।

Child: একটা ট্রিতে রুট ছাড়া বাকি যেই নোডগুলো থাকে সেগুলো child.

Parent: কোনো একটা নোডের যদি এক বা একাধিক child থাকে তাহলে তাকে বলা হয় parent.

Siblings: যেই নোডগুলোর parent একই তাদেরকে বলে siblings (আপন মায়ের পেটের ভাই বোন আর কি! 

Edge: যেই কানেকশন বা লিংকের মাধ্যমে একটা নোড আরেকটা নোডের সাথে যুক্ত থাকে।

Leaf: যেই নোডের কোনো child নাই। একে external node-ও বলা হয়।

Branch: যেই নোডের অন্তত একটা child আছে সেটাই একটা branch.

Degree: কোনো একটা নোডের sub-tree এর সংখ্যাই ঐ নোডের degree.

Path: একটা নোড থেকে আরেকটা নোডে পৌঁছানোর জন্য edge এর মাধ্যমে এক বা একাধিক নোডের সিকোয়েন্সই হচ্ছে path.

Height of Node: কোনো একটা নোড থেকে একটা leaf-এ পৌঁছাতে সব চেয়ে লম্বা যে দূরত্ব অতিক্রম করতে হয়, অর্থাৎ একটা নোড থেকে সবচেয়ে দূরের leaf-এ পৌঁছাতে অতিক্রম করা edge এর সংখ্যাই হচ্ছে ঐ নোডের height.

Height of Tree: রুটের height-ই কোনো ট্রি এর height. অর্থাৎ রুট থেকে সব চেয়ে লম্বা পথে leaf এ পৌঁছাতে যে কয়টি edge পার হতে হয় সেটিই height of tree.

Depth: রুট থেকে কোনো একটা নোডে পৌঁছানোর edge সংখ্যাই ঐ নোডের depth.

Level: কোনো একটা নোডের Level হচ্ছে রুট থেকে ঐ নোডে পৌঁছানোর edge এর সংখ্যার চেয়ে ১ বেশি। সংক্ষেপে, level = 1 + depth.

Ancestor: যদি A নোড থেকে B নোডে যাওয়া যায় তাহলে A হচ্ছে B এর ancestor. যদি A→B→C→D যাওয়া যায়। তাহলে D এর ancestor হচ্ছে A, B ও C.

Descendant: যদি A নোড থেকে B নোডে যাওয়া যায় তাহলে B হচ্ছে A এর descendant. যদি A→B→C→D যাওয়া যায়। তাহলে D হচ্ছে A, B ও C এর descendant.

Some properties of Tree

One way direction: ট্রি এর রুট থেকে যখন অন্যান্য নোডে traverse করা হবে সেটি হবে এক দিকে। অর্থাৎ root থেকে leaf এর দিকে। কিন্তু leaf থেকে root এর দিকে কোনো direction বা link থাকবে না।

No cycle: একটা ট্রি এর মধ্যকার নোডগুলো কেবল মাত্র parent-child relationship এর মত করে যুক্ত থাকবে। পরস্পরের সাথে এমন ভাবে যুক্ত হওয়া যাবে না যেখানে নোডগুলোর মধ্যে কোনো loop বা cycle তৈরি হয়।

All nodes are must be connected: কোনো একটা ট্রি এর এ কোনো দুটি নোড নিজেদের মধ্যে একটা মাত্র লিংকের মাধ্যমে যুক্ত থাকতে পারবে। যদি এক গুচ্ছ নোড আরেক গুচ্ছ নোডের সাথে কোনো লিংক দ্বারা যুক্ত না থাকে তাহলে উভয় গুচ্ছ নোডকে একত্রে ট্রি বলা যাবে না। গুচ্ছগুলো যদি আলাদা আলাদা ভাবে ট্রি এর বৈশিষ্ট্য পূরণ করে সেক্ষেত্রে সবগুলো আলাদা আলাদা ট্রি হিসেবে বিবেচিত হবে।

Every child must have only one parent: root node ব্যতীত অন্যান্য সকল নোডের কেবল মাত্র একটি parent node থাকবে। অর্থাৎ একাধিক নোড কোনো একটা নোডকে পয়েন্ট করতে পারবে না বা কোনো child এর একাধিক parent থাকতে পারবে না। শুধুমাত্র root node এর কোনো parent node থাকবে না।

Recursive Data Structure: ট্রি-কে রিকার্সিভ ডেটা স্ট্রাকচারও বলা হয়। কারণ হচ্ছে রুটের উপাদানগুলো রিকার্সিভলি সাজানো থাকে। যেমন ধরো, T একটা ট্রি যার রুট হচ্ছে R. এই রুটের দুইটা child আছে। এই দুইটা child এর প্রত্যেকের আবার আরো ২ টা করে child আছে। তাহলে কী দাঁড়াচ্ছে? রুট R এর অধীনে আছে দুইটা ট্রি, t1, t2. ধরতে পারো এদের রুট r1, r2. দেখলা ট্রি এর ভিতরে ট্রি, রুটের ভিতরে রুট? এই রুটগুলোর অধীনে ওদের বাচ্চাকাচ্চা আছে। এরপর নাতিপুতি আছে। ট্রি এর ভিতর ট্রাভার্স করলে শেষ পর্যায়ে একটা নোডই পাওয়া যাবে। এই ট্রি এর ভিতর ট্রি, নোডের ভিতর নোড এই বৈশিষ্ট্যের জন্যেই একে বলা হয় রিকার্সিভ ডাটা স্ট্রাকচার। ডেটাগুলো recursively একটার ভিতরে আরেকটা সাজানো থাকে।

Number of Edges is N-1: কোনো একটা ট্রিতে N সংখ্যক নোড থাকলে তাতে অবশ্যই N-1 সংখ্যক edge থাকবে। যেহেতু কোনো নোডের একাধিক parent হতে পারে না তাই এই রুলসটা সকল ট্রি এর জন্য সত্য হবে।

 

Some applications of Tree

শুধু natural hierarchical data স্টোর করার জন্যেই ট্রি ব্যবহার করা হয় না। আমাদের প্রতিদিন ব্যবহার করা অসংখ্য সফটওয়্যারে এই ডেটা স্ট্রাকচার ব্যবহার করা হয়। তবে হায়ারারকিক্যাল ডেটার উদাহরণ সবচেয়ে কমন ও সহজে বোধগম্য।

Natural Hierarchical data বলতে বুঝায় এমন কিছু ডেটা যেগুলো স্বাভাবিক ভাবেই parent-child relationship অনুযায়ী সাজানো থাকবে। যেমন ধরো তোমার বংশ পরম্পরা বা পূর্ব-পুরুষদের নামের তালিকা যদি করতে চাও। বা সেই তালিকায় খুব দ্রুত সার্চ, ইনসার্ট, আপডেটের মত কাজগুলো করতে চাও তাহলে ডেটাগুলো প্রসেস করার সবচেয়ে ভাল উপায় হচ্ছে ট্রি ডেটা স্ট্রাকচারে ফেলা। ধরো তোমার ৫ পুরুষ আগের থেকে হিসাব শুরু করতে চাও। তাহলে তোমার আগের ৫ম পুরুষকে রুট ধরতে পার। তার ধরো ৭ ছেলেমেয়ে ছিল। তাদেরকে রুটের চাইল্ড বানায় দাও। এরপর পরের প্রজন্ম, তার পরের প্রজন্ম এমন করতে করতে তোমার পর্যন্ত আসবে। যদি তোমার এখন পর্যন্ত ছেলেপুলে না থেকে থাকে তাহলে তুমি হবে এই ট্রি এর একটা leaf. তোমার ছেলেপুলে হবার পর তুমি তোমার বাবার চাইল্ড ঠিকই থাকবা, আবার তোমার চাইল্ডের প্যারেন্টও হবা।

একই ভাবে কোনো প্রতিষ্ঠানের CEO, CTO, MD, Manager, worker ইত্যাদি ম্যান পাওয়ারদেরকে tree structure এ সাজানো যায়।

ট্রি এর অন্যান্য কমন ও গুরুত্বপূর্ণ অ্যাপ্লিকেশনগুলো নিচে আলোচনা করা হল।

Folders in Operating System: উইন্ডোজ বা লিনাক্স, উভয় ক্ষেত্রেই ফোল্ডারগুলো সাজানো থাকে ট্রি স্ট্রাকচারে। তুমি হয়ত বাচ্চা কালে পিসি স্লো হয়ে গেলে কমান্ড লাইনে tree কমান্ড দিতা। ঘ্যাচ্চর ঘ্যাচ্চর করে ৩-৪ বার এই কমান্ড দিলে পিসি ফাস্ট হয়, এই মহান তথ্য কারো না কারো থেকে অবশ্যই শুনে থাকবার কথা। আসলে এই কমান্ড দিলে পিসি ফাস্ট হবার কোনো কারণ নাই। এই কমান্ডের কাজ হচ্ছে তোমার পিসির সব ড্রাইভ, ফোল্ডার ইত্যাদি যেই ট্রি স্ট্রাকচারে সাজানো আছে সেটা command prompt এ শো করা।

Windows File System Tree Structure

Linux File System Tree Structure

পিসি ফাস্ট করার আরেকটা মহান ট্রিক্স হল বার বার Refresh করা! বাচ্চা কাল থেকে দেখে আসতেছি এই রিফ্রেশ আর ট্রির কারিশমা! তুমি তো এখন জানোই রিফ্রেশ করার ব্যাপারটাও বোগাস! রিফ্রেশ করলে পিসি “ফ্রেশ” হয় না বরং তুমি যেই ভিউটা দেখতে পাচ্ছ সেটা রিসেট হয়। এগুলার সাথে পিসি ফাস্ট হবার কোনো সম্পর্ক নাই। ISP এর লোকেরা বাসায় আসলে অভ্যাস বশত বার বার রিফ্রেশ করতে গিয়ে রিফ্রেশ অপশন আর খুঁজে পায় না। লিনাক্সে রিফ্রেশ অপশন পাইবে কৈ? 

HTML Document Object Model (DOM): তুমি যদি একদম ব্যাসিক HTML সম্পর্কে জেনে থাকো তাহলে খুব সহজেই নিচের চিত্র দেখে ব্যাপারটা বুঝে যাবা। যত ওয়েব পেজ আছে সবগুলোর ডেটাগুলো এরকম একটা ট্রি এর মাধ্যমেই মেমরি স্টোর করা হয়।

HTML Document Object Model (DOM)

Network Routing: তোমার যদি নেটওয়ার্কিং এর ব্যাপারে আগ্রহ থাকে বা ঘাটাঘাটি করে থাকো তাহলে জানার কথা যে ডেটা যখন একটা মেশিন থেকে অন্য মেশিনে যায় তখন মাঝে অনেকগুলো রাউটারের মধ্যে দিয়ে যায়। তোমার পিসি থেকে আমার ব্লগে হিট করেছ। আমার ব্লগ ধরো হোস্ট করা আছে আমেরিকার কোনো সার্ভারে। এখান থেকে সার্ভার পর্যন্ত ডেটাগুলো যাওয়ার সময় মাঝে অনেকগুলো রাউটার পরে। কোন রাউটারের পর কোন রাউটারের কাছে ডেটা নিয়ে যেতে হবে সেই পথ বাতলে দেয়ার জন্য আছে Network Routing Algorithm. এখানেও রয়েছে ট্রি ডেটা স্ট্রাকচারের কাজ।

Network Routing

Syntax Tree in Compiler: কম্পাইলার যখন আমাদের প্রোগ্রামকে কম্পাইল করে তখন প্রতিটা expression কে syntax tree ফরমেটে কনভার্ট করে।

Syntax Tree in Compiler

Auto Correcter and Spell Checker: অটো কারেকশনের কাজটা কিন্তু একদম ইন্সট্যান্ট হয়। এজন্য ডেটাগুলো বা শব্দগুলো এমন ফরমেটে থাকা জরুরি যেখান থেকে খুব দ্রুত সার্চ করা যায় বা ভুল ও শুদ্ধ বানানের মাঝের পার্থক্যটা দ্রুত ধরে ফেলা যায়। তাই শব্দগুলোকে ট্রিতে সাজিয়ে রাখা হয়।

Tree for Auto Correcter and Spell Checker

Next Move in AI based Games: যেসব কম্পিউটার গেমগুলো কম্পিউটারের সাথে খেলা যায় সেখানে কম-বেশি আর্টিফিশিয়াল ইন্টেলিজেন্স এর কাজ থাকে। ধরো দাবার ক্ষেত্রেই। কম্পিউটার ট্রিতে স্টোর করে রাখে পরের চালগুলো কী কী হতে পারে। সেখান থেকে অ্যানালাইসিস করে বেস্ট চালগুলো সে দিয়ে থাকে।

Tree for Next Move in AI based Games

Classification of Tree Data Structure

এই সিরিজে আপাতত প্রায় সব আলোচনা হবে বিভিন্ন ধরনের বাইনারি ট্রি নিয়ে। তাই এগুলোর জন্য ২-১ লাইনের ব্যাখ্যা দেয়ার চেষ্টা করব। বাকিগুলোর জাস্ট নাম উল্লেখ করা হবে।

Binary Tree

যেই ট্রি এর নোডগুলোতে সর্বোচ্চ দুইটি child থাকতে পারে তাকে বাইনারি ট্রি বলা হয়। নোডগুলোতে লিংকড লিস্টের মত এক বা একাধিক ডেটা স্টোর করার ফিল্ড/ভেরিয়েবল থাকতে পারে। আর থাকবে এই নোডের Left Child ও Right Child এর মেমরি অ্যাড্রেস। যার মাধ্যমে এদেরকে অ্যাক্সেস করা যায়।

Perfect Binary Tree: যেই বাইনারি ট্রি এর প্রত্যেকটি interior node এ দুটি child থাকে এবং সকল leaf এর depth ও level একই হবে।

Full Binary Tree: এমন একটা বাইনারি ট্রি যার নোডগুলোতে ০ অথবা ২ টি child থাকতে পারে। অর্থাৎ কোনো নোডে একটা child থাকলে সেটা full binary tree হবে না। একে proper binary tree, strictly binary tree বা plane binary tree-ও বলা হয়।

Complete Binary Tree: যে বাইনারি ট্রি এর শেষ লেভেল বাদে বাকি সব লেভেল সম্পূর্ণ ভাবে child দ্বারা পূর্ণ। অর্থাৎ সবগুলো নোডেই দুটি করে child আছে। এবং শেষের লেভেলের ক্ষেত্রে নোডগুলো fill up হতে হবে একদম বাম পাশ থেকে। বামের দিকের কোনো একটা নোডের জায়গা ফাঁকা রেখে ডান দিকে নোড যুক্ত করলে তাকে complete binary tree বলা যাবে না।

Binary Search Tree

Binary Search Tree এক ধরনের বাইনারি ট্রি। এই ট্রির বিশেষ একটা বৈশিষ্ট্য রয়েছে। যে কোনো নোডের left child এর মান হবে নোডটির মানের চেয়ে ছোট অথবা সমান আর right child এর মান হবে নোডের চেয়ে বড়।

বাইনারি সার্চ ট্রি বা BST. Credit: Wikipedia

চিত্র দেখলেই ব্যাপারটা ক্লিয়ার হয়ে যাবে। রুট নোডের কথাই ধরো। এর বামের সবগুলো মান রুটের মানের চেয়ে ছোট। ডানের সবগুলো নোডের মান রুটের চেয়ে বড়। একই ভাবে অন্যান্য যে কোনো parent node এর ক্ষেত্রেও এই শর্ত প্রযোজ্য।

আরো কয়েক ধরনের ট্রি আছে। যথাঃ

• AVL Tree
• Red Black Tree
• Splay Tree
• Trie
• Huffman Tree
• N-ary Tree
• Suffix Tree ইত্যাদি।

 

BST – Binary Search Tree

Binary Search Algorithm এ যেমন আমরা অ্যারের ঠিক মধ্যখানের ডেটার সাথে সার্চিং আইটেমের তুলনা করে সিদ্ধান্ত নিই যে কোন অংশকে বাদ দিব। BST এর ক্ষেত্রেও একই ধরনের একটা আইডিয়া কাজ করবে।

বাইনারি সার্চ ট্রি বা BST. Credit: Wikipedia

অ্যারের মত এই ট্রি থেকেও কোনো একটা মান সার্চ করতে O(log n) running time দরকার হবে। তাই এই ট্রি এর নাম দেয়া হয়েছে বাইনারি সার্চ ট্রি।

বাইনারি সার্চ ট্রির ডেটাগুলো একটা বিশেষ ফ্যাশনে সর্টেড হয়ে থাকে। তা হচ্ছে যে কোনো নোডের left sub-tree এর সবগুলো নোডের মান হবে ঐ নোডের চেয়ে ছোট বা সমান। আর right sub-tree এর সবগুলো নোডের মান হবে ঐ নোডের মানের চেয়ে বড়। এভাবে ডেটাগুলো সাজানো থাকলে worst case এর ক্ষেত্রেও O(log n) টাইমে যে কোনো ডেটা সার্চ করা সম্ভব।

এই সর্টেড হয়ে থাকাটা যেমন রুটের ক্ষেত্রে প্রযোজ্য, একই ভাবে অন্যান্য সকল নোডের ক্ষেত্রেও প্রযোজ্য। একটা বাইনারি সার্চ ট্রির root এর বাম পাশের সকল নোডগুলো হবে রুটের মানের চেয়ে ছোট বা সমান। ডানপাশের সকল নোডের মান হবে রুটের মানের চেয়ে বড়। একই ভাবে রুটের বাম পাশের চাইল্ডের ক্ষেত্রেও এটা সত্য হবে। এই চাইল্ডের যদি আরো চাইল্ড থাকে তাহলে দেখা যাবে এই চাইলের বামের সকল নোডগুলো এর চেয়ে ছোট বা সমান। ডানেরগুলো বড়। BST এর দারুণ একটা visualization দেখতে পারো এখান থেকে।  কয়েকটা integer value ইনসার্ট করে নিও।

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

Prerequisites: কোড করার জন্য নিচের টপিকগুলো সম্পর্কে ধারনা থাকতে হবে। তা না হলে এই পোস্টের বাকি অংশ বুঝতে সমস্যা হবে।

• Structure
• Recursion
• Linked List

Operations of Tree

অন্যান্য ডেটা স্ট্রাকচারের মত ট্রি এরও কিছু ব্যাসিক অপারেশন রয়েছে। সেগুলো হচ্ছেঃ

• Insert – নতুন কোনো child ট্রিতে যুক্ত করা
• Search – কোনো একটা item ট্রিতে সার্চ করে দেখা
• Delete – কোনো একটা child ট্রি থেকে মুছে দেয়া
• In-order Traversal – প্রথমে left sub-tree ভিজিট করবে, এরপর root, অতঃপর right sub-tree ভিজিট করবে
• Pre-order Traversal – প্রথমেই root ভিজিট হবে, এরপর যথাক্রমে left sub-tree ও right sub-tree ভিজিট হবে
• Post-order Traversal – প্রথমে left sub-tree, এরপর ভিজিট হবে right sub-tree. সবার শেষে ভিজিট হবে root.

Implementation of Binary Search Tree – BST

Create a node

এটা যেহেতু বাইনারি ট্রি তাই প্রতিটা নোডে সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। সুতরাং একটা স্ট্রাকচার বানাতে হবে যাতে ডেটা হিসাবে থাকবে একটা int type এর variable. আর child node এর মেমরি অ্যাড্রেস স্টোর করার জন্য দুটি pointer type variable.

Main function এর বাইরে globally একটা স্ট্রাকচার বানানো হল এবং root declare করা হল।

1.0  Define a structure for node of BST

typedef struct tree {     int number;     struct tree *leftChild;     struct tree *rightChild; } node; node *root=NULL;

আপাতত রুটের মান NULL করে রাখা হয়েছে। insert করার function এর ভিতরে রুটের জন্য memory allocate করা হবে।

Insert a node

ইনসার্টের জন্য একটা ফাংশন লিখা হবে। ফাংশন বডির শুরুতেই একটা temporary node এর জন্য memory allocate করা হবে। ফাংশনের প্যারামিটারে পাঠানো ভ্যালুটা নতুন নোডের number ভ্যারিয়েবলে assign করে child দুটির মান NULL করে রাখা হবে। কারণ আমরা এই নোডের ব্যাপারেই এই মুহুর্তে আগ্রহী। এর বাচ্চাকাচ্চা নেয়ার চিন্তা আপাতত নাই।

1.1  Insert a node into BST in C

void insertNode(int value) {     node *tempNode;     node *currentNode=NULL;     node *parentNode=NULL;       tempNode = (node *) malloc(sizeof(node));     tempNode->number = value;       //For the very first call     if(root==NULL)     {         root = tempNode;     }     else     {         currentNode = root;         parentNode = NULL;           while(1)         {             parentNode = currentNode;               if(value <= parentNode->number)             {                 currentNode = currentNode->leftChild;                   if(currentNode==NULL)                 {                     parentNode->leftChild = tempNode;                     return;                 }             }             else             {                 currentNode = currentNode->rightChild;                   if(currentNode==NULL)                 {                     parentNode->rightChild = tempNode;                     return;                 }             }           }     } }

এরপর চেক করা হবে রুট নোডের মান NULL কিনা। প্রথমবার যখন এই ফাংশনকে কল করা হবে তখন এই IF সত্য হবে। তখন এই নতুন বানানো নোডটাকেই রুট নোড হিসাবে assign করে দেয়া হচ্ছে। আর যদি এই IF সত্য না হয় তাহলে কিছু হিসাব নিকাশ করে নোডটা ট্রি এর সাথে জুড়ে দিতে হবে। যেহেতু কিছু শর্ত (left child এর মান ছোট বা সমান, right child এর মান বড়) মানতে হবে তাই এই নোডটাকে যে কোনো নোডের বাচ্চা হিসেবে জুড়ে দেয়া যাবে না।

ELSE block এর শুরুতে currentNode আর parentNode নামের দুটি নোডে NULL assign করা হয়েছে। আমাদের উদ্দেশ্য হচ্ছে রুট থেকে ট্রিতে ট্রাভার্স করা শুরু করব। ফাংশন প্যারামিটার হিসাবে যেই ভ্যালু পাঠানো হয়েছে সেই ভ্যালুর সাথে প্রতিটা নোডের ভ্যালুকে চেক করব। যদি দেখা যায় value এর মান ঐ নোডের number এর চেয়ে ছোট বা সমান তাহলে ঐ নোডের leftChild এ যেতে হবে। leftChild এ যাওয়ার পর এটাই কিন্তু আমাদের currentNode হয়ে যাবে। এবার আবার চেক করব value এই নতুন হওয়া currentNode এর number এর চেয়ে ছোট নাকি বড়। ছোট বা সমান হলে আবার এই নোডের leftChild এ যাব, অন্যথায় rightChild এ যাব। leftChild এর মাধ্যমে কোনো একটা নোডে যাওয়ার পর যদি দেখা যায় ঐ নোডটা (currentNode) NULL (কোডের ২৮ নাম্বার লাইন) তাহলে কী বুঝব? বুঝব parentNode আসলে একটা leaf. এই নোডের এখনো কোনো বাচ্চাকাচ্চা হয় নাই। parentNode এর leftChild এর মেমরি অ্যাড্রেস hold করছে আমাদের currentNode. এই নোড তাই এখনো NULL. আমরা যেই নতুন নোডটা বানিয়েছি সেটাই হবে parentNode নোডের বাম পাশের বাচ্চা বা leftChild. আর যদি parentNode এর rightChild এর মেমরি অ্যাড্রেস NULL পাওয়া যায় (কোডের ৩৮ নাম্বার লাইন) তখন নতুন নোডের memory address-কে পয়েন্ট করবে parentNode এর rightChild.

যতক্ষণ পর্যন্ত কোনো NULL node পাওয়া না যাবে ততক্ষণ লুপ ঘুরতে থাকবে। কোনো নোডের child এর মেমরি অ্যাড্রেস NULL পাওয়া গেলে নতুন নোডটাকে সেখানে উপরের মত করে জুড়ে দিয়ে ফাংশনের কাজ return; কীওয়ার্ডের এর মাধ্যমে শেষ করতে হবে।

এভাবে যদি কোনো একটা ট্রিতে মান ইনসার্ট হতে থাকে তাহলে সব সময় যে কোনো নোডের leftChild এর number এর মান সেই নোডের চেয়ে ছোট বা সমান হবে এবং rightChild এর number এর মান বড় হবে।

ফাংশনের কোডটা বেশ বড়। নিজে হাতে কোড না লিখে কপি-পেস্ট করে রান করলে কোডগুলো বুঝতে সমস্যা হবে। তাই পরামর্শ রইলো প্রয়োজনে দেখে দেখে নিজ হাতে টাইপ করার। এতে প্রতি লাইন বাই লাইন কোড বুঝতে সুবিধা হবে।

Search on BST

উপরের এত আয়োজন শুধু আমাদের ডেটাগুলোকে sorted রাখার জন্য। অ্যারেতে ডেটা ইনসার্ট করা সহজ। কিন্তু একটা সর্টেড অ্যারেতে ডেটা ইনসার্ট করে সেটাকে সর্ট করা কিন্তু বেশ costly. তোমাকে অ্যারের নির্দিষ্ট ইনডেক্স খুঁজে বের করতে হবে যেখানে তোমার নতুন ডেটা ইনসার্ট করতে হবে। এরপর সেই ইনডেক্স থেকে অ্যারের শেষ পর্যন্ত সবগুলো ইনডেক্সের ডেটাগুলোকে এক ইনডেক্স করে ডানে সরিয়ে ফাঁকা হওয়া ইনডেক্সে নতুন মান assign করতে হবে। Worst case এর ক্ষেত্রে (যদি অ্যারের শুরুতে কোনো মান ইনসার্ট করার দরকার হয়) শুধু সর্ট করার জন্যেই O(n) সময় লাগবে। এরপর সার্চের জন্য ধরো আরো O(log n). এই সময়টা বাঁচানোর জন্যেই BST. সর্ট করতে worst case এর ক্ষেত্রেও সময় লাগছে O(log n). কারণ আমরা সব ডেটাকে চেক করছি না বা সরাচ্ছি না। প্রতি iteration এ ডেটার পরিমাণ অর্ধেক হয়ে যাচ্ছে। অর্ধেক হতে হতে এক পর্যায়ে গিয়ে আমাদের নতুন ডেটা ইনসার্ট হয়। তাই অ্যারের O(n) এর তুলনায় এর efficiency অনেক ভাল (O(log n)).

Insert করার ফাংশন বুঝে গিয়ে থাকলে সার্চ করার ফাংশনও বুঝবা। একই আইডিয়া কাজে লাগিয়ে প্রতি iteration এ ক্ষুদ্র থেকে ক্ষুদ্রতর sub-tree তে ট্রাভার্স করে আমাদের কাংক্ষিত আইটেম খুঁজে বের করব।

1.2  Search an item on BST in C

 

void searchOnTree(int value) {     node *currentNode = root;     int flag = 0;       while(1)     {         if(value == currentNode->number)         {             flag = 1;             break;         }         else if(value<=currentNode->number)             currentNode = currentNode->leftChild;         else             currentNode = currentNode->rightChild;           if(currentNode==NULL)             break;       }       if(flag==1)         printf("\n%d is found on Tree.\n\n", currentNode->number);     else         printf("\n%d is not found on Tree.\n\n", value); }

root node থেকে সবগুলো নোডে ট্রাভার্স করব, যতক্ষণ না পর্যন্ত আইটেম পাওয়া যায় এবং কোনো নোডের মেমরি অ্যাড্রেস NULL না হয়। যদি নোডের number ও value সমান হয় তাহলে flag = 1 করে লুপ ব্রেক করতে হবে। লুপের বাইরে flag এর মানের উপর ভিত্তি করে decision নেয়া হচ্ছে value-টা ট্রিতে পাওয়া গেছে কিনা।

লুপের ভিতরে যদি কোনো একটা স্টেজে currentNode->number==value না হয় তাহলে চেক করতে হবে value টা নোডের number এর চেয়ে ছোট নাকি বড়। যদি value ছোট বা সমান হয় তাহলে ইনসার্টের মতই currentNode এর leftChild এ গিয়ে খুঁজে দেখতে হবে, অন্যথায় rightChild এ গিয়ে খুঁজতে হবে। কোনো একটা পর্যায়ে গিয়ে যদি কোনো নোডের অ্যাড্রেস হিসাবে NULL value পাওয়া যায় তাহলে বুঝতে হবে value-টা ট্রিতে অনুপস্থিত। তখন লুপ ব্রেক করে ফাংশনের কাজ শেষ করতে হবে।

Binary Search Tree Traversal

কোনো ডেটা স্ট্রাকচার ব্যবহারের সময় ডেটাগুলোতে traverse করার দরকার হয়। ট্রাভার্সের অর্থ এক্ষেত্রে সবগুলো ডেটাতে access করা। যেমন অ্যারে বা লিংকড লিস্ট শেখার সময় আমরা স্টোর করা ডেটাগুলো প্রিন্ট করা শিখেছি। শুধু প্রিন্ট নয়, যে কোনো ডেটা সার্চ করা বা নির্দিষ্ট ডেটা আপডেট করার জন্যও সবগুলো ডেটাতে ভ্রমণ করে (traverse) দেখা দরকার হতে পারে। অথবা নিছক এটা দেখার জন্যও সব ডেটাতে ট্রাভার্স করা লাগতে পারে যে, ডেটাগুলো আমার স্ট্রাকচারে ইনসার্ট করেছি সেগুলো আদৌ ঠিকঠাক মত ইনসার্ট হয়েছে কিনা।

অ্যারে, স্ট্যাক, কিউ বা লিংকড লিস্ট হচ্ছে লিনিয়ার ডেটা স্ট্রাকচার। কিন্তু ট্রি নন-লিনিয়ার ডেটা স্ট্রাকচার। Linear Data Structure এর ক্ষেত্রে পুরো স্ট্রাকচারে traverse করা একদম সোজা কাজ। যেহেতু ডেটাগুলো সিরিয়াল্যি থাকে তাই একটার পর একটা ডেটাগুলোতে অ্যাক্সেস করা যায়। অ্যাক্সেসের ধরণও একই হয়। Singly Linked List এর ক্ষেত্রে ধরো, পুরোটা লিংকড লিস্ট প্রিন্ট করতে চাইলে কিন্তু এক ভাবেই প্রিন্ট করা সম্ভব। বা যে কোনো valid code এর জন্য আউটপুট একই আসবে।

ট্রি ট্রাভার্সের সাথে লিনিয়ার ডেটা স্ট্রাকচারের ট্রাভার্সের পার্থক্যটা এখানেই। আগের পোস্ট থেকে দেখেছো যে ট্রির প্রতি নোডে এক বা একাধিক ডেটা থাকে। আর left child ও right child এর মেমরি অ্যাড্রেস থাকে। যদি তোমাকে ট্রি প্রিন্ট করতে বলি তাহলে তুমি কিভাবে প্রিন্ট করব? রুট থেকে লুপ চালিয়ে প্রতিটা নোডে যাবা আর ডেটাগুলো প্রিন্ট করবা, সিম্পল তাই না? একটু চিন্তা করো! কোনো একটা নোডে গিয়ে আগে এই নোডের ডেটা প্রিন্ট করবা নাকি তার বাচ্চাকাচ্চাদের ডেটা প্রিন্ট করবা? তুমি হয়ত আগে নোডের ডেটা প্রিন্ট করবা, এরপর বামের চাইল্ডের ডেটা এরপর ডানের চাইল্ডের ডেটা। আরেক জন দেখা যাবে প্রিন্ট করছে, আগে নোডের বাচ্চাকাচ্চাদের ডেটা। এরপর নোডের নিজের ডেটা। উভয় ক্ষেত্রেই কিন্তু ট্রি এর ডেটাই প্রিন্ট হচ্ছে। শুধু ডেটাগুলো আগে-পিছে প্রিন্ট হচ্ছে। এই ভিন্নতাগুলো সবগুলোই valid. এই আগে পরে প্রিন্টের ব্যাপারটা নিয়েই এখন কথা বলব। DFS – Depth Search Algorithm এর সাহায্যে একটা বাইনারি ট্রি ট্রাভার্স করার তিনটি পদ্ধতি রয়েছে। সেগুলো হচ্ছেঃ

• Pre-order traversal
• In-order traversal
• Post-order traversal

DFS এর মাধ্যমে ট্রি ট্রাভার্সের একটা মূলনীতি আছে। তা হচ্ছে কোনো একটা নোডের siblings এ সার্চ করার আগে ঐ নোডের মাধ্যমে ট্রি এর যতটা deep এ যাওয়া যায় ততটা deep এ যেতে হবে। ধরো রুটের চাইল্ড হচ্ছে A, B. A এর চাইল্ড হচ্ছে C, D. C এর চাইল্ড E, F. এখানে A, B কিন্তু siblings (আপন মায়ের পেটের ভাইবোন)। তুমি যখন A নোডে এসে একটা ডেটা খুঁজে পেলে না, তখন B নোডে গিয়ে খুঁজতে পারবা না। A এর বাচ্চাকাচ্চার মধ্যে খুঁজতে হবে। A থেকে গেলে C তে। C তে খুঁজে না পেলে C এর চাইল্ড D এর কাছে গিয়ে খুঁজতে হবে। এভাবে ট্রি এর গভীর থেকে গভীরে নেমে যেতে হবে। যখন একটা NULL node পাওয়া যাবে তখন বাকি থাকা siblings এর মধ্যে একে একে খুঁজতে হবে। মূলনীতির কনসেপ্ট এটাই।

General recursive pattern for traversing a binary tree

একটা non-empty বাইনারি ট্রি এর যে কোনো নোড N হলে তাতে নিচের তিনটা ঘটনা ঘটতে পারেঃ

(L) – recursively এই N নোডের left subtree তে ট্রাভার্স করবা। Left subtree ট্রাভার্স করা হয়ে গেলে তুমি আবার N এর কাছেই ফিরে আসবা
(R) – recursively এই N নোডের right subtree তে ট্রাভার্স করবা। Right subtree ট্রাভার্স করা হয়ে গেলে তুমি আবার N এর কাছেই ফিরে আসবা
(N) – নোড N-কে প্রসেস করবা।

L-R-N এর কোনটার কাজ আগে করবা কোনটাকে পরে করবা সেই ক্রমই হচ্ছে pre-order, in-order আর post-order. একটা ট্রি প্রিন্ট করার উদাহরণ দিয়ে এই ব্যাপারগুলো ব্যাখ্যা করা হচ্ছে।

ধরো একটা BST-তে এই ডেটাগুলো যথাক্রমে ইনসার্ট করা হবে। 45 হচ্ছে এই ট্রি এর root. BST আঁকা যায় এভাবেঃ
45, 54, 40, 49, 38, 70, 30, 39, 41, 45, 44

Binary Search Tree – BST

Pre-order Traversal

উপরের তিনটা প্রসেসের ক্রম হবে এক্ষেত্রে N-L-R.
অর্থাৎ, N নোডটি NULL না হলে শুরুতেই তাকে প্রসেস করা হবে বা নোডের ডেটাকে প্রিন্ট করে দেয়া হবে। এরপর recursively left subtree এবং right subtree. যদি N নোডটি NULL হয় তাহলে ফাংশন return করবে। কারণ NULL হওয়ার মানে এই নোডটি ট্রিতে exist করে না।

Binary Tree traversal in Pre-order. Output: F, B, A, D, C, E, G, I, H.

1.1 BST Print in Pre-order way using C programming

 

void preOrderPrint(node *rootNode) {     if(rootNode==NULL)         return;       printf("%d ", rootNode->number);       preOrderPrint(rootNode->leftChild);     preOrderPrint(rootNode->rightChild); }

কোডে দেখো, প্রথমেই নোডের ডেটা প্রিন্ট করে দেয়া হয়েছে। এরপর রিকার্সিভ কল হয়েছে। Fig 1.1 এ যেই ট্রি এর ছবি দেয়া হয়েছে এটার জন্য pre-order traversal এ আউটপুট আসবে এটাঃ 45 40 38 30 39 41 45 44 54 49 70

In-order Traversal

এক্ষেত্রে কাজের ক্রম হবে L-N-R.
প্রথমে N নোডের left subtree তে recursively ট্রাভার্স করবে এরপর নোড N-কে প্রসেস করা হবে অর্থাৎ N এর ডেটাকে প্রিন্ট করা হবে। অতঃপর right subtree তে ট্রাভার্স করবে।

BST in In-order. Output: A, B, C, D, E, F, G, H, I.

1.2 BST print in In-order way using C programming

 

void inOrderPrint(node *rootNode) {     if(rootNode==NULL)         return;       inOrderPrint(rootNode->leftChild);       printf("%d ", rootNode->number);       inOrderPrint(rootNode->rightChild); }

Fig 1.1 এর ট্রির আউটপুটঃ 30 38 39 40 41 44 45 45 49 54 70

Post-order Traversal

প্রসেসগুলোর ক্রম হবে L-R-N.
postOrderTraverse(node *N) নামের যদি কোনো ফাংশন থাকে তাহলে তাকে N নোডের left child দিয়ে recursive call করার মাধ্যমে left subtree-তে ট্রাভার্স করবে। এরপর একই ফাংশনকে আবার রিকার্সন কল করা হবে N এর right child দিয়ে। তাহলে right subtree এর সবগুলো নোড ট্রাভার্স করা হবে (নোডগুলোর ডেটা প্রিন্ট করবে)। এরপর গিয়ে N এর ডেটা প্রিন্ট করা হবে।

Binary Tree traversal in Post-order. Output: A, C, E, D, B, H, I, G, F.

1.3 BST print in Post-order way using C programming

 

void postOrderPrint(node *rootNode) {     if(rootNode==NULL)         return;       postOrderPrint(rootNode->leftChild);     postOrderPrint(rootNode->rightChild);       printf("%d ", rootNode->number);   }

Fig 1.1 এর ট্রির আউটপুটঃ 30 39 38 44 45 41 40 49 70 54 45

BST: Find maximum and minimum value

BST কে pre-order, in-order ও post-order এ প্রিন্ট করতে শিখেছিলাম। যে কোনো ডেটা স্ট্রাকচার শেখার সময় আরেকটি কমন অপারেশন শেখানো হয়। তা হচ্ছে maximum ও minimum সংখ্যাটাকে খুঁজে বের করা। এটাও যেহেতু একটা সার্চিং অপারেশন তাই একটা Binary Search Tree এর সর্বোচ্চ বা সর্বনিম্ন মানটি search করার complexity হচ্ছে O(log n).

BST এর properties হচ্ছে এর যে কোনো নোডের left subtree এর সবগুলো নোড হবে ঐ নোডের চেয়ে ছোট বা সমান এবং right subtree এর নোডগুলো হবে বড়। এই বৈশিষ্ট্য থেকে কিন্তু খুব সহজেই বুঝা যায় একদম ছোট মানটা Tree এর কোন পজিশনে থাকবে। যেহেতু বামের নোডগুলোর মান ছোট তাই রুট থেকে যদি ক্রমাগত প্রতিটা নোডের left child এ যেতে থাকি তাহলে সর্বশেষ নোডটার মানই সবচেয়ে ছোট। আর সর্বোচ্চ মানের জন্য যেতে হবে প্রতিটা নোডের ডান right child এ।

Binary Search Tree – BST

উপরের ছবিতে দেখো। সবচেয়ে ছোট মানটা (30) আছে left most node এ। আর সর্বোচ্চ মান (70) আছে right most node এ। তাই সর্বনিম্ন মান খুঁজার জন্য আমরা recursively বা লুপ চালিয়ে সর্ববামের node এ চলে যাব। আর বড় মান খুঁজার জন্য যাব সর্বডানের node এ।

Find Maximum value of BST

Maximum ও minimum সংখ্যা বের করার জন্য recursive ও iterative দুই ভাবেই কোড করা যায়। উভয় কোডই দেখব। maximum বের করব recursively আর minimum বের করব iteratively.

1.1 Recursively find the maximum value of BST in C

 

node * findMaxRecursive(node *root) {     if(root->rightChild==NULL)         return root;       return findMaxRecursive(root->rightChild); }

প্রথমে বেজ কেস চেক করা হচ্ছে। যদি কোনো নোডে গিয়ে দেখা যায় তার right child নাই তার মানে বুঝতে হবে এটাই এই ট্রি এর সবচেয়ে বড় সংখ্যা। তাই যেই নোডে গিয়ে right child পাওয়া যাচ্ছে না সেই নোডটাকেই main function এর কাছে return করা হচ্ছে। আর যদি rightChild==NULL সত্য না হয়, অর্থাৎ right child থাকে তাহলে ঐ rightChild এর অ্যাড্রেসটা দিয়ে এই ফাংশনকে আবার কল করা হচ্ছে। আশা করি বুঝে গেছ। তুমি এবার উপরের কোডটাকে একটু edit করে সর্বনিম্ন মান বের করার জন্য একটা ফাংশন লিখে ফেল।

 

উল্লেখ্য, এই ফাংশন কিন্তু সর্বনিম্ন মানকে রিটার্ন করছে না। বরং যেই নোডটাতে সর্বনিম্ন মান রয়েছে সেই নোডের memory address রিটার্ন করছে। main function থেকে এই অ্যাড্রেসের মানটাকে প্রিন্ট করতে হবে। তবে তুমি চাইলে এই ফাংশনের return type পয়েন্টার না দিয়ে int-ও দিতে পারো। সেক্ষেত্রে এই নোডের মানটাই main function এর কাছে পাঠিয়ে দিবে।

Find Minimum value of BST

Iterative way -তে একটা BST এর সর্বনিম্ন সংখ্যা বের করতে হবে।

1.2 Iteratively find the minimum value of BST in C

node * findMinIterative(node *root) {     if(root==NULL)         return root;     while(root->leftChild != NULL)     {         root = root->leftChild;     }     return root; }

Function parameter হিসেবে root এর মেমরি অ্যাড্রেস পাঠানো হয়েছে। যদি কোনো empty tree এর সর্বনিম্ন সংখ্যা বের করার জন্য এই ফাংশনকে কল করা হয় তখন ফাংশন বডির ভিতরে শুরুর IF blockটা execute হবে। অর্থাৎ আমাদের রুটের মেমরি অ্যাড্রেস যদি NULL হয় তাহলে এই NULL ই রিটার্ন করা হবে। কিন্তু যদি root==NULL মিথ্যা হয় তাহলে ফাংশনের বাকি অংশ কাজ করবে।

আমাদের উদ্দেশ্য হচ্ছে সর্বনিম্ন সংখ্যা বের করা। ছোট সংখ্যাগুলো যেহেতু ট্রির left subtree তে থাকে তাই লুপ ঘুরিয়ে বারবার ট্রি এর বাম দিনের নোডগুলোতে traverse করা হচ্ছে। while এর condition হিসাবে দেয়া হয়েছে root->leftChild != NULL. অর্থাৎ যদি root এর leftChild এর memory address NULL না হয় তাহলে লুপ ঘুরতে থাকবে। লুপের বডিতে বলা হয়েছে root = root->leftChild; অর্থাৎ root এর যেহেতু leftChild বিদ্যমান তাই root এর মধ্যে assign করা হচ্ছে রুটের left child এর মেমরি লোকেশন। এভাবে একে একে ট্রি এর left most node এ পৌঁছে যাব। Left most node এ আসার পর while এর কন্ডিশন মিথ্যা হয়ে যাবে। কারণ left most node এর leftChild এ কোনো child node থাকবে না। যেহেতু কোনো leftChild থাকবে না তাই leftChild != NULL এটা মিথ্যা হবে, কেননা leftChild = NULL। তখন loop break করবে। এরপর return করবে root এর মেমরি অ্যাড্রেস।

মনে করিয়ে দেয়ার জন্য বলি, এই root কিন্তু ট্রি এর সত্যিকারের রুট না। প্রতিবার লুপ ঘুরাতে কিন্তু এই রুটের মান পরিবর্তন হয়েছে। এটা একটা local variable যার lifetime শুধু এই ফাংশনের ভিতরেই থাকবে। রিটার্ন করার পর main function থেকে নোডের অ্যাড্রেসটা receive করে ঐ অ্যাড্রেসের মাধ্যমে নোডের মানটা প্রিন্ট করতে পারো। আশা করি এটা বুঝতেও কোনো সমস্যা নাই। তুমি এখন maximum সংখ্যাটা বের করার জন্য iterative code লিখে ফেল।

Delete any node of BST

লিংকড লিস্ট ছিল Linear Data Structure. তাই লিস্টের মাঝ থেকে কোনো একটা নোড ডিলেট করতে চাইলে তার আগের নোডের সাথে পরের নোডের লিংক করে দিলেই কাজ হয়ে যেত। ট্রি এর ক্ষেত্রে একটু জটিলতা আছে। ধাপে ধাপে ডিলেট করার প্রসেসগুলো দেখাব। আশা করি পোস্ট শেষে যখন সব বুঝে যাবা তখন প্রশ্ন করবা “জটিল পার্টটুকু কুতায়?”

Binary Search Tree – BST এর কোনো একটা নোড ডিলেট করার সময় তিনটা সিচুয়েশন handle করতে হবে। সিচুয়েশনগুলো ভাগ করছি যে কোনো নোডের child এর সংখ্যা দিয়ে। BST এর যে কোনো নোডকে child এর সংখ্যার হিসাবে তিন ভাগে ভাগ করা যায়। যথাঃ

১। 0 child – এমন নোড যার কোনো child নাই। আর জানোই তো এ ধরণের নিঃসন্তান নোডকে বলা হয় leaf.
২। 1 child – যেই নোডের ১ টা মাত্র child আছে। সেটা left child বা right child যে কোনোটাই হতে পারে।
৩। 2 child – যে নোডের ২ টা বাচ্চা আছে।

যেহেতু আমরা কাজ করছি BST নিয়ে তাই আমাদের স্লোগান হতে পারে “দুটি চাইল্ডের বেশি নয়, একটি হলে ভাল হয়!” 

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

BST – Binary Search Tree

Node has 0 child

নিঃসন্তান নোডকে ভ্যানিশ করে দেয়া সবচেয়ে সহজ। কারণ এই বেচারার কোনো পিছুটান নাই। ছেলে-মেয়ে, নাতি-নাতনীর সাথে কোনো বন্ধন নাই। যদি এমন নিঃসন্তান নোডকে ডিলেট করার দরকার হয় তাহলে সেই নোডে NULL assign করে দিলেই কিসসা খতম! কোডটা দেখে ফেলিঃ

1.1 Delete a leaf of BST in C

 

if(currentNode->leftChild == NULL && currentNode->rightChild == NULL) currentNode = NULL;

উপরের দেয়া ছবিতে কয়টা leaf node আছে? এখানে থাকা leaf node-গুলো হচ্ছে 30, 39, 41, 44, 46, 49 এবং 59. অর্থাৎ হলুদ রঙের নোডের প্রত্যেকটিকে উপরের এক লাইন কোডের মাধ্যমে delete করে দেয়া যাবে।

Node has 1 child

এই ট্রিতে ১ মাত্র child আছে এমন নোডের সংখ্যা একটি। সেটিকে দেখানো হয়েছে আকাশী রঙ দিয়ে। ট্রি থেকে যদি 70 ডিলেট করতে চাই আর উপরের কোডের মত করে ঐ নোডের মান NULL করে দেই তাহলে কি ডিলেট হবে? উত্তর হচ্ছে নোডটা তো ডিলেট হবেই সাথে তার চাইল্ডও ডিলেট হবে। কারণ 70 নোডের মান NULL করে দেয়ার মানে হচ্ছে 70 এর parent (54) তার right child হিসেবে NULL কে পয়েন্ট করে থাকবে। ফলে 70 এবং 70 এর left child (59) উভয়েই ট্রি থেকে ডিলেট হয়ে যাবে। কিন্তু আমাদের তো লক্ষ্য 70 কে ডিলেট করা। 70 টা শুধু ডিলেট হবে, 59 ঠিকই ট্রির সাথে থাকবে।

এক্ষেত্রে আমরা লিংকড লিস্টের কোনো আইটেম ডিলেট করার সিসটেমটা ফলো করব। তা হচ্ছে 54 এর right child হিসেবে বসিয়ে দিব 59 এর মান। তাহলে 70 কে কেউ পয়েন্ট করছে না। এটা এমনিতেই ডিলেট হয়ে যাবে। নিচের ছবিটা দেখলে আরো ক্লিয়ার হবে।

Delete node 70 of BST

Source Code:

1.1 Delete a node of BST who has only one child

// node has only right child if(currentNode->leftChild == NULL)     currentNode = currentNode->rightChild; // node has only left child else if(currentNode->rightChild == NULL)     currentNode = currentNode->leftChild;

যদি নোডের right child থেকে থাকে তাহলে প্রথম IF BLOCK কাজ করবে অন্যথায় দ্বিতীয়টা কাজ করবে। উদাহরণের ক্ষেত্রে কাজ করবে দ্বিতীয় ব্লক। 70 কে hold করছে যেই নোড সেটাকে currentNode নাম দিলে currentNode->rightChild == NULL সত্য হবে। তাই রুটকে ডিলেট করতে চাইলে currentNode এর মধ্যে এর leftChild-কে assign করে দিলেই কাজ শেষ। 70 এর leftChild হচ্ছে 59. তাই 70 এর মেমরি অ্যাড্রেস হয়ে যাবে 59 এর মেমরি অ্যাড্রেস। আর এই মেমরি অ্যাড্রেসকে পয়েন্ট করবে 54 এর rightChild.

Node has 2 childred

কমলা রঙের নোডগুলোর প্রত্যেকের দুটি করে children আছে। ধরো আমরা 43 কে ডিলেট করতে চাই। 43 এর নোডকে যদি NULL করে দেই তাহলে এই পুরো subtree-টাই ডিলেট হয়ে যাবে। তাই এমন ভাবে ডিলেট করতে হবে যেন শুধু এই নোডটাই ডিলেট হয়। বাকি নোডগুলো ট্রি এর সাথেই সাথে। এখন প্রশ্ন হচ্ছে 43 কে ডিলেট করার পর তার ঐ স্থানে কাকে বসাবো? 43 এর left child নাকি right child. ধরো right child 45 কে বসালাম 43 এর স্থলে। তাহলে 45 এর তো নিজের দুইটা চাইল্ড আছে সেটা তো থাকবেই, 43 এর left child 41 কোথায় বসবে? একটু চিন্তা ভাবনা করো। 

আমরা জানি যে BST এর বৈশিষ্ট্য হচ্ছে এর মধ্যকার যে কোনো left subtree হবে parent এর চেয়ে ছোট বা সমান। আর right subtree হবে parent এর চেয়ে বড়। আমরা যখন কোনো একটা নোডকে ডিলেট করব বা কোনো একটা নোড insert করব উভয় ক্ষেত্রেই মাথায় রাখতে হবে যেন এই বৈশিষ্ট্য অক্ষুণ্ণ থাকে। অর্থাৎ কোনো নোড insert করার সময় এমন ভাবে করতে হবে যেন এটা যোগ করার ফলে BST এর বৈশিষ্ট্য নষ্ট না হয়। একই ভাবে যখন কোনো নোডকে ডিলেট করব তখনো এমন ভাবে নোডগুলোকে লিংক করতে হবে যেন BST এর properties ঠিক থাকে। এবার চলো, দেখি দুই বাচ্চাওয়ালা নোডকে কিভাবে ডিলেট করা যায়।

দুটি চাইল্ড আছে এমন নোড ডিলেট করার অ্যালগরিদমঃ
১। নোডটির right subtree এর minimum value বের করতে হবে।
২। Minimum value টা ঐ নোডে replace করতে হবে। (রিপ্লেস করলে কিন্তু নোডের আগের মানটা গায়েব হয়ে যাবে)
৩। Minimum value আগে যেই নোডে ছিল সেই নোডকে delete করতে হবে (তা না হলে তো duplicate মান থেকে যাবে ট্রি তে!)

মাথা ঘুরান্টি দিছে? কোনো তালগোল পাচ্ছ না কেনো এই তিনটা স্টেপ ফলো করতে হবে? দাঁড়াও বলছি…

আমাদেরকে যেহেতু 43 কে ডিলেট করতে বলা হয়েছে তাই এই নোডের মানের জায়গায় অন্য যে কোনো মান বসালে এই নোডের মান কিন্তু ডিলেট হয়েই গেল। প্রশ্ন হচ্ছে এই নোডের মানের জায়গায় কেন right subtree এর minimum value বসাবো? কারণ হচ্ছে BST এর বৈশিষ্ট্য অক্ষুণ্ণ রাখার জন্য। চিন্তা করে দেখ… 43 এর right subtree এর সবগুলো মান 43 এর চেয়ে বড়। আমরা যদি randomly 46 কে 43 এর জায়গায় বসাই তাহলে কিন্তু BST এর বৈশিষ্ট্য ঠিক থাকে না। 46 এর right child হবে তখন 45. Right এ তো parent এর চেয়ে ছোট মান থাকতে পারে না। কিন্তু আমরা যদি রাইট সাবট্রি এর সব চেয়ে ছোট মানটা 43 এর জায়গায় বসাই এবং আদী minimum value এর নোডটা ডিলেট করি তাহলে কিন্তু সব বৈশিষ্ট্য ঠিক থাকে।

একই লজিক দিয়ে আরেকটু ভিন্ন ভাবেও কাজ করানো যায়। তা হচ্ছে নোডের right subtree এর minimum value না নিয়ে left subtree এর maximum value দিয়ে নোডের মানটা রিপ্লেস করা এবং maximum value এর নোডটাকে ডিলেট করা। চিন্তা করে দেখো, উভয় ক্ষেত্রেই কিন্তু BST এর properties ঠিক থাকছে। আশা করি বুঝেছ। হয়ত একটু কনফিউশন থাকতে পারে। কোড দেখলে সেটাও দূর হবে। আর এখানে পুরো delete function-টাই দেখানো হচ্ছে। যেটা 0 child, 1 child এবং 2 child আছে অর্থাৎ সকল নোডের ক্ষেত্রেই কাজ করবে।

1.3 Delete a node of BST who has two child

node * deleteNode(node *currentNode, int value) {     if(currentNode==NULL) // empty tree         return NULL;     else if(value < currentNode->number) // value is less than node's number. so go to left subtree         currentNode->leftChild = deleteNode(currentNode->leftChild, value);     else if(value > currentNode->number) // value is greater than node's number. so go to right subtree         currentNode->rightChild = deleteNode(currentNode->rightChild, value);     else // node found. Let's delete it!     {         //node has no child         if(currentNode->leftChild == NULL && currentNode->rightChild == NULL)         {             currentNode = NULL;         }         else if(currentNode->leftChild == NULL) // node has only right child         {             currentNode = currentNode->rightChild;         }         else if(currentNode->rightChild == NULL) // node has only left child         {             currentNode = currentNode->leftChild;         }         else // node has two children         {             node *tempNode = findMinimum(currentNode->rightChild);             currentNode->number = tempNode->number;             currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number);         }     }     return currentNode; }

tempNode এ এখন minimum value এর নোডটার অ্যাড্রেস আছে। আমরা চাই এই নোডের ভ্যালুটা (number variable) currentNode এর ভ্যালু হিসেবে বসে যাক। সেটাই করা হয়েছে currentNode->number = tempNode->number; এই লাইনের মাধ্যমে। ডিলেট করার অ্যালগরিদমের প্রথম দুইটা স্টেপের কাজ শেষ। এখন ডুপ্লিকেট হয়ে যাওয়া নোডটা ডিলেট করতে হবে।

Delete a node of BST. Step by step procedure.

currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number); এই লাইনের মাধ্যমে রিকার্সিভ কল করা হয়েছে minimum value এর নোডটা NULL করে দেয়ার জন্য। 43 কে ডিলেট করার ক্ষেত্রে এই লাইনে থাকা ফাংশনের প্যারামিটার হিসাবে যাচ্ছে 45 এর মেমরি অ্যাড্রেস ও 44. Parameter এ 44 পাঠানোর কারণ হচ্ছে ডুপ্লিকেট মানটা ডিলেট করা। এই ফাংশন যখন কল হবে তখন ফাংশন বডির ৫ নাম্বার লাইনের ELSE IF এর ব্লকটা কাজ করবে। কারণ বর্তমান নোডের মান 45 কিন্তু value তে আছে 44. তখন আবারো ফাংশন কল হবে 45 এর leftChild এর memory location ও 44 দিয়ে। 45 এর leftChild এ এসে দেখা গেল ৫ ও ৭ নাম্বার লাইনের কন্ডিশন মিথ্যা। কারণ value এর মান currentNode->number এর চেয়ে ছোটও না বড়ও না। তার মানে সমান! আমরা যেই নোডটাকে খুঁজছি সেটাকে পাওয়া গেছে। তখন ৯ নাম্বার লাইনের ELSE block কাজ করবে। যেহেতু 44 একটা leaf অর্থাৎ এর কোনো বাচ্চাকাচ্চ নাই তাই ১২ নাম্বার লাইনের condition true হবে। তখন স্বাভাবিক ভাবেই currentNode = NULL করে দেয়ার মাধ্যমে এই নোডটাকে ভ্যানিশ করে দেয়া হল।

ওয়েট! কাজ এখনো শেষ হয় নাই। যেহেতু রিকার্সিভ কল করা হয়েছে আরো কয়েক জন বসে আছে ফাংশনের রিটার্ন ভ্যালুর জন্য। 44 এর নোডকে NULL করার পর ৩৩ নাম্বার লাইনের মাধ্যমে 45 এর কাছে ফাংশনের রিটার্ন টাইপ হিসাবে নোডের অ্যাড্রেস NULL রিটার্ন করবে। এই NULL value বসে যাবে 45 এর leftChild এ। কেননা আগে ৬ নাম্বার লাইনে currentNode->leftChild = deleteNode(root->leftChild, value); কল হয়েছিল। তাই NULL ভ্যালুটা currentNode->leftChild এ assign হবে।

২৮ নাম্বার লাইনে currentNode->rightChild = deleteNode(currentNode->rightChild, tempNode->number); কল করা হয়েছিল। 45 এর অ্যাড্রেস বসে যাবে 44 এর rightChild pointer variable এ। 45 এর নতুন হওয়া parent 44 তার নিজের মেমরি লোকেশন রিটার্ন করবে 44 এর parent 40 এর কাছে। 40 তার নিজের লোকেশন রিটার্ন করবে 47 এর কাছে। 47 হচ্ছে এই ট্রির রুট। 47 তার নিজের লোকেশন রিটার্ন করবে main function এর কাছে। কারণ main function থেকে root = deleteNode(root, 43); কল করা হয়েছিল।

Source-

http://subeen.com

https://hellohasan.com/

http://alavolacoder.blogspot.com/

https://shahinur.com/