AVL Tree রোটেশন ও Binary Heap অপারেশনস গাইড

মূল ধারণা (Core Concepts)

AVL ট্রি হলো একটি সেলফ-ব্যালেন্সিং বাইনারি সার্চ ট্রি যেখানে প্রতিটি নোডের ব্যালেন্স ফ্যাক্টর $\text{BF} = \text{Height(Left)} - \text{Height(Right)} \in \{-1, 0, +1\}$।

৪টি রোটেশন (Rotations)

1. LL Rotation (Single Right Rotation): বাম সন্তানের বামে নোড ঢুকলে রুটে ডানে ঘোরানো হয়।
2. RR Rotation (Single Left Rotation): ডান সন্তানের ডানে নোড ঢুকলে রুটে বামে ঘোরানো হয়।
3. LR Rotation (Double Rotation): বাম সন্তানের ডানে নোড ঢুকলে প্রথমে বাম সন্তানে Left Rotation, তারপর রুটে Right Rotation।
4. RL Rotation (Double Rotation): ডান সন্তানের বামে নোড ঢুকলে প্রথমে ডান সন্তানে Right Rotation, তারপর রুটে Left Rotation।

বাইনারি হিপের ইনডেক্সিং (0-Indexed Array)

• নোড $i$-এর প্যারেন্ট: $\lfloor (i - 1) / 2 \rfloor$
• বাম সন্তান: $2i + 1$
• ডান সন্তান: $2i + 2$

> ⚡ ৫-সেকেন্ড শর্টকাট (Exam Shortcut): > একটি অগোছালো অ্যারে থেকে ক্রমান্বয়ে উপাদান ইনসার্ট করলে হিপ তৈরিতে $O(n \log n)$ সময় লাগে; কিন্তু নিচের স্তর থেকে Bottom-up Heapify করলে মোট সময় লাগে মাত্র $O(n)$!

> ⚠️ পরীক্ষার ফাঁদ (Exam Trap): > পরীক্ষায় জিজ্ঞেস করা হয়: "উচ্চতা $h$ বিশিষ্ট AVL ট্রিতে সর্বনিম্ন নোড সংখ্যা কত?" মনে রাখবেন: $N(0) = 1, N(1) = 2, N(h) = N(h-1) + N(h-2) + 1$ (ফিবোনাচ্চি ধারার অনুরূপ)। $2^h - 1$ হলো সাধারণ বাইনারি ট্রির সর্বনিম্ন নয় বরং ফুল ট্রির নোড সংখ্যা!