درخت AVL — به زبان ساده

۳۴۴۴ بازدید
آخرین به‌روزرسانی: ۲۲ شهریور ۱۴۰۲
زمان مطالعه: ۳ دقیقه
درخت AVL — به زبان ساده

اگر ورودی یک درخت جستجوی باینری به روشی مرتب باشد (نزولی یا صعودی) در این صورت ظاهری شبیه زیر خواهد داشت:

مشخص شده است که عملکرد سناریوی بدترین حالت برای درخت جستجوی باینری نزدیک به الگوریتم‌های جستجوی خطی است که همان (O(n است. در مورد داده‌های همزمان نمی‌توان الگوی داده‌ها و فراوانی‌های آن‌ها را پیش‌بینی کرد. بنابراین باید درخت‌های جستجوی باینری موجود مجدداً متعادل‌سازی شوند.

درخت‌های AVL که به نام خالقانشان Adelson, Velski و Landis نام‌گذاری شده‌اند، نوعی از درختان جستجوی باینری با ارتفاع متعادل هستند. درخت AVL سمت راست و چپ را بررسی کرده و تضمین می‌کند که زیردرخت راست و چپ اختلافی بیش‌تر از 1 واحد ندارند. این اختلاف به نام عامل تعادل (Balance Factor) نامیده می‌شود.

در ادامه می‌بینیم که درخت نخست متعادل است و دو درخت بعدی متعادل نیستند:

در مورد درخت دوم، زیردرخت چپ C ارتفاع 2 دارد و زیردرخت راست ارتفاع 0 دارد، بنابراین اختلاف برابر با 2 است. درخت سوم، زیردرخت راست A ارتفاع 2 دارد و زیردرخت چپ وجود ندارد و از این رو ارتفاعش 0 است و اختلاف بار دیگر 2 می‌شود. درخت AVL تنها امکان داشتن اختلاف (عامل تعادل) برابر با 1 را مجاز می‌شمارد.

 ارتفاع زیردرخت راست -  ارتفاع زیردرخت چپ = عامل تعادل

چرخش‌های AVL

درخت AVL برای این که خود را متعادل کنند، باید چهار نوع چرخش زیرا را اجرا کند:

  • چرخش چپ
  • چرخش راست
  • چرخش چپ-راست
  • چرخش راست-چپ

دو نوع چرخش اول، چرخش‌های منفرد هستند و دو نوع دوم چرخش‌های دوگانه محسوب می‌شوند. برای این که درخت متعادل باشد، باید دست‌کم درختی با ارتفاع 2 گره داشته باشیم. در چنین درخت ساده‌ای انواع مختلف چرخش‌ها را بررسی می‌کنیم.

چرخش چپ

اگر درختی نامتعادل شود، وقتی گرهی در زیردرخت راستِ زیردرخت راست درج شود، در این صوت یک چرخش به چپ منفرد اجرا می‌شود:

در مثال فوق گره A نامتعادل است، زیرا به عنوان یک گره در زیردرخت راستِ زیردرخت راست A درج شده است. با اجرای چرخش چپ باعث می‌شویم که گره A به زیردرخت چپ گره B تبدیل شود.

چرخش راست

درخت AVL در صورتی که یک گره در زیردرخت چپِ زیردرخت چپ درج شود نیز می‌تواند نامتعادل شود. در این صورت باید چرخش راست روی درخت اجرا شود:

همان طور که در تصویر فوق مشخص است، گره نامتعادل با اجرای چرخش راست، به فرزند راستِ فرزند چپ خود تبدیل می‌شود.

چرخش راست-چپ

چرخش‌های دوگانه نسخه پیچیده‌تری از چرخش‌های ساده هستند که در بخش قبلی بررسی کردیم. برای درک بهتر آن‌ها باید به عملیاتی که در هر مرحله از چرخش اجرا می‌شود توجه کنیم. ابتدا شیوه اجرای چرخش چپ-راست را بررسی می‌کنیم. چرخش چپ-راست ترکیبی از چرخش چپ و سپس چرخش راست است.

وضعیتعمل
Right Rotationیک گره در زیردرخت راستِ زیردرخت چپ ایجاد می‌شود. این امر موجب می‌شود که C یک گره نامتعادل شود. این سناریوها باعث می‌شوند که درخت AVL، چرخش چپ-راست را اجرا کند.
Left Rotationابتدا چرخش چپ روی زیردرخت چپ C اجرا می‌شود. این امر موجب می‌شود که A به زیردرخت چپ B تبدیل شود.
Left Rotationبا این وجود، گره C همچنان به دلیل وجود زیردرخت چپِ زیردرخت چپ نامتعادل است.
Right Rotationاینک چرخش راست را روی درخت اجرا می‌کنیم و گره B را به یک ریشه جدید این زیردرخت تبدیل می‌کنیم. در این مرحله C به زیردرخت راستِ زیردرخت چپ خود تبدیل می‌شود.
Balanced Avl Treeاینک درخت در وضعیت متعادل قرار دارد.

چرخش راست-چپ

نوع دوم از چرخش‌های دوگانه، چرخش راست-چپ است. این چرخش ترکیبی از چرخش راست و سپس چرخش چپ است.

وضعیتعمل
Left Subtree of Right Subtreeیک گره در سمت چپ زیردرخت راست این زیردرخت درج شده است. این امر موجب شده است که A به یک گره نامتعادل با عامل تعادل 2 تبدیل شود.
Subtree Right Rotationابتدا چرخش راست را روی گره C اجرا می‌کنیم و آن را به زیردرخت راست ِ زیردرخت چپ خودش یعنی B تبدیل می‌کنیم. اینک B زیردرخت راست A شده است.
Right Unbalanced Treeگره A همچنان نامتعادل است و دلیل این مسئله زیردرخت راستِ زیردرخت راست آن است که به یک چرخش چپ نیاز دارد.
Left Rotationیک چرخش چپ روی B اجرا می‌شود و آن را به گره ریشه زیردرخت تبدیل می‌کند. بدین ترتیب A به زیردرخت چپِ زیردرخت راست خودش (B) تبدیل می‌شود.
Balanced AVL Treeاینک درخت متعادل شده است.

بدین ترتیب این نوشته با موضوع معرفی درخت‌های AVL به پایان می‌رسد. هر گونه پیشنهاد یا دیدگاه خود را می توانید در بخش نظرات با ما و دیگر خوانندگان فرادرس در میان بگذارید.

اگر این نوشته مورد توجه قرار گرفته است، پیشنهاد می‌کنیم موارد زیر را نیز ملاحظه نمایید:

==

بر اساس رای ۲۳ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
tutorialspoint
۱ دیدگاه برای «درخت AVL — به زبان ساده»

عالی بود.استفاده بردم

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *