Binary Tree - Basics
বাইনারি ট্রি (Binary Tree) হলো এমন একটি ট্রি যেখানে প্রতিটি নোডের সর্বোচ্চ দুটি চাইল্ড থাকতে পারে। এদের সাধারণত Left Child এবং Right Child বলা হয়।
১. বাইনারি ট্রি স্ট্রাকচার (Binary Tree Structure)
বাইনারি ট্রির প্রতিটি নোডে তিনটি অংশ থাকে:
- ডেটা (Data)
- বাম চাইল্ডের অ্যাড্রেস (Pointer to Left Child)
- ডান চাইল্ডের অ্যাড্রেস (Pointer to Right Child)
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- নতুন নোডের জন্য মেমরি বরাদ্দ করুন।
- নোডের ডেটা ফিল্ডে ভ্যালু এসাইন করুন।
- বাম এবং ডান পাশের রেফারেন্সগুলো শুরুতে নাল হিসেবে সেট করুন।
// Java Implementation
class Node {
int data;
Node left, right;
public Node(int value) {
data = value;
left = right = null;
}
}# Python Implementation
class Node:
def __init__(self, value):
self.data = value
self.left = None
self.right = None২. বাইনারি ট্রির বৈশিষ্ট্য (Binary Tree Properties)
- সর্বোচ্চ নোড সংখ্যা: $H$ উচ্চতার একটি বাইনারি ট্রিতে সর্বোচ্চ $2^{H+1} - 1$ টি নোড থাকতে পারে।
- লিফ নোড সংখ্যা: যদি $L$ টি লিফ নোড থাকে এবং $I$ টি ইন্টারনাল নোড (যাদের ডিগ্রি ২) থাকে, তবে $L = I + 1$।
- সর্বনিম্ন উচ্চতা: $N$ সংখ্যক নোডের জন্য সর্বনিম্ন উচ্চতা $\log_2(N+1) - 1$।
৩. বিভিন্ন ধরনের বাইনারি ট্রি (Types of Binary Trees)
Full Binary Tree (পূর্ণ বাইনারি ট্রি)
এমন একটি ট্রি যেখানে প্রতিটি নোডের হয় ০টি অথবা ২টি চাইল্ড থাকে। ১টি চাইল্ড থাকা সম্ভব নয়।
Complete Binary Tree (সম্পূর্ণ বাইনারি ট্রি)
সবগুলো লেভেল পূর্ণ থাকে, শুধু শেষ লেভেলটি বাম দিক থেকে পূর্ণ হতে পারে।
Perfect Binary Tree (নিখুঁত বাইনারি ট্রি)
সবগুলো ইন্টারনাল নোডের ২টি চাইল্ড থাকে এবং সব লিফ নোড একই লেভেলে থাকে।
Balanced Binary Tree (ভারসাম্যপূর্ণ বাইনারি ট্রি)
এমন একটি ট্রি যেখানে বাম এবং ডান সাব-ট্রির উচ্চতার পার্থক্য সর্বোচ্চ ১ হয়। উদাহরণ: AVL Tree, Red-Black Tree।
Skewed Binary Tree (একপাক্ষিক বাইনারি ট্রি)
যে ট্রিতে সব নোডের শুধু একটি করে চাইল্ড থাকে (হয় বাম অথবা ডান)। এটি অনেকটা লিঙ্কড লিস্টের মত আচরণ করে।
কেন বাইনারি ট্রি গুরুত্বপূর্ণ?
বাইনারি ট্রি ডেটা সার্চিং এবং সর্টিং-এর জন্য খুবই কার্যকর। বিশেষ করে Binary Search Tree এবং Binary Heap এর মত স্ট্রাকচারগুলো প্রচুর ব্যবহৃত হয়।