سلام
عمق BSTدر حالت متوسط [tex]O(n\: \log n)[/tex] هست یا [tex]O(\: \log n)[/tex]؟؟؟
دوست عزیز عمق درخت bst در بدترین حالت می تونه چی باشه؟
n باشه دیگه که میشه درخت مورب
خوب nlogn که بزرگتر از n
پس در حالت متوسط
logn هستش موفق باشید.
(۱۵ دى ۱۳۹۳ ۰۱:۳۲ ب.ظ)Hamid_0311 نوشته شده توسط: دوست عزیز عمق درخت bst در بدترین حالت می تونه چی باشه؟اره میدونم،یجا nlognدیدم!!!واسه همین شک کردم!!
n باشه دیگه که میشه درخت مورب
خوب nlogn که بزرگتر از n
پس در حالت متوسط
logn هستش موفق باشید.
مرسی.
(۱۵ دى ۱۳۹۳ ۰۱:۳۲ ب.ظ)Hamid_0311 نوشته شده توسط: دوست عزیز عمق درخت bst در بدترین حالت می تونه چی باشه؟
n باشه دیگه که میشه درخت مورب
خوب nlogn که بزرگتر از n
پس در حالت متوسط
logn هستش موفق باشید.
===============
درخت بی اس تی یک ساختمان داده برای جستجوی می باشد که به طور مثال در گوگل برای جستجوها از ان برای افزایش سرعت استفاده میکنند
bst در بدترین حالت ارتفاعش با درج متوالی اگر لیست ورودی صعودی یا نزولی باشد مورب شده وارتفاعش n می شود
اما در حالت عادی ارتفاعش h میباشد که اگر درخت متوازن شود میشه log اگر مورب بود میشه n
اما اقایان ادلسون و ولسکی دونفر روسی اومدن روی بی اس تی کار کردن و درخت رو متوازن کردن درختی که حداکثر ارتفاع دو زیر درخت چپ وراستش ۱یا ۰ یا -۱ بشه. , , و اسم درخت شد avl مخفف اول اسم این اقایان
یعنی ارتفاع چپ منهای راست حداکثر یک بشه. به این صورت که به محض اینکه ارتفاع در درجهای متوالی ۲ شد با چرخش یا rotate ارتفاع رو درت ومتوازن میکنن
هزینه چرخش هم چون فقط ۳تا اشاره گر عوض میشه میشه o 1
ببخشد بد نگارش میکنم
اینا چیزایی بود که به ذهنم رسید