درخت AVL در پایتون (AVL Tree in Python)

در این قسمت تیم کدگیت را با آموزش درخت AVL در پایتون همراهی کنید. در این جلسه به معرفی یکی دیگر از ساختار داده‌ها خواهیم پرداخت. با معرفی درخت AVL کار خود را آغاز کرده و در ادامه به پیاده سازی این درخت در پایتون خواهیم پرداخت. پیشنهاد می‌کنیم قبل از مطالعه این جلسه، آموزش‌های زیر را بررسی کنید:

درخت AVL

عملیات‌های درج گره و حذف گره در درخت دودویی جست‌جو به طور معمول O(logn) است. اما درخت جستجوی دودویی زیر را ببینید:

درخت AVL در پایتون

در این شرایط حذف و اضافه کردن گره زمان O(n) می‌گیرد. اگر در درخت فوق پس از هر حذف و یا اضافه کردن درخت، ما تضمین کنیم ارتفاع درخت log n است پس هزینه درج و حذف همانطور که انتظار داریم Log n خواهد بود (در بدترین حالت). درخت AVL نوعی درخت جستجوی باینری با ارتفاع متعادل است بدین معنی که تضمین می‌کند ارتفاع درخت همیشه O(logn) است.

در این آموزش تنها به توضیح و پیاده سازی عملیات درج گره در درخت AVL خواهیم پرداخت. در جلسات آینده عملیات‌های مانند حذف و … نیز توضیح داده می‌شود.

درج گره در درخت AVL

برای درج گره در درخت AVL ابتدا همانند BST عمل کرده و گره را در درخت درج می‌کنیم. سپس با عملیاتی (که توضیح خواهیم داد) ارتفاع درخت را متعادل می‌کنیم. برای متعادل کردن ارتفاع درخت AVL ما نیاز به عملیات‌هایی به نام چرخش راست و چرخش چپ داریم. تصویر زیر این چرخش‌ها را به صورت ساده نمایش داده است:

درخت AVL در پایتون

مطابق با تصویر فوق متغیر‌های T1 و T2 و T3 فرزندان درختی هستند که ریشه آن گره X یا Y است. دقت کنید چرخش چپ و راست به صورت همزمان در یک تصویر آورده شده است.

برای درج گره در درخت AVL، مانند درخت BST عمل کرده و گره را وارد درخت می‌کنیم. پس از وارد کردن گره بررسی می‌کنیم درخت ما شرط AVL را دارد (متعادل هست یا خیر). برای ایجاد تعادل در درخت AVL حالات زیر در درخت رخ خواهد داد:

  • Y فرزند چپ z و x فرزند چپ y است:
درخت AVL در پایتون
  • Y فرزند چپ z و x فرزند راست y است:
درخت AVL در پایتون
  • Y فرزند راست z و x فرزند راست y است:
درخت AVL در پایتون
  • Y فرزند راست z و x فرزند چپ y است:
درخت AVL در پایتون

پیاده سازی درخت AVL در پایتون

برای پیاده سازی درخت AVL در پایتون همانند پیاده سازی درخت BST یک کلاس Node ایجاد می‌کنیم(در اینجا نام کلاس TreeNode قرار دادیم). سورس این کلاس مانند درخت BST بوده و تنها برای نگهداری ارتفاع گره‌ها متغیری به نام Height به آن اضافه کردیم. کد کلاس TreeNode به صورت زیر است:

حال نوبت به پیاده سازی درخت است. ابتدا کد درخت AVL را با هم ببینیم:

بیشتر بخوانید:  ساخت تصویر معکوس در پایتون (Mirror Image)

توابع و متغیر‌های استفاده شده در کد بالا به صورت زیر می‌باشد:

  • تابع getHeight: ارتفاع یک گره در درخت را برمی‌گرداند.
  • تابع insert: تابع insert به صورت بازگشتی یک گره را در دخت اضافه می‌کند.
  • تابع getBalance: این تابع یک گره را به عنوان ورودی می‌گیرد و اختلاف زیردرخت راست و چپ آن را بر‌میگرداند. وقتی این تابع عدد بزرگتر از 1 را برمی‌گرداند بدین معنی است که درخت متعادل نیست و ما با چرخش (چرخش راست یا چرخش چپ سپس چرخش راست) نیاز داریم. در صورتی که عدد کوچکتر از -1 برگردانده شود یعنی ما در شرایط عکس حالت قبل هستیم.
  • تابع leftRotate: این تابع چرخش چپ را انجام می‌دهد.
  • تابع rightRotate: این تابع چرخش راست را انجام می‌دهد.
  • تابع Inorder: این تابع برای پیمایش درخت می‌باشد. از این متد برای چاپ گره‌های درخت در این مثال استفاده خواهد شد.

تست برنامه

برای تست کدهای بالا، کد زیر را پیاده سازی کنید:

خروجی کد بالا به صورت زیر است:

بیشتر بخوانید:  Tuple در پایتون (Tuple in python Language)

اگر سوالی در خصوص درخت AVL دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.

    پسورد: www.codegate.ir

    دیدگاهتان را بنویسید

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