موضوع مقاله: درخت ای‌وی‌ال | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درخت ای‌وی‌ال | مقدمه: الگوریتم یا علوم رایانه، درخت ای‌وی‌ال ، یک نوع درخت جستجوی دودویی خود متوازن‌کننده‌است و اولین ساختار داده‌ای از این نوع می‌باشد که اختراع شد.رابرت سدجویک، الگوریتم‌ها، ادیسون-ویسلی، ۱۹۸۳, ، صفحه ۱۹۹، فصل ۱۵: درخت‌های متوازن. | ## بخش 1: درخت ای‌وی‌ال | در یک درخت ای‌وی‌ال اختلاف ارتفاع دو زیر شاخهٔ هر گره حداکثر برابر یک است؛ بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته می‌شود. توجه کنید که عملیات درج، حذف و جستجو در یک درخت ای‌وی‌ال در بدترین حالت و حالت متوسط به اندازه خواهد بود به‌طوری‌که n تعداد گره‌های درخت می‌باشد. در عملیات درج و حذف ممکن است نیاز باشد که درخت به وسیله چرخش درخت‌ها، یک یا چند بار متوازن گردد. Landis، که مقاله خود را در سال ۱۹۶۲ با موضوع «یک الگوریتم برای سازماندهی اطلاعات» منتشر کردند گرفته شده‌است. دلیل آن این است که هر دو داده ساختار قادر به انجام یک مجموعه از عملیات یکسان می‌باشند. درخت‌های ای‌وی‌ال برای کاربردهای وسیع و گسترده جستجو بهتر از درخت‌های قرمز-سیاه هستند. الگوریتم‌های متوازن کردن درخت‌ها در بسیاری از دوره‌های علوم رایانه ظاهر شده و مورد استفاده قرار می‌گیرد. تعریف اولیه ضریب توازن هر گره، تفاضل ارتفاع زیردرخت چپ آن گره از ارتفاع زیردرخت راست آن گره است. با دانستن تعریف یک درخت ای‌وی‌ال و ضریب توازن، با اضافه شدن گره جدید و تغییر ارتفاع، می‌توان یک درخت ای‌وی‌ال را متوازن نگه داشت. در روش قدیمی برای هر گره دو بیت نگه داشته می‌شد ولی تحقیقات بعدی نشان داد که تنها یک بیت برای هر گره کافی است. به این صورت که برای در هر گره تفاضل ارتفاع گره با از ارتفاع پدرش ذخیره می‌شود و همان‌طور که واضح است این مقدار همواره برابر ۱ یا ۲ است. ارتفاع هر درخت ای‌وی‌ال با تعداد n گره همواره در محدوده زیر قرار دارد: که در آن با تعریف عدد طلایی ، و . | ## بخش 2: درخت ای‌وی‌ال | دلیل این محدوده این است که هر درخت ای‌وی‌ال با ارتفاع h، حداقل به تعداد Fh+2 – 1 گره دارد که در آن F دنباله فیبوناتچی است. درج کردن اگر ضریب توازن تمام گره‌ها ۱-، ۰ یا ۱ باشد درخت در حال حاضر متوازن است و هیچ چرخش دیگری نیاز ندارد. اگر ضریب توازن یک گره ۲ یا ۲- شود، درخت با ریشه این گره نامتوازن است و چرخش درخت نیاز است. چهار حالت اساسی برای محاسبه وجود دارد که دو تای آن‌ها متناسب، یا به عبارت دیگر متقارن با دو حالت دیگر است. برای سادگی ریشه زیر درخت نامتوازن را P، فرزند سمت راست آن را R، و فرزند سمت چپ را L بنامید. اگر ضریب توازن P مساوی ۲ بود یعنی زیر درخت سمت راست سنگین تر از زیر درخت سمت چپ است و باید ضریب توازن فرزند سمت راست بررسی شود. اگر ضریب توازن (R)برابر ۱ است، این بدان معنا است که درج در سمت راست آن گره رخ داده و یک چرخش درخت به چپ با محوریت ریشه P است. اگر ضریب توازن R برابر ۱- باشد، این بدان معنا است که درج در سمت چپ گره اتفاق افتاده‌است. اولین چرخش به سمت راست با محوریت R به عنوان ریشه و سپس یک چرخش به سمت چپ با محوریت P است. در غیر این صورت آن را با بزرگ‌ترین گره در زیر درخت سمت چپش یا با کوچک‌ترین گره در زیر درخت سمت راستش جایگزین می‌کنیم و محل جایگزینی را به خاطر می‌سپاریم. سپس آن گره را (که حالا حداکثر یک بچه دارد) در محل جایگزینی به راحتی حذف می‌کنیم. بعد از حذف گره مسیری را که از سمت محل جایگزینی به طرف ریشه است را پیمایش می‌کنیم و ضریب‌های توازن را در صورت لزوم اصلاح می‌کنیم. | ## بخش 3: درخت ای‌وی‌ال | اگر در طول مسیر در یک گره ضریب توازن ۲ یا ۲- شود؛ این بدان معنا است که زیر درخت با ریشه آن گره نامتوازن است و برای متوازن شدن نیاز به چرخش می‌باشد. هزینه صرف شده برای حذف کردن برابر جمع هزینه‌های لازم برای جستجو و بازیابی مسیر است که هر دو به اندازه می‌باشد. هیچ شرط خاصی برای رعایت کردن وجود ندارد و در طول جستجو ساختار درخت تغییری نمی‌کند. (می توان جستجو در درخت ای‌وی‌ال را در تباین با جستجو در درخت گسترده دانست که در آن ساختار درخت در حین جستجو تغییر می‌کند) اگر هر گره ارتفاع زیر درخت خود را نیز ذخیره کند، هر گره می‌تواند در زمان نیز بازیابی شود. متوازن‌سازی اگر در هنگام اجرای یک عملیات (درج یا حذف) روی یک درخت ای‌وی‌ال ضریب توازن یک گره ۲ یا ۲- شود، (از محدوده مجاز ۱ تا ۱- خارج شود) آن درخت نیازمند عمل متوازن‌سازی خواهدبود. فرض کنید گره ای که ضریب توازنش از محدوده مجاز خارج شده‌است X و فرزند بزرگتر آن (با ارتفاع بیشتر) Z باشند. علت عدم توازن X در عمل درج، اضافه شدن یک نود به Z، و در عمل حذف، حذف شدن یک نود از بچه‌های برادر Z است. در دو حالت اول (راست راست و چپ چپ) نیاز به تک-چرخش و در دو حالت دیگر نیاز به دو-چرخش است. همان‌طور که مشاهده می‌شود با تغییر سه یال و به روز رسانی دو ضریب توازن، این درخت دوباره متوازن شده‌است. در چرخش چپ، همان‌طور که ملاحظه می‌شود، گره‌های سمت راست X و چپ Z تغییری نمی‌کنند. در این حالت ابتدا با جابحا کردن Y و Z به یکی از حالات چپ چپ یا راست راست می‌رسیم و سپس با یک چرخش درخت را متوازن می‌کنیم. | ## جمع‌بندی | برای یک درخت به سایز n: ارتفاع درخت ای‌وی‌ال محدود می‌شود به: ارتفاع درخت قرمز-سیاه محدود می‌شود به: درخت ای‌وی‌ال دارای توازن بیشتری نسبت به درخت قرمز-سیاه‌است یا به عبارت دیگر بسیار متوازن تر از درخت قرمز-سیاه‌است، که این منجر به این می‌شود که حذف و درج کردن به صورت کند، اما بازیابی در زمان سریع تری انجام شود.