বাংলা শব্দ গাছ এর ইংরেজী প্রতিশব্দ হল Tree. ট্রি সম্পর্কে নতুন করে কিছু বলার নাই। ট্রি ঠিক নরমাল ট্রি (গাছ) এর মতই তবে গঠন বা পজিশনের দিক দিয়ে ঠিক বাস্তব ট্রি'র উল্টো! যদি মস্ত বড় ভূমিকম্পে পৃথিবী কখনো উল্টে যায় তাহলে ডাটা স্ট্রাকচারের ট্রি আর নরমাল ট্রি'র পজিশন এক হয়ে যাবে। যাইহোক, ভূতাত্ত্বিক গবেষনা বাদ দিয়ে ডাটা স্ট্রাকচার নিয়ে জানাশুনা করি! ট্রি আসলে কি ? এ নিয়ে উইকিপিডিয়ার বক্তব্যঃ
In computer science, a tree is a widely used abstract data type (ADT) or data structure implementing this ADT that simulates a hierarchical tree structure, with a root value and subtrees of children, represented as a set of linked nodes.
 |
| চিত্রঃ ট্রি |
১। প্যারেন্ট(parent): যে নোড থেকে অন্য নোডের দিকে লিঙ্ক করা থাকে তাকে ওই নোডগুলোর প্যারেন্ট বলে। যেমন , B হল D ও E এর প্যারেন্ট, C হল F এর প্যারেন্ট এবং F হল G ও H এর প্যারেন্ট!
২। সিবলিংস (siblings): একই প্যারেন্ট যুক্ত নোডগুলোর একে অপরকে সিবলিংস বলে। যেমন, D ও E অথবা G ও H হল একে অপরের সিবলিংস।
৩। চিলড্রেন (children): যে নোডের সাথে পূর্ববর্তী কোন নোডের লিঙ্ক করা থাকে তাকে ওই নোডের চিলড্রেন বলে। চিত্রেঃ B ও C হল A নোডের চিলড্রেন; D ও E হল B নোডের চিলড্রেন ; F হল C নোডের চিলড্রেন এবং G ও H হল F নোডের চিলড্রেন!
৪। রুট নোড (Root node): যে নোডের দিকে অন্য কোন নোডের লিঙ্ক নাই তাকে রুট নোড বলে অথবা যে নোডের কোন parent নাই তাকেই রুট নোড বলে। যেকোন ট্রি'র মাত্র একটি রুট নোড থাকে! সাধারনত প্রথম নোডটাই রুট নোড হয়ে থাকে। চিত্রে A হল রুট নোড।
৫। লিফ নোড (Leaf node): যে নোড হতে অন্য কোন নোডের দিকে লিঙ্ক করা থাকেনা তাকে লিফ নোড বলে। অন্যভাবে বলতে গেলে যে নোডের কোন বাচ্চাকাচ্চা-চিলড্রেন নাই তাকে লিফ নোড বলে! চিত্রে- D,E,G,H হল লিফ নোড।
৬। ancestor (অ্যানসেস্টর): অ্যানসেস্টর কথাটার অর্থই হল পূর্বপুরুষ! পূর্বপুরুষ কি জিনিস বলার প্রয়োজন নাই! আরো সহজে বলতে গেলে কোন নোড কোন কোন নোড অতিক্রম করে ওই নোডে এসেছে সেই সেই নোডগুলোই বলা হয় ওই নোডের অ্যানসেস্টর।
যেমন, H এর অ্যানসেস্টর হল A,C,F
E এর অ্যানসেস্টর হল- A,B
লক্ষনীয়ঃ প্রত্যেকে আবার নিজেই নিজের নিজের অ্যানসেস্টর! নিজেকে বাদ দিয়ে যে অ্যানসেস্টর হয় তাকে proper ancestor বলে।
যেমনঃ Ancestor of H: {H,A,C,F}
proper ancestor of H:{ A,C,F}
৭। Descendant( বংশধর): descendant মানে হল বংশধর! কোন এক প্যারেন্ট থেকে বাচ্চা কাচ্চা সহ যে পরিমান নাতি-পুতি বের হইছে সবগুলোকেই descendant বলে :D
যেমন H হল A,C,F এর descendant
descendant of C: {F,G,H}
৮। Degree of Node: কোন নোডের ডিগ্রি হল ওই নোড থেকে আশা মোট সাব- ট্রি'র সংখ্যা!
যেমন A এর সাব ট্রি B ও C সুতরাং A এর ডিগ্রি- 2
এভাবে-
Degree of B: 2
Degree of F: 2
Degree of G: 0
৯। height of a node: কোন নোডে থেকে লিফ নোড পর্যন্ত সর্বাধিক লম্বা পথে ভ্রমন করলে যে পরিমান লিঙ্ক পাওয়া যায় তাকে সে নোডের উচ্চতা বা height বলে।
Height of A: 3
Height of C: 2
Height of B: 1
Height of G: 0
৯। Level a tree (লেবেল): রুট নোড থেকে শুরু করে লিফ নোড পর্যন্ত লম্বা পথে থাকা মোট লিঙ্ক সংখ্যাকে লেবেল বলে। লেবেল শুন্য থেকে শুরু হয়।
Level of the tree: 3
Level of A: 0
Level of B,C: 1
Level of D,E,F: 2
Level of G,H: 3
১০। Depth of a node: রুট নোড থেকে ঐ নোড পর্যন্ত যতগুলো লিঙ্ক থাকে সে লিঙ্কের মোট সংখ্যাকে ওই নোডের depth বলে। যেমন,
Depth of A: 0
Depth of B: 1
Depth of F: 2
Depth of H: 3
#লক্ষণীয়ঃ প্রত্যেকটি ট্রি'র n-1 লিঙ্ক থাকে! যেখানে n হল মোট নোড সংখ্যা!
আজ এ পর্যন্তই ! ধন্যবাদ, সাথে থাকুন ।
