لطفا به نکات زیر در هنگام خرید دانلود پاورپوینت درخت AVL توجه فرمایید.

1-در این مطلب، متن اسلاید های اولیه دانلود پاورپوینت درخت AVL قرار داده شده است 2-به علت اینکه امکان درج تصاویر استفاده شده در پاورپوینت وجود ندارد،در صورتی که مایل به دریافت  تصاویری از ان قبل از خرید هستید، می توانید با پشتیبانی تماس حاصل فرمایید 3-پس از پرداخت هزینه ، حداکثر طی 12 ساعت پاورپوینت خرید شده ، به ادرس ایمیل شما ارسال خواهد شد 4-در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل اسلاید ها میباشد ودر فایل اصلی این پاورپوینت،به هیچ وجه بهم ریختگی وجود ندارد 5-در صورتی که اسلاید ها داری جدول و یا عکس باشند در متون زیر قرار نخواهند گرفت

اسلاید ۱ :

درخت BST متعادل

lدر درخت متعادل BST متوسط تعداد مقايسه پايينتر خواهد بود؟

lبراي اينكه درخت را متعادل  نماييم:

–بايد درخت را از نو بازسازي كنيم. صرف وقت

–درخت را متوازن نگه داريم.

اسلاید ۲ :

تعريف بازگشتي درخت متعادل دودويي

lاگرT يك درخت دودويي غير تهي با زير درختان سمت چپ و راست TLوTRباشد، آنگاه Tيك درخت متعادل از نظر ارتفاع است اگر و فقط اگر

–TL و TR از نظر ارتفاع متعادل بوده و

–۱<= |hL-hR| باشد كه در آن  hL و hR به ترتيب ارتفاع TRو  TL هستند.

 

اسلاید ۳ :

ضريب تعادل

lضريب تعادل يك گره مانند T ، (BF(T ، در يك درخت دودويي به صورتhL-hR   تعريف مي گردد.

l

lبراي هر گره T در درخت باينري متعادل، BF(T) برابر با ۱- و ۰ و ۱ است.

l

اسلاید ۴ :

انواع چرخش

lچرخشها توسط نزديك ترين جد A يك گره ي درج شده مانند Y كه ضريب تعادل آن ۲+ و ۲- است ، مشخص مي گردد.

l

lLL : گره ي جديد Y در زير درخت چپ مربوط به زير درخت چپ A درج مي شود.

lLR: Y در زير درخت راست مربوط به زير درخت چپ A درج مي شود.

lRR: Y در زير درخت راست مربوط به زير درخت راست A درج مي شود.

lRL: Y در زير درخت چپ مربوط به زير درخت راست A درج مي شود.

l  LL و RR مانند LR و RL متقارن است .

اسلاید ۵ :

انواع چرخش

lهميشه ارتفاع زير درختي كه در چرخش شركت مي كند ، بدون تغيير باقي مي ماند.

lبراي انجام چرخش لازم است كه مكان گره A كه قرار است چرخش حول آن انجام گيرد تعيين شود.

اسلاید ۶ :

نكات انواع چرخش

lضريب تعادل يك گره نمي تواند به ميزان ۲+ و ۲- تغيير كند، مگر انكه ضريب تعادل آن قبل از جايگذاري ۱+ و۱- باشد.

l بنابراين مي توان گفت كه گره A نزديكترين جد گره جديد است كه ضريب تعادل آن قبل از درج ۱+ و۱- مي باشد.

اسلاید ۷ :

نكات انواع چرخش

lزماني كه درج يك گره منجر به يك درخت نامتعادل نگردد، چه مساله اي رخ خواهد داد؟

lاگر در پي يك درج درخت حالت نامتعادل پيدا نكند ، در اينصورت حتما مقدار جديد ضريب تعادل A برابر ۰ خواهد بود.

lاگر جد A با ضريب توازن ۱+و يا ۱- وجود نداشته باشد، A را ريشه اختيار كنيد.

lضريب هاي توازن گره ها از A به پدر گره ي جديد ، به ۱+ و۱- تغيير مي كند.

اسلاید ۸ :

ارتفاع درخت AVL

lاگر h ارتفاع درخت قبل از جايگذاري باشد ، آنگاه زمان لازم براي درج يك شناسه جديد برابر  O(h) خواهد بود.

   كه همان زمان درختهاي جستجوي دودويي نامتوازن است.

   اگرجه اكنون سربار آن بصورت قابل توجهي بيشتر است.

lدر مورد درخت  AVL ،h حداكثر مي تواند O(log n) باشد.از ابن رو زمان عمل درج در بد ترين حالت برابر O(log n) است.