درخت ایویال
From Wikipedia, the free encyclopedia
الگوریتم یا علوم رایانه، درخت ایویال (به انگلیسی: AVL tree)، یک نوع درخت جستجوی دودویی خود متوازنکنندهاست و اولین ساختار دادهای از این نوع میباشد که اختراع شد.[1] در یک درخت ایویال اختلاف ارتفاع دو زیر شاخهٔ هر گره حداکثر برابر یک است؛ بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته میشود. توجه کنید که عملیات درج، حذف و جستجو در یک درخت ایویال در بدترین حالت و حالت متوسط به اندازه خواهد بود بهطوریکه n تعداد گرههای درخت میباشد. در عملیات درج و حذف ممکن است نیاز باشد که درخت به وسیله چرخش درختها، یک یا چند بار متوازن گردد.
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
درخت ایویال | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
گونه | درخت | ||||||||||||||||||||
سال اختراع | ۱۹۶۲ | ||||||||||||||||||||
مخترع | جرجی اندلسون-ولسکی و اوگنی لاندیس | ||||||||||||||||||||
زمان اجرای الگوریتم بر پایه نماد O بزرگ | |||||||||||||||||||||
|
عنوان AVL TREE از اول نامهای دو مخترع آن به نامهای G.M. Adelson-Velsky و E.M. Landis، که مقاله خود را در سال ۱۹۶۲ با موضوع «یک الگوریتم برای سازماندهی اطلاعات» منتشر کردند گرفته شدهاست.
درختهای ایویال غالباً با درختهای قرمز-سیاه مقایسه میشود. دلیل آن این است که هر دو داده ساختار قادر به انجام یک مجموعه از عملیات یکسان میباشند. در درختهای قرمز-سیاه نیز زمان لازم برای انجام عملیات اساسی به اندازه است. درختهای ایویال برای کاربردهای وسیع و گسترده جستجو بهتر از درختهای قرمز-سیاه هستند. الگوریتمهای متوازن کردن درختها در بسیاری از دورههای علوم رایانه ظاهر شده و مورد استفاده قرار میگیرد.[2]