Post updated on 31st January, 2017 at 04:16 pm
ট্রি ডেটা স্ট্রাকচার সিরিজের প্রথম পর্বে ট্রি সম্পর্কে প্রাথমিক ধারণা দেয়া হয়েছিল। ট্রি এর উপাদানগুলো কী কী? কোনটাকে কী বলা হয়? ট্রি এর কিছু বৈশিষ্ট্য নিয়েও আলোচনা করা হয়েছে। এই পর্বে দেখব ট্রি এর অ্যাপ্লিকেশন বা কোথায় কোথায় ট্রি ব্যবহার করতে হয় সে বিষয়ে। আরো জানবো কয়েক ধরণের ট্রি এবং সেগুলোর বৈশিষ্ট্য।
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 এ শো করা।
পিসি ফাস্ট করার আরেকটা মহান ট্রিক্স হল বার বার Refresh করা! বাচ্চা কাল থেকে দেখে আসতেছি এই রিফ্রেশ আর ট্রির কারিশমা! তুমি তো এখন জানোই রিফ্রেশ করার ব্যাপারটাও বোগাস! রিফ্রেশ করলে পিসি “ফ্রেশ” হয় না বরং তুমি যেই ভিউটা দেখতে পাচ্ছ সেটা রিসেট হয়। এগুলার সাথে পিসি ফাস্ট হবার কোনো সম্পর্ক নাই। ISP এর লোকেরা বাসায় আসলে অভ্যাস বশত বার বার রিফ্রেশ করতে গিয়ে রিফ্রেশ অপশন আর খুঁজে পায় না। লিনাক্সে রিফ্রেশ অপশন পাইবে কৈ? 😛
HTML Document Object Model (DOM): তুমি যদি একদম ব্যাসিক HTML সম্পর্কে জেনে থাকো তাহলে খুব সহজেই নিচের চিত্র দেখে ব্যাপারটা বুঝে যাবা। যত ওয়েব পেজ আছে সবগুলোর ডেটাগুলো এরকম একটা ট্রি এর মাধ্যমেই মেমরি স্টোর করা হয়।
Network Routing: তোমার যদি নেটওয়ার্কিং এর ব্যাপারে আগ্রহ থাকে বা ঘাটাঘাটি করে থাকো তাহলে জানার কথা যে ডেটা যখন একটা মেশিন থেকে অন্য মেশিনে যায় তখন মাঝে অনেকগুলো রাউটারের মধ্যে দিয়ে যায়। তোমার পিসি থেকে আমার ব্লগে হিট করেছ। আমার ব্লগ ধরো হোস্ট করা আছে আমেরিকার কোনো সার্ভারে। এখান থেকে সার্ভার পর্যন্ত ডেটাগুলো যাওয়ার সময় মাঝে অনেকগুলো রাউটার পরে। কোন রাউটারের পর কোন রাউটারের কাছে ডেটা নিয়ে যেতে হবে সেই পথ বাতলে দেয়ার জন্য আছে Network Routing Algorithm. এখানেও রয়েছে ট্রি ডেটা স্ট্রাকচারের কাজ।
Syntax Tree in Compiler: কম্পাইলার যখন আমাদের প্রোগ্রামকে কম্পাইল করে তখন প্রতিটা expression কে syntax tree ফরমেটে কনভার্ট করে।
Auto Correcter and Spell Checker: অটো কারেকশনের কাজটা কিন্তু একদম ইন্সট্যান্ট হয়। এজন্য ডেটাগুলো বা শব্দগুলো এমন ফরমেটে থাকা জরুরি যেখান থেকে খুব দ্রুত সার্চ করা যায় বা ভুল ও শুদ্ধ বানানের মাঝের পার্থক্যটা দ্রুত ধরে ফেলা যায়। তাই শব্দগুলোকে ট্রিতে সাজিয়ে রাখা হয়।
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 এর মান হবে নোডের চেয়ে বড়।
চিত্র দেখলেই ব্যাপারটা ক্লিয়ার হয়ে যাবে। রুট নোডের কথাই ধরো। এর বামের সবগুলো মান রুটের মানের চেয়ে ছোট। ডানের সবগুলো নোডের মান রুটের চেয়ে বড়। একই ভাবে অন্যান্য যে কোনো parent node এর ক্ষেত্রেও এই শর্ত প্রযোজ্য।
আরো কয়েক ধরনের ট্রি আছে। যথাঃ
- AVL Tree
- Red Black Tree
- Splay Tree
- Trie
- Huffman Tree
- N-ary Tree
- Suffix Tree ইত্যাদি।
এই পোস্টটিও বেশ বড় হয়ে যাওয়ায় এখানে আর ইমপ্লিমেন্টেশন করলাম না। পরের পোস্টে বাইনারি সার্চ ট্রি এর ইমপ্লিমেন্টেশন সোর্স কোড সহ পাওয়া যাবে।
