درخت AVL
AVL TreeAVL یک BST خودمتعادل‌شونده است که اختلاف ارتفاع زیر‌درخت چپ و راست هر Node را حداکثر 1 نگه می‌دارد و با Rotation تعادل را برمی‌گرداند.
اول این مفهوم را در ذهن نگه دار
AVL یک BST خودمتعادل‌شونده است که اختلاف ارتفاع زیر‌درخت چپ و راست هر Node را حداکثر 1 نگه می‌دارد و با Rotation تعادل را برمی‌گرداند.
چطور کار می‌کند؟ ساده و مرحله‌ای
بعد از insert/delete هنگام برگشت به سمت root ارتفاع‌ها به‌روزرسانی می‌شوند.
اگر balance factor از محدوده خارج شود، با یکی از rotationهای LL/RR/LR/RL تعادل اصلاح می‌شود.
الگوریتم را به شکل تصمیم‌های پشت سر هم بخوان
Invariant اصلی ساختار را مشخص کن.
مسیر read/update را در ساختار دنبال کن.
بعد از mutation قبل از return invariant را دوباره برقرار کن.
یک ورودی خیلی کوچک را دستی اجرا کن و بعد از هر عملیات مهم state را بنویس. برای درخت AVL هدف این است که invariant را ببینی، نه اینکه کد را حفظ کنی.
O(log n)
این Complexity را حفظی نگو. اول مشخص کن مربوط به کدام عملیات یا بعد ورودی است؛ بعد هزینه را از روی loopها، عمق recursion، عملیات ساختمان داده و فرض‌های preprocessing نتیجه بگیر.
موارد مناسب
- وقتی عملیات غالب برنامه با نقاط قوت این ساختار هماهنگ است از آن استفاده کن.
- علاوه بر Big-O، هزینه حافظه را هم مقایسه کن.
کجا معمولاً اشتباه می‌کنیم؟
- پیچیدگی را بدون فهم representation حفظ نکن.
- بدترین شکل ساختار یا هزینه resize/rebalance را نادیده نگیر.
مدل یک پاسخ حرفه‌ای
مقایسه مهم: AVL سخت‌گیرانه‌تر متعادل است و برای lookup زیاد جذاب است؛ Red-Black معمولاً هنگام update rotation کمتری لازم دارد.
درخت AVL چه مسئله‌ای را حل می‌کند؟
AVL یک BST خودمتعادل‌شونده است که اختلاف ارتفاع زیر‌درخت چپ و راست هر Node را حداکثر 1 نگه می‌دارد و با Rotation تعادل را برمی‌گرداند.
درباره Complexity چه چیزی باید بگویم؟
پیچیدگی معمول اینجا O(log n) است، اما جواب کامل باید این هزینه را به representation، constraint ورودی و عملیات غالب وصل کند.
رایج‌ترین اشتباه چیست؟
پیچیدگی را بدون فهم representation حفظ نکن.