• بازدید : 62 views
  • بدون نظر
این فایل در ۳۰صفحه قابل ویرایش تهیه شده وشامل موارد زیر است:

در درخت متعادل BST متوسط تعداد مقايسه پايينتر خواهد بود؟
براي اينكه درخت را متعادل  نماييم:
بايد درخت را از نو بازسازي كنيم. صرف وقت
درخت را متوازن نگه داريم. 
اگرT يك درخت دودويي غير تهي با زير درختان سمت چپ و راست TLوTRباشد، آنگاه Tيك درخت متعادل از نظر ارتفاع است اگر و فقط اگر
TL و TR از نظر ارتفاع متعادل بوده و
۱<= |hL-hR| باشد كه در آن  hL و hR به ترتيب ارتفاع TRو  TL هستند.
ضريب تعادل يك گره مانند T ، (BF(T ، در يك درخت دودويي به صورتhL-hR   تعريف مي گردد. 

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

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

درخت‌های متوازن غالباً با درخت‌های قرمز-سیاه مقایسه می‌شود. دلیل آن این است که هر دو داده ساختار قادر به انجام یک مجموعه از عملیات یکسان می‌باشند و در درخت‌های قرمز-سیاه زمان لازم برای انجام عملیات اساسی به اندازه (O(log nاست. درخت‌های متوازن برای کاربردهای وسیع و گسترده جستجو بهتر از در خت‌های قرمز-سیاه هستند. الگوریتم‌های متوازن کردن درخت‌ها در بسیاری از دوره‌های علوم رایانه ظاهر شده و مورد استفاده قرار می‌گیرد
چرخشها توسط نزديك ترين جد A يك گره ي درج شده مانند Y كه ضريب تعادل آن ۲+ و ۲- است ، مشخص مي گردد.

LL : گره ي جديد Y در زير درخت چپ مربوط به زير درخت چپ A درج مي شود.
LR: Y در زير درخت راست مربوط به زير درخت چپ A درج مي شود.
RR: Y در زير درخت راست مربوط به زير درخت راست A درج مي شود.
RL: Y در زير درخت چپ مربوط به زير درخت راست A درج مي شود.
  LL و RR مانند LR و RL متقارن است 
هميشه ارتفاع زير درختي كه در چرخش شركت مي كند ، بدون تغيير باقي مي ماند.
براي انجام چرخش لازم است كه مكان گره A كه قرار است چرخش حول آن انجام گيرد تعيين شود

ضريب تعادل يك گره نمي تواند به ميزان ۲+ و ۲- تغيير كند، مگر انكه ضريب تعادل آن قبل از جايگذاري ۱+ و۱- باشد.
 بنابراين مي توان گفت كه گره A نزديكترين جد گره جديد است كه ضريب تعادل آن قبل از درج ۱+ و۱- مي باشد
زماني كه درج يك گره منجر به يك درخت نامتعادل نگردد، چه مساله اي رخ خواهد داد؟
اگر در پي يك درج درخت حالت نامتعادل پيدا نكند ، در اينصورت حتما مقدار جديد ضريب تعادل A برابر ۰ خواهد بود.
اگر جد A با ضريب توازن ۱+و يا ۱- وجود نداشته باشد، A را ريشه اختيار كنيد. 
ضريب هاي توازن گره ها از A به پدر گره ي جديد ، به ۱+ و۱- تغيير مي كند.

عتیقه زیرخاکی گنج