Table of Contents
درختان جستجوی باینری متعادل ساختارهای داده ای هستند که داده های مرتب شده را حفظ می کنند و عملیات کارآمد مانند جستجو، قرار دادن و حذف دو نوع مشترک، درختان AVL و درختان قرمز رنگ هستند که هر کدام دارای اصول متعادل سازی منحصر به فرد هستند که عملکرد را بهینه می کنند.
درختان AVL
درختان AVL درختان جستجوی باینری خود را بالا می برند که در آن تفاوت در ارتفاع بین زیردرخت های چپ و راست هر گره در بیشتر موارد یکی است.این تعادل سخت زمان جستجوی سریع تر را تضمین می کند اما نیاز به چرخش بیشتر در هنگام قرار دادن و حذف تعادل دارد.
هنگامی که یک گره پس از عمل نامتعادل می شود، چرخش برای بازگرداندن مالکیت AVL انجام می شود، این چرخش ها شامل چرخش های تک و دو است که به حفظ محدودیت های تفاوت ارتفاع کمک می کند.
درختان سرخ
درختان قرمز سیاه نوعی درخت جستجوی باینری خود بالدار هستند که رنگ (قرمز یا سیاه) را به هر گره اختصاص می دهد.قوانین رنگ آمیزی اطمینان حاصل می کنند که درخت تقریبا متعادل است، بدون هیچ راهی از ریشه به برگ بیش از دو برابر بیشتر از هر دو برابر است.
ویژگی های کلیدی شامل:
- هر گره یا قرمز یا سیاه است.
- ریشه همیشه سیاه است.
- گره های قرمز نمی توانند کودکان قرمز داشته باشند.
- هر مسیر از یک گره به برگ های نسل آن شامل تعداد گره های سیاه است.
این خواص اجازه می دهد تا درختان قرمز رنگ به انجام قرار دادن و حذف به طور موثر در حالی که حفظ تعادل از طریق رنگ آمیزی و چرخش.
مقایسه درختان AVL و قرمز
هر دو AVL و درختان قرمز هدف حفظ تعادل درخت برای عملکرد بهینه هستند.درخت AVL تمایل به متعادل تر شدن دارند، ارائه ظاهر سریع تر، اما ممکن است نیاز به چرخش بیشتر در طول به روز رسانی درختان قرمز کمتر سخت تر، ارائه ورودی سریع تر و حذف با نگاه کمی کندتر.