Index

AVL ট্রি এর পরিচিতি ও গুরুত্বপূর্ণ বিষয়সমূহ:

১. বাইনারি ট্রি (Binary Tree) এবং এর সমস্যা:

• বাইনারি ট্রির ক্ষেত্রে প্রতিটি নোডের (Node) সর্বোচ্চ দুটি চাইল্ড বা সন্তান থাকতে পারে (০, ১ বা ২)।
• এতে ডেটা ইনসার্ট বা প্রবেশ করানোর কোনো নির্দিষ্ট নিয়ম বা ক্রম থাকে না। যেকোনোভাবেই ডেটা রাখা যায়।
• তবে কোনো নির্দিষ্ট নিয়ম না থাকায় ডেটা সার্চ (অনুসন্ধান) করার সময় সমস্যা তৈরি হয়। যেমন একটি ক্লাসে শিক্ষার্থীরা যদি কোনো নিয়ম না মেনে এলোমেলোভাবে বসে, তবে নির্দিষ্ট কাউকে খুঁজে পেতে কষ্ট হয়। ডেটা স্ট্রাকচারের মূল উদ্দেশ্যই হলো ডেটাকে সঠিকভাবে সাজানো যাতে সহজে অনুসন্ধান, ইনসার্ট বা ডিলিট করা যায়।

২. বাইনারি সার্চ ট্রি (Binary Search Tree - BST):

• বাইনারি ট্রির সমস্যা সমাধানের জন্য বাইনারি সার্চ ট্রি ব্যবহার করা হয়। এর নিয়ম হলো—মূল বা রুট (Root) নোডের চেয়ে ছোট উপাদানগুলো বাম দিকে (Left Subtree) এবং বড় উপাদানগুলো ডান দিকে (Right Subtree) বসবে।
• একটি আদর্শ বা ব্যালেন্সড (Balanced) বাইনারি সার্চ ট্রির হাইট বা উচ্চতা হয় log n (যেখানে n হলো নোডের সংখ্যা)। উচ্চতা log n হলে সার্চ, ইনসার্ট ও ডিলিট করার জটিলতা বা টাইম কমপ্লেক্সিটি অনেক কমে যায়।

৩. BST-এর সমস্যা (Worst Case):

• কিন্তু BST-এর একটি বড় সমস্যা রয়েছে। যদি ডেটা একটি নির্দিষ্ট ক্রমানুসারে আসে (যেমন: ১০, ২০, ৩০, ৪০, ৫০), তবে ট্রিটি আর সাধারণ ট্রির মতো না থেকে একটি লিংকড লিস্টের (Linked List) মতো আচরণ করে।
• এটি যেকোনো একদিকে বৃদ্ধি পেতে থাকে, যাকে বলা হয় স্কিউড ট্রি (Skewed Tree)। ডান দিকে বাড়লে 'Right Skewed' এবং বাম দিকে বাড়লে 'Left Skewed' বলা হয়।
• এই অবস্থায় ট্রির উচ্চতা হয়ে যায় n এবং যেকোনো উপাদান সার্চ, ইনসার্ট বা ডিলিট করার টাইম কমপ্লেক্সিটি বেড়ে O(n) হয়ে যায়, যা অত্যন্ত ধীরগতির।

৪. AVL ট্রি (AVL Tree) কী?

• BST-এর এই ওর্স্ট কেস (Worst Case) বা চরম সমস্যা সমাধানের জন্যই ব্যালেন্সড বাইনারি সার্চ ট্রি বা AVL Tree-এর উৎপত্তি। তিনজন রাশিয়ান বিজ্ঞানী এটি আবিষ্কার করেন এবং তাঁদের নামানুসারেই এর নামকরণ করা হয়েছে।
• সম্পর্ক: সকল AVL ট্রিই হলো বাইনারি সার্চ ট্রি (BST), এবং সকল BST হলো বাইনারি ট্রি। কিন্তু এর উল্টোটা সবসময় সত্য নয়।

৫. ব্যালেন্স ফ্যাক্টর (Balance Factor - BF):

• একটি বাইনারি সার্চ ট্রি তখনই AVL ট্রি হবে যখন এর প্রতিটি নোড ব্যালেন্সড থাকবে। আর এটি পরিমাপ করা হয় ব্যালেন্স ফ্যাক্টরের মাধ্যমে।
• সূত্র: ব্যালেন্স ফ্যাক্টর (BF) = বাম সাব-ট্রির উচ্চতা (Height of Left Subtree) - ডান সাব-ট্রির উচ্চতা (Height of Right Subtree)।
• শর্ত: একটি ট্রির প্রতিটি নোডের ব্যালেন্স ফ্যাক্টরের মান অবশ্যই -১, ০, অথবা +১ হতে হবে। যদি এই তিনটি মানের বাইরে অন্য কিছু (যেমন: -২, ২ ইত্যাদি) আসে, তবে ট্রিটি আনব্যালেন্সড বা ভারসাম্যহীন হয়ে পড়বে।

৬. AVL ট্রির সুবিধা ও কার্যকারিতা:

• যদি কোনো ট্রির প্রতিটি নোডের ব্যালেন্স ফ্যাক্টর শর্ত মেনে চলে, তবে ট্রির সর্বোচ্চ উচ্চতা log n এর মধ্যে সীমাবদ্ধ থাকে।
• এর ফলে সার্চ, ইনসার্ট এবং ডিলিট—সব ধরনের অপারেশনের টাইম কমপ্লেক্সিটি সবসময় O(log n) থাকে।
• যদি কোনো কারণে ব্যালেন্স ফ্যাক্টর নিয়ম লঙ্ঘন করে, তবে বিভিন্ন রোটেশন (Rotation) বা কৌশলের মাধ্যমে সেটিকে পুনরায় AVL ট্রিতে রূপান্তর করতে হয় (যা পরবর্তী ভিডিওতে আলোচনা করা হবে)।