ট্রি (Tree) এবং বাইনরি সার্চ ট্রি (Binary Search Tree) ডেটা স্ট্রাকচারগুলি কম্পিউটার সায়েন্সে গুরুত্বপূর্ণ। এগুলো হায়ারার্কিক্যাল ডেটা সংগঠনের জন্য ব্যবহৃত হয় এবং বিশেষ করে ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনের জন্য খুবই কার্যকরী।
১. ট্রি (Tree)
একটি ট্রি হলো একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা একটি সেট নোড এবং এদের মধ্যে সংযুক্ত এজ (edges) দিয়ে গঠিত হয়। ট্রি সাধারণত একটি রুট (root) নোড দিয়ে শুরু হয় এবং অন্যান্য নোডগুলি রুটের সাথে সংযুক্ত থাকে।
ট্রি ডেটা স্ট্রাকচারের কিছু গুরুত্বপূর্ণ বৈশিষ্ট্য:
- রুট (Root): ট্রির প্রথম নোড, যেখান থেকে অন্যান্য নোডগুলো শাখা বা উপশাখা হিসেবে বৃদ্ধি পায়।
- লিফ (Leaf): যে নোডগুলির কোন চাইল্ড নোড থাকে না, তাদের লিফ নোড বলা হয়।
- প্যারেন্ট (Parent): একটি নোড যার চাইল্ড নোড থাকে।
- চাইল্ড (Child): যে নোডটি প্যারেন্ট নোডের অধীনে থাকে।
- এজ (Edge): দুটি নোডের মধ্যে সংযোগ।
উদাহরণ:
A
/ \
B C
/ \
D Eএখানে:
Aহলো রুট।BএবংCহলোAএর চাইল্ড।DএবংEহলোBএর চাইল্ড।D,E, এবংCহলো লিফ নোড।
২. বাইনারি ট্রি (Binary Tree)
একটি বাইনারি ট্রি হলো একটি বিশেষ ধরনের ট্রি যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকে। অর্থাৎ, প্রতিটি নোডের দুটি সন্তান থাকতে পারে: একটি বাম (Left) এবং একটি ডান (Right) সন্তান।
উদাহরণ:
A
/ \
B C
/ \
D Eএখানে:
Aহলো রুট নোড।BহলোAএর বাম চাইল্ড এবংCহলোAএর ডান চাইল্ড।DএবংEহলোBএর বাম ও ডান চাইল্ড।
৩. বাইনারি সার্চ ট্রি (Binary Search Tree - BST)
একটি বাইনারি সার্চ ট্রি (BST) হলো একটি বিশেষ ধরনের বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম সাবট্রি এবং ডান সাবট্রির মধ্যে একটি নির্দিষ্ট নিয়ম থাকে:
- বাম সাবট্রি: একটি নোডের বাম চাইল্ড সাবট্রিতে থাকা সব নোডের মান ঐ নোডের মানের চেয়ে ছোট।
- ডান সাবট্রি: একটি নোডের ডান চাইল্ড সাবট্রিতে থাকা সব নোডের মান ঐ নোডের মানের চেয়ে বড়।
এই নিয়মের কারণে BST-তে ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনগুলো খুব দ্রুত সম্পন্ন করা যায়। সাধারণত O(log n) সময়ে এই অপারেশনগুলো সম্পন্ন করা সম্ভব হয়।
উদাহরণ:
10
/ \
5 15
/ \ \
2 7 20এখানে:
10হলো রুট নোড।- বাম সাবট্রিতে (5, 2, 7) এর মানগুলি
10এর চেয়ে ছোট, আর ডান সাবট্রিতে (15, 20) এর মানগুলি10এর চেয়ে বড়।
এটি বাইনারি সার্চ ট্রির একটি উদাহরণ।
৪. BST এর মূল অপারেশন
BST-তে কিছু প্রধান অপারেশন রয়েছে যা গুরুত্বপূর্ণ ডেটা ম্যানিপুলেশনে ব্যবহৃত হয়। এগুলি হলো:
- ইনসার্ট (Insert):
- BST-তে নতুন নোড যোগ করার সময়, নতুন নোডটি সঠিক স্থানে বসাতে হয় যাতে ট্রির নিয়ম বজায় থাকে। মানের তুলনায় ছোট হলে বাম সাবট্রিতে এবং বড় হলে ডান সাবট্রিতে যুক্ত হয়।
- অনুসন্ধান (Search):
- BST-তে অনুসন্ধান করা সহজ, কারণ প্রতি নোডের বাম ও ডান সাবট্রির মধ্যে নিয়মিত অবস্থান থাকে। প্রতিটি নোডে গিয়ে আপনি খুঁজতে পারেন যে নোডটি কোথায় অবস্থিত। এটির গড় সময় জটিলতা O(log n) হয়।
- ডিলিট (Delete):
- BST-তে ডিলিট অপারেশন তিনটি ক্ষেত্রে বিভক্ত হতে পারে:
- কেস ১: যদি মুছে ফেলা নোডের কোন চাইল্ড না থাকে, তাহলে শুধু নোডটি মুছে ফেলতে হবে।
- কেস ২: যদি একটি চাইল্ড থাকে, তাহলে চাইল্ডটি সরাসরি নোডের জায়গায় বসিয়ে দেওয়া হয়।
- কেস ৩: যদি দুটি চাইল্ড থাকে, তাহলে নোডের ডান বা বাম সাবট্রি থেকে সর্বনিম্ন (বা সর্বোচ্চ) মানের নোডটি খুঁজে এনে তা মুছে ফেলা নোডের জায়গায় বসানো হয়।
- BST-তে ডিলিট অপারেশন তিনটি ক্ষেত্রে বিভক্ত হতে পারে:
৫. BST-এর সুবিধা ও অসুবিধা
সুবিধা:
- দ্রুত অনুসন্ধান: ডেটা BST-তে সজ্জিত থাকলে অনুসন্ধান, ইনসার্ট, ডিলিট অপারেশনগুলো O(log n) সময়ের মধ্যে সম্পন্ন করা যায়।
- প্রাকৃতিক সাজানো: BST ডেটাকে স্বাভাবিকভাবে সাজায়, যাতে ইন অর্ডার ট্রাভার্সাল করলে সজ্জিত ডেটা পাওয়া যায়।
অসুবিধা:
- অসামঞ্জস্যপূর্ণ ডেটা: যদি ডেটা সঠিকভাবে সাজানো না থাকে (যেমন একে একে বাড়ানো বা কমানো), তাহলে BST একটি লিনিয়ার স্ট্রাকচারে পরিণত হতে পারে, যার ফলে অপারেশনগুলো O(n) সময় নিতে পারে।
- ব্যালেন্সিং: ব্যালেন্সড না হলে BST-এর কার্যকারিতা কমে যায়, তাই সাধারনত AVL ট্রি বা Red-Black ট্রি ব্যবহার করা হয়।
সারাংশ
- ট্রি একটি হায়ারার্কিক্যাল ডেটা স্ট্রাকচার যা নোড এবং এজ দিয়ে গঠিত হয়।
- বাইনারি ট্রি এমন একটি ট্রি যেখানে প্রতিটি নোডে সর্বাধিক দুটি চাইল্ড নোড থাকে।
- বাইনারি সার্চ ট্রি (BST) এমন একটি বাইনারি ট্রি যা ডেটাকে একটি নির্দিষ্ট নিয়মে সাজায়, যা অনুসন্ধান, ইনসার্ট এবং ডিলিট অপারেশনকে দ্রুত করতে সাহায্য করে।
BST ব্যবহৃত হয় দ্রুত ডেটা অনুসন্ধান, ইনসার্ট এবং ডিলিট করতে, তবে এটি ব্যালেন্সড রাখতে হয় যাতে অপারেশনগুলি দক্ষ থাকে।
Read more
