عامل تعادل یک مفهوم کلیدی در درختان AVL است، نوعی از درخت جستجوی باینری خودبالینگ کمک می کند تا ارتفاع درخت را حفظ کند و عملیات کارآمد مانند جستجو، قرار دادن و حذف را تضمین کند.

عامل تعادل چیست؟

عامل تعادل گره در یک درخت AVL تفاوت بین ارتفاع های زیردرخت چپ و راست آن است.

عامل درجه بندی = بلندی های زیردرخت چپ – بلندی های زیردرخت راست

عامل تعادل گره می تواند -1، 0 یا 1 برای درخت متعادل باشد، اگر عامل تعادل از این ارزش ها فراتر رود، درخت نیاز به تعادل از طریق چرخش دارد.

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

برای تعیین فاکتور تعادل، ابتدا ارتفاع هر زیردرخت ریشه در کودکان گره را پیدا کنید. ارتفاع تعداد لبه ها در طولانی ترین مسیر از گره به یک برگ است.

به عنوان مثال، اگر زیردرخت چپ دارای ارتفاع 3 باشد و زیردرخت راست دارای ارتفاع 1 باشد، عامل تعادل 2 است که نشان می دهد گره نامتعادل است و نیاز به چرخش دارد.

برنامه های کاربردی از فاکتور تعادل

عامل تعادل در هنگام قرار دادن و حذف برای حفظ تعادل درخت AVL استفاده می شود، زمانی که یک عامل تعادل گره خارج از محدوده -1 تا 1 چرخش برای بازگرداندن تعادل انجام می شود.

  • تک تک تک تک تک تک تک تک Rights
  • تک تک چپی
  • چپ راست (چپ)
  • سمت راست چپ

این عملیات به حفظ ارتفاع درخت حداقل، اطمینان از عملکرد بهینه برای عملیات جستجو کمک می کند.