Post updated on 21st September, 2017 at 07:27 am
তোমার কম্পিউটারে অসংখ্য ফোল্ডার আছে। ফোল্ডারের ভিতরে ফোল্ডার আছে, তার ভিতরে আরো ফোল্ডার আছে। এভাবে ফোল্ডারের ভিতরে ঢুকতে থাকতে থাকলে এক পর্যায়ে গিয়ে দেখা যাবে আর ফোল্ডার নাই। হয়ত এক বা একাধিক ফাইল আছে।
উপরের চিত্রটা দেখ। কী চেনা চেনা লাগে? ধরো একদম উপরের বক্সটা তোমার পিসির “My Computer”. পিসি ওপেন করেই তুমি এই আইকনে ডাবল ক্লিক করো। এরপর C, D, E ও F নামের চারটা ড্রাইভ দেখতে পাও। একেকটা ড্রাইভের মধ্যে একেক টাইপের ডেটা আছে। যেমন D drive এ দেখা যাচ্ছে চারটা ফোল্ডার। টিউটোরিয়াল নামের ফোল্ডারের ভিতরে তিনটা ফোল্ডার আছে এবং একটা ফাইল আছে। java নামক ফোল্ডারে ডাবল ক্লিক করলে এই ফোল্ডারটা ওপেন হবে। ভিতরে হয়ত আরো ফোল্ডার বা ফাইল দেখতে পাওয়া যাবে। কিন্তু Java.pdf নামক যেই ফাইলটা আছে সেটাতে ডাবল ক্লিক করলে কী ঘটবে? এটা যেহেতু ফাইল তাই এটা নির্দিষ্ট অ্যাপ্লিকেশনের মাধ্যমে ওপেন করা যাবে। এটা ওপেন হয়ে কিন্তু আরো কোনো ফোল্ডার/ফাইল পাওয়ার কোনো সম্ভাবনা নাই। অর্থাৎ ফাইলগুলোকে ধরা যায় একেকটা end point হিসেবে। এর পরে আর যাওয়ার রাস্তা নাই।
এতক্ষণ আমরা কথা বললাম My Computer>D Drive>Tutorial এই লোকেশনের ফাইল/ফোল্ডার নিয়ে। একই রকম ভাবে অন্যান্য সকল ফোল্ডারের ভিতরেই এরকম ফাইল/ফোল্ডার পাওয়া যাবে। এই ফাইল ফোল্ডার একটার পরে একটা কিভাবে সাজানো আছে এটা বুঝে গিয়ে থাকলে তোমার ট্রি ডেটা স্ট্রাকচারের ব্যাসিক বুঝা হয়ে গেছে।
এইবার এক
টু বইয়ের ভাষায় কথা বলা যাক। ট্রি হচ্ছে কিছু নোডের সমন্বয়ে গঠিত একটা নন-লিনিয়ার এবং Hierarchical Data Structure. যেখানে নোডগুলো একে অপরের সাথে যুক্ত থাকবে কিন্তু কোনো সাইকেল তৈরি করবে না। যেমন পাশের ছবিটি (Fig:1. Binary 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 হতে পারে না তাই এই রুলসটা সকল ট্রি এর জন্য সত্য হবে।
আজ এ পর্যন্তই। পরের পর্বে ট্রি এর অ্যাপ্লিকেশন ও প্রকারভেদ নিয়ে আলোচনা করা হবে।
অনেক সুন্দর করে লিখেছেন। অসংখ্য অসংখ্য ধন্যবাদ। এধরনের বাংলায় আরো কিছু যোগ করবেন আশা করছি।