Tree Basics
ট্রি (Tree) হলো একটি নন-লিনিয়ার (Non-linear) এবং হায়ারার্কিকাল (Hierarchical) ডেটা স্ট্রাকচার। এটি নোড (Node) এবং এজ (Edge) এর সমন্বয়ে গঠিত হয়।
১. ট্রি টার্মিনোলজি (Tree Terminology)
- Root: ট্রির একদম উপরের নোড যেটির কোনো পেরেন্ট নেই।
- Leaf: ট্রির শেষ প্রান্তের নোডগুলো যাদের কোনো চাইল্ড নেই।
- Parent: যে নোড থেকে অন্য নোড তৈরি হয়।
- Child: পেরেন্ট নোড থেকে যে নোডগুলো বের হয়।
- Sibling: একই পেরেন্ট নোডের চাইল্ডদের একে অপরের সিবলিং বলা হয়।
- Ancestor: কোনো নির্দিষ্ট নোড থেকে রুট পর্যন্ত পথে থাকা সব নোড।
- Descendant: কোনো নোড থেকে লিফ পর্যন্ত পথে থাকা সব নোড।
২. ট্রির বৈশিষ্ট্য (Tree Properties)
- Height: রুট থেকে সবচেয়ে দূরের লিফ নোড পর্যন্ত থাকা এজ-এর সংখ্যা।
- Depth: রুট থেকে নির্দিষ্ট কোনো নোড পর্যন্ত থাকা এজ-এর সংখ্যা।
- Level: রুট হলো লেভেল ০, তার চাইল্ডগুলো লেভেল ১, এভাবে বাড়তে থাকে।
- Degree: একটি নোডের কতগুলো চাইল্ড আছে তার সংখ্যা।
৩. ট্রির প্রকারভেদ (Types of Trees)
- General Tree: একটি নোডের যেকোনো সংখ্যক চাইল্ড থাকতে পারে।
- Binary Tree: প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড থাকতে পারে।
- Binary Search Tree (BST): একটি স্পেশাল বাইনারি ট্রি যেখানে বাম চাইল্ড ছোট এবং ডান চাইল্ড বড় হয়।
- AVL Tree: সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি।
৪. বাইনারি ট্রি বনাম জেনারেল ট্রি (Binary Tree vs General Tree)
| বৈশিষ্ট্য | জেনারেল ট্রি | বাইনারি ট্রি |
|---|---|---|
| চাইল্ড সংখ্যা | যেকোনো সংখ্যক হতে পারে | সর্বোচ্চ ২ টি (০, ১ বা ২) |
| অর্ডার | নির্দিষ্ট কোনো অর্ডার নেই | বাম এবং ডান চাইল্ডের অর্ডার গুরুত্বপূর্ণ |
৫. ট্রির ব্যবহার (Tree Applications)
- File Systems: কম্পিউটারের ডিরেক্টরি এবং ফাইল ম্যানেজমেন্টে।
- HTML DOM: ওয়েব পেজের স্ট্রাকচার রিপ্রেজেন্টেশনে।
- Decision Trees: মেশিন লার্নিং এবং ডিসিশন মেকিংয়ে।
- Routing Algorithms: নেটওয়ার্ক রাউটিং টেবিল ম্যানেজমেন্টে।
৬. ট্রি রিপ্রেজেন্টেশন (Tree Representation)
কোডের মাধ্যমে আমরা সাধারণত একটি নোড ক্লাস বা স্ট্রাকচার তৈরি করে ট্রি রিপ্রেজেন্ট করি।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- একটি
Nodeক্লাস তৈরি করুন। - ক্লাসের ভেতরে ডেটা স্টোর করার জন্য একটি ভ্যারিয়েবল নিন।
- বাম এবং ডান পাশের চাইল্ড নোডগুলোর অ্যাড্রেস রাখার জন্য দুটি পয়েন্টার/রেফারেন্স (উদাঃ
left,right) নিন। - কনস্ট্রাক্টরের মাধ্যমে নতুন নোড তৈরি করার সময় ডিফল্টভাবে চাইল্ডগুলোকে
nullবাNoneসেট করুন।
java
// Java Node Representation for Binary Tree
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}python
# Python Node Representation for Binary Tree
class Node:
def __init__(self, key):
self.left = None
self.right = None
self.val = key