বাইনারি ট্রি (Binary Tree)
বাইনারি ট্রি হলো একটি বিশেষ ধরনের গাছের (Tree) ডেটা স্ট্রাকচার যেখানে প্রতিটি নোডের সর্বাধিক দুইটি সন্তান থাকতে পারে। এটি সাধারণত লেফট চাইল্ড এবং রাইট চাইল্ড হিসেবে পরিচিত। বাইনারি ট্রি গঠন এবং পরিচালনা সহজ হওয়ার কারণে অনেক ক্ষেত্রে ব্যবহৃত হয়।
- প্রকারভেদ:
- সম্পূর্ণ বাইনারি ট্রি (Complete Binary Tree): সব লেভেল পূর্ণ থাকে, তবে শেষ স্তরে নোডগুলো বাম থেকে ডানে পূর্ণ না হলেও শেষ স্তরের বাম দিকে নোড থাকবে।
- পূর্ণ বাইনারি ট্রি (Full Binary Tree): প্রতিটি নোডের বা তো দুইটি সন্তান থাকে, নয়তো কোনো সন্তান থাকে না।
- পারফেক্ট বাইনারি ট্রি (Perfect Binary Tree): সমস্ত লেভেল পূর্ণ থাকে এবং প্রতিটি স্তরে সমান সংখ্যক নোড থাকে।
BST (Binary Search Tree)
BST বা বাইনারি সার্চ ট্রি একটি বাইনারি ট্রির বিশেষ ধরনের যেখানে প্রতিটি নোডের বাম সন্তান তার চেয়ে ছোট এবং ডান সন্তান তার চেয়ে বড়। এটি একটি কার্যকর উপায়ে ডেটা সংরক্ষণ, অনুসন্ধান এবং সন্নিবেশ (Insertion) এর জন্য ব্যবহৃত হয়।
- বৈশিষ্ট্য:
- বাম সন্তান (Left Child): সবসময় বর্তমান নোডের চেয়ে ছোট মান ধারণ করে।
- ডান সন্তান (Right Child): সবসময় বর্তমান নোডের চেয়ে বড় মান ধারণ করে।
- অপারেশন:
- সন্নিবেশ (Insertion): নতুন মান বাম বা ডান পাশে রাখার জন্য উপযুক্ত অবস্থান খুঁজে নিয়ে স্থাপন করা হয়।
- অনুসন্ধান (Search): একটি মান খুঁজতে সঠিক পথে চলা হয়, যেমন বড় হলে ডানে যাওয়া এবং ছোট হলে বামে যাওয়া।
- ডিলিশন (Deletion): একটি নির্দিষ্ট মান মুছে ফেলা হয়, এবং এটি তিনটি অবস্থার উপর ভিত্তি করে হতে পারে—কোনো সন্তান নেই, একটি সন্তান আছে, বা দুইটি সন্তান আছে।
AVL ট্রি (AVL Tree)
AVL ট্রি হলো একটি BST যা ব্যালেন্সড থাকে। এটি একটি সেল্ফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি, যেখানে প্রতিটি নোডের বাম এবং ডান উপ-গাছের উচ্চতার মধ্যে পার্থক্য সর্বাধিক ১ থাকতে পারে। উচ্চতা ভারসাম্য রক্ষা করতে এটিতে রোটেশন অপারেশন রয়েছে।
ব্যালেন্স ফ্যাক্টর: প্রতিটি নোডের বাম উপ-গাছ এবং ডান উপ-গাছের উচ্চতার পার্থক্যকে বলে ব্যালেন্স ফ্যাক্টর। এটি সাধারণত -১, ০, বা +১ হতে পারে।
রোটেশন অপারেশন:
- LL (Left-Left): বাম দিকে ভারী হলে ডান দিকে রোটেশন।
- RR (Right-Right): ডান দিকে ভারী হলে বাম দিকে রোটেশন।
- LR (Left-Right): বাম-ডান ভারী হলে বামে ঘুরে তারপর ডানে রোটেশন।
- RL (Right-Left): ডান-বাম ভারী হলে ডানে ঘুরে তারপর বামে রোটেশন।
অপারেশন:
- সন্নিবেশ (Insertion): মান যোগ করার পরে ব্যালেন্স ফ্যাক্টর পরীক্ষা করা হয় এবং প্রয়োজনে রোটেশন করে ট্রি ব্যালেন্স করা হয়।
- ডিলিশন (Deletion): নোড মুছে ফেলার পর ট্রির ভারসাম্য পরীক্ষা করা হয় এবং প্রয়োজন অনুযায়ী রোটেশন করা হয়।
সংক্ষেপে (Summary)
- বাইনারি ট্রি: প্রতিটি নোডের দুইটি সন্তান পর্যন্ত থাকতে পারে।
- BST: বাইনারি ট্রি যেখানে প্রতিটি নোডের বাম শিশু ছোট এবং ডান শিশু বড়।
- AVL ট্রি: একটি সেল্ফ-ব্যালেন্সিং BST, যেখানে নোডের বাম এবং ডান উপ-গাছের উচ্চতার পার্থক্য সর্বাধিক ১।
এই ট্রিগুলির প্রয়োগ বিভিন্ন ক্ষেত্রে ডেটা পরিচালনা এবং সংগঠনে ব্যবহার করা হয়। বিশেষত, AVL ট্রি তার দ্রুত গতি এবং ভারসাম্য বজায় রাখার ক্ষমতার কারণে দক্ষতা বৃদ্ধি করে।
Read more
