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