درخت ای وی ال

برای دیگر کاربردها، AVL (ابهام‌زدایی) را ببینید.

در علم رایانه، درخت متوازن، یک نوع درخت جستجوی دودویی خود متوازن کننده‌است و اولین ساختار داده‌ای می‌باشد که اختراع شد. در یک درخت متوازن ارتفاع هر دو فرزند زیر درخت هر گره با حداکثر یکی تفاوت می‌کند، بنابراین به این درخت، درخت با ارتفاع متوازن نیز گفته می‌شود. توجه کنید که عملیات درج، حذف در یک درخت متوازن در بدترین حالت و حالت متوسط به اندازه (O(log nخواهد بود به طوری که n تعداد گرهای درخت می‌باشد. در عملیات درج و حذف ممکن است نیاز باشد که درخت به وسیله چرخش درخت‌ها، یک یا چند بار متوازن گردد.

عنوان AVL TREE از اول نام‌های دو مخترع آن به نام‌های G.M. Adelson-Velsky و E.M. Landis، که مقاله خود را در سال ۱۹۶۲ با موضوع«یک الگوریتم برای سازماندهی اطلاعات» منتشر کردند گرفته شده‌است.

فاکتور توازن هر گره به صورت تفاوت بین ارتفاع زیر درخت چپ گره از ارتفاع زیر درخت راست آن گره تعریف می‌شود و هر گره با فاکتور توازن ۱، ۰و-۱ به صورت گره متوازن شده در نظر گرفته می‌شود. یک گره با هر فاکتور توازن دیگری غیر از انچه ذکر شد، یک گره نامتوازن تلقی می‌شود و در نتیجه نیاز به متوازن کردن مجدد درخت می‌باشد. فاکتور توازن یا صورت مستقیم در گره و یا از طریق ارتفاع زیر درخت محاسبه می‌شود.

درخت‌های متوازن غالبا با درخت‌های قرمز-سیاه مقایسه می‌شود. دلیل آن این است که هر دو داده ساختار قادر به انجام یک مجموعه از عملیات یکسان می‌باشند و در درخت‌های قرمز-سیاه زمان لازم برای انجام عملیات اساسی به اندازه (O(log nاست. درخت‌های متوازن برای کاربردهای وسیع و گسترده جستجو بهتر از در خت‌های قرمز-سیاه هستند. الگوریتم‌های متوازن کردن درخت‌ها در بسیاری از دوره‌های علوم کامپیوتر ظاهر شده و مورد استفاده قرار می‌گیرد.

عملیات

به طور کلی عملیات اساسی در درخت‌های متوازن شامل همان عملیاتی که در درختهای جستجوی دودویی انجام می‌شود می‌باشد، اما اصلاحات وتغییرات به صورت فراخوانی یک یا چند باره چرخش درخت خواهد بود که به باز ذخیره کردن ارتفاع زیر درخت کمک می‌کند.

درج کردن

توصيف تصويري متوازن كردن درخت توسط چرخش هاويك مرحله از مسير بازيابي يه سمت ريشه يراي اصلاح فاكتور توازن گره‌ها.

اگر فاکتور توازن ۱-، ۰ یا ۱ باشد درخت در حال حاضر در حالت متوازن است و هیچ چرخش دیگری نیاز ندارد.

اگر فاکتور توازن ۲ یا -۲ شود، درخت با ریشه این گره نا متوازن است ویک چرخش درخت نیاز است. حد اکثر یک یا دو چرخش برای متوازن کردن درخت نیاز خواهد بود.

چهار حالت اساسی برای محاسبه وجود دارد که دو تای آنها متناسب، یا به عبارت دیگر متقارن با دو حالت دیگر است. برای سادگی ریشه زیر در خت نا متوازن را P، فرزند سمت راست آن را R، و فزند سمت چپ را L بنامید. اگر فاکتور توازنP مساوی ۲ بود یعنی زیر درخت سمت راست سنگین تر از زیر درخت سمت چپ است وبایدفاکتور توازت فرزند سمت راست بررسی شود. اگر فاکتور توازن (R)برابر ۱ است، این بدان معنا است که درج در سمت رایت آن گره رخ داده و یک چرخش درخت به چپ با محوریت ریشه P است. اگر فاکتور توازن R برابر ۱- باشد، این بدان معنا است که درج در سمت چپ گره اتفاق افتاده‌است. در این حالت نیاز به دو بار چرخش می‌باشد. اولین چرخش به سمت راست با محوریت R به عنوان ریشه وسپس یک چرخش به سمت چپ با محوریت P است.

حذف کردن

اگر گره یک برگ باشد می‌توان آن را حذف کرد. در غیر این صورت آن را با بزرگ‌ترین گره در زیر در خت سمت چپش یا با کوچک‌ترین گره در زیر درخت سمت راستش جایگزین می‌کنیم. گره جایگزین حداکثر یک زیر در خت دارد. بعد از حذف گره مسیری که از سمت پدر گره جایگزین به طرف ریشه‌است را پیمایش می‌کنیم و فاکتورهای توازن را در صورت لزوم اصلاح می‌کنیم.(این عمل را بازیابی مسیر می‌نامیم). بازیابی مسیر تا زمانی که فاکتور توازن ۱ یا ۱- شود ادامه پیدا می‌کند. اگر فاکتور تواز ن ۱ یا۱-باشدغ‌این بدان معنا است که ارتفاع زیر در خت بدون تغییر باقی مانده‌است. اگر فاکتور توازن صفر شود، یعنی ارتفاع زیر درخت یک واحد کم شده‌است وبازیابی مسیر باید ادامه یابد. اگر فاکتور توازن ۲ یا -۲ شود ؛، این بدان معنا است که زیر درخت نا متوارن است وبرای متوازن شدن نیاز به چرخش می‌باشد. اگر چرخش فاکتور توارن زیر درخت را صفر کند بازیابی مسیر تا زمان که ارتفاع زیر در خت یک واحد کم شود ادامه می‌یابد. هزینه صرف شده برای حذف کردن برابر جمع هزینه‌های لازم برای جستجو و بازیابی مسیر است که هر دو به اندازه (O (logn می‌باشد. در نتیجه هزینه لازم برای حذف نیز از مرتبه (O (logn می‌باشد.

جستجو

جستجو در درخت متوازن همانند جستجو در در خت دودویی نا متوازن است. به دلیل توازن ارتفاع درخت هزینه جستجو برابر (O(logn است. هیچ شرط خاصی برای رعایت کردن وجود ندارد و در طول جستجو ساختار در خت تغیری نمی‌کند.(می توان جستجو در درخت متوازن را در تباین با جستجو در درخت گسترده دانست که در آن ساختار درخت درحین جستجو تغییر می‌کند.) اگر هر گره ارتفاع زیر درخت خود را نیز ذخیره کند، هر گره می‌تواند در زمان (O (logn نیز باز یابی شود. گره قبل و بعد هر گره در درخت متوازن در یک زمان ثابت سرشکن قابل دسترسی است. در موارد محدودی حدود (۲logn)پیوند پیمایش می‌شود. در اکثر موارد یک پیوند و در حالت متوسط دو پیوند پیمایش می‌شود.^{[نیازمند منبع]}

مقایسه باداده ساختارهای دیگر

درخت‌های متوازن و قرمز-سیاه، هر دو از نوع درخت‌های جستجوی دودویی خود متوازن کننده هستند، بنا براین از نظر قانون ریاضی تفاوتی ندارند. عملیات برای متوازن کردن آنها متفاوتند اما هر دو در زمان ثابتی انجانم می‌شوند. تفاوت بین آ نها در میزان ارتفاعشان است. برای یک درخت به سایز n:

• ارتفاع درخت متوازن محدود می‌شود به: $1.44 \cdot \log(n)$
• ارتفاع درخت قرمز-سیاه محدود می‌شود به:$2 \cdot \log(n)$

درخت متوازن دارای توازن بیشتری نسبت به درخت قرمز-سیاه‌است یا به عبارت دیگر بسیار متوازن تر از درخت قرمز-سیاه‌است، که این منجر به این می‌شود که حذف و درج کردن به صورت کند، اما بازیابی در زمان سریع تری انجام شود.

جستارهای وابسته

• درخت‌ها
• چرخش درخت
• درخت گسترده
• درخت قرمز-سیاه
• درخت بی
• درخت تی
• لیست ساختمان‌های داده

منابع

• ویکی‌پدیای انگلیسی:

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 458–475 of section 6.2.3: Balanced Trees.

پیوند به بیرون

• توصیفی از الگورینم‌ها و ساختمان‌های داده
• آموزش تصویری عملیات روی درخت متوازن

پیاده سازی‌ها

• فایل سرآغاز به زبان C توسط اییان پییومارتا