ডাটা স্ট্রাকচার - ৭ঃ ট্রি টার্মিনোলজি

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

ট্রি এর কিছু গুরুত্বপুর্ন টার্মঃ 

১। মুল নোড (Root node): যেকোন ট্রি এর সবচেয়ে উপরের নোডটাই হল রুট নোড। যেমন, উপরের ট্রি ক্ষেত্রে রুট নোড হল- 10

২। এজ(Edge): দুটি নোডের মধ্যবর্তী সংযোগকে এজ বলা হয়। প্রত্যেকটি ট্রি'র n-1 লিঙ্ক থাকে! যেখানে n হল মোট নোড সংখ্যা! 

৩। প্যারেন্ট এবং চিলড্রেন(Parent and Children): যে নোড থেকে অন্য নোডের দিকে লিঙ্ক করা থাকে তাকে ওই নোডগুলোর প্যারেন্ট বলে। যেমন , 10 হল 20 ও 30 এর প্যারেন্ট নোড। একইভাবে 20, 30 হল 10 এর চিলড্রেন  

৪। সিবলিংস (Siblings): একই প্যারেন্ট যুক্ত নোডগুলোর একে অপরকে সিবলিংস বলে। যেমন, 20 ও 30 হলো পরস্পর পরস্পরের সিবলিংস। 

৫। লিফ নোড (Leaf Node): যে নোডের কোন চিলড্রেন থাকেনা তাদেরকে লিফ নোড বলে। চিত্রে 30, 40, 50 হল লিফ নোড 

৬। অ্যানসেস্টর (Ancestor): রুট নোড থেকে কোন নোডে আসতে যতগুলো নোড অতিক্রম করতে হয় তাদের প্রত্যেককেই ওই নোডের অ্যানসেস্টর বলে। বাংলায় যাকে বলা হয় পূর্বপুরুষ। 
যেমন, 40 এর অ্যানসেস্টর হল 10, 20 , 40
30 এর অ্যানসেস্টর হল- 10, 30  

লক্ষনীয়ঃ প্রত্যেকে আবার নিজেই নিজের নিজের অ্যানসেস্টর! নিজেকে বাদ দিয়ে যে অ্যানসেস্টর হয় তাকে proper ancestor বলে।
যেমনঃ Ancestor of 10: {10, 20}
proper ancestor of 40: {10}

৭। Descendant( বংশধর): কোন নোড থেকে লিফ নোড পর্যন্ত যেতে যতগুলো নোড অতিক্রম করতে হয় তাদের প্রত্যেক্যে ডিসচেন্ডেন্ট বা বংশধর বলে। বাংলায় যাকে বলে- সন্তান-সন্ততি/নাতি-পুতি :|  
10 এর ডিসচেন্ডেন্টঃ 10, 20, 40 

৮।  Degree of Node: কোন নোডের ডিগ্রি হল ওই নোড থেকে যাওয়া মোট সাব- ট্রি'র সংখ্যা! 
যেমন 10 এর সাব ট্রি 20 ও 30 সুতরাং  20 এর ডিগ্রি- 30, 40
এভাবে-
Degree of 10: 2
Degree of 20: 2
Degree of 30: 0

৯। Height of a Node: লিফ নোড থেকে কোন নির্দিষ্ট নোড পর্যন্ত সর্বাধিক লম্বা পথে যে পরিমান লিঙ্ক বা এজ পাওয়া যায় তাকে সে নোডের উচ্চতা বা height বলে। 
Height of 10: 2
Height of 20: 1
Height of 30: 0
Height of 40: 0

৯। Level a Tree (লেবেল): রুট নোডকে বলা হয় লেভেল ০ নোড। রুট নোডের চাইল্ডগুলোকে বলা হয় লেভেল ১ নোড। লেভেল ১ এর চাইল্ডগুলোকে বলা হয় লেভেল ২ নোড। এভাবে নোডগুলোর লেভেলিং হয়। 
Level 0: 10
Level 1: 20, 30
Level 2: 40, 50

১০। Depth of a Node: রুট নোড থেকে ঐ নোড পর্যন্ত যতগুলো লিঙ্ক থাকে সে লিঙ্কের মোট সংখ্যাকে ওই নোডের Depth বলে। যেমন,
Depth of A: 0
Depth of B: 1
Depth of F: 2
Depth of H: 3

***বাইনারি ট্রিঃ  ট্রি অনেক ধরনের হতে পারে। কম্পিউটার প্রোগ্রামিং এ সবচেয়ে বেশী আলোচনা হয় বাইনারি ট্রি নিয়ে। এই বাইনারি ট্রি দিয়েই বেশ কিছু অ্যালগরিদম আছে। বাইনারি ট্রি হল এমন এক ধরনের ট্রি যেখানে প্রতিটা নোডের চাইল্ড দুইটার বেশী হয়না। অথ্যাৎ, প্রতিটা নোডের চাইল্ড সংখ্যা ০, ১, ২ এর মধ্যেই সীমাবদ্ধ। বাইনারি ট্রি 

ফুল বাইনারি ট্রিঃ যেসব ট্রি  এর প্রতিটা নোডের দুইটা করে চাইল্ড থাকে তাকে ফুল বাইনারি ট্রি বলে। 

২। কমপ্লিট বাইনারি ট্রিঃ যেসব নোড ফুল বাইনারি ট্রি না কিন্তু নোডগুলো বাম পাশ থেকে ফিলাপ হয়ে আসে তাকে কমপ্লিট বাইনারি ট্রি বলে।