درخت متوازن (AVL)
درخت AVL: فاکتور توازن، چرخش‌های چهارگانه برای متوازن‌سازی و تضمین O(log n) در همه حالات
مشکل BST و راه‌حل AVL
دیدیم که BST با داده مرتب به لیست کج تبدیل می‌شود. درخت AVL (نام‌گذاری به افتخار مخترعانش: Adelson-Velsky و Landis) اولین درخت خودمتوازن‌شونده است: بعد از هر درج/حذف، توازن را چک و در صورت لزوم با چرخش اصلاح می‌کند — پس همیشه O(log n)!
فاکتور توازن
برای هر گره:
Balance Factor = ارتفاع(چپ) − ارتفاع(راست)| فاکتور توازن | وضعیت |
|---|---|
| −۱، ۰، +۱ | متعادل ✓ |
| بیشتر از +۱ | چپ‌سنگین ✗ |
| کمتر از −۱ | راست‌سنگین ✗ |
چهار حالت عدم توازن و چرخش‌ها
- چپ‌سنگین چپ (LL): یک چرخش راست
- راست‌سنگین راست (RR): یک چرخش چپ
- چپ‌سنگین راست (LR): اول چرخش چپ فرزند، بعد چرخش راست
- راست‌سنگین چپ (RL): اول چرخش راست فرزند، بعد چرخش چپ
چرخش راست — شهود
گره ۲۰ به بالا می‌آید و ۳۰ به راستش می‌رود؛ ترتیب BST حفظ می‌شود! چرخش‌ها عملیات O(1) هستند و ساختار مرتب را خراب نمی‌کنند.
مزایای AVL
- جستجو سریع‌تر از Red-Black (توازن سخت‌گیرانه‌تر)
- تضمین O(log n) برای همه عملیات
- مناسب برای داده‌های جستجوی زیاد و درج/حذف کم
معایب
- چرخش‌های بیشتر در درج/حذف (نسبت به Red-Black)
- پیاده‌سازی پیچیده‌تر
نکته: در عمل، Red-Black Tree (با توازن ملایم‌تر) در کتابخانه‌های استاندارد رایج‌تر است (مثل map در C++)؛ اما AVL مفهوم متوازن‌سازی را گویاتر نشان می‌دهد.
جمع‌بندی
- AVL = BST + خودمتوازنی با چرخش
- فاکتور توازن هر گره باید −۱، ۰ یا +۱ باشد
- چهار الگوی عدم توازن: LL، RR، LR، RL
- نتیجه: تضمین O(log n) حتی با داده مرتب
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.