پیمایش های bst از چه مرتبه ای است؟ همه جا نوشتن O(n) .تو کتاب clrs هم همینطور البته توضیح داده که مثلا برای پیمایش میانترتیب کوچکترین گره رو با tree-Min پیدا میکنیم.بعد n-1 بار Tree-Successor رو فراخوانی میکنیم.
مگه Tree-Successor از مرتبه O(logn) نیست؟ درنتیجه پیمایش bst باید از مرتبه O(nlog) بشه نه O(n) . چونکه n-1 بار Tree-Successor رو فراخوانی کردیم!
در پیمایش مثلا میان ترتیب،کاری که صورت میگیره اینه که یک گره(در اینجا ریشه) تکلیفش معلوم میشه و تابعمون به دو قسمت شکسته میشه و.پس می تونیم بگیم که تابع بازگشتی بصورت زیردارد:
[tex]T(n) = T(k) T(n – k – ۱) c[/tex]
حالا توی حالتهای مختلف تابع بالا را در نظر میگیریم:
حالت اول:یکی از زیر درختها خالی و بقیه در دیگری.
[tex]T(n) = T(0) T(n – ۱) c[/tex]
بصورت بازگشتی که بنویسیم داریم:
[tex]T(n) = (n-1)T(0) T(1) (n-1)c[/tex]
با توجه به اینکه پیمایش یک درخت خالی زمان ثابتی خواهد شد. تابع از مرتبه [tex]O(n)[/tex] خواهد بود.
حالت دوم:دو زیر درخت مساوی.
[tex]T(n) = 2T(\left \lfloor \frac{n}2 \right \rfloor ) c[/tex]
که توی این حالت هم طبق قضیه master تابع از مرتبه [tex]O(n)[/tex] خواهد بود.
ولی روشی که خودتون گفتید:
پیدا کردن مینیمم که [tex]O(n)[/tex] طول میکشه چرا که ممکنه درختمون اریب باشه.Tree-Successor هم همانطور که گفتید از مرتبه [tex]O(lgn)[/tex] هست.ولی الگوریتم مورد نظر خیلی پیچیده‌تر از اینه که شما به این سادگی بهش نگاه کردید و اثبات طولانی دارد.فقط همین رو بگم که ثابت میشه که هر یال درخت در این الگوریتم حداکثر دو بار پیمایش خواهد شد.
الگوریتم succ از مرتبه O(h) هست که در بدترین حالت میشه O(n) و درحالت متوسط میشه O(lgn).و در پیمایش باید کل گره‌ها یعنی بدترین حالت رو در نظر بگیریم.دوستان اگه اشتباه میگم اصلاح کنید.
(۲۹ دى ۱۳۸۹ ۰۴:۱۴ ب.ظ)sal_dovomi نوشته شده توسط: الگوریتم succ از مرتبه O(h) هست که در بدترین حالت میشه O(n) و درحالت متوسط میشه O(lgn).و در پیمایش باید کل گره‌ها یعنی بدترین حالت رو در نظر بگیریم.دوستان اگه اشتباه میگم اصلاح کنید.
منظور من حالت متوسط بود.و می خواستم به صاحب تاپیک بگم که تناقضی توی دانسته هاشون وجود نداره و این الگوریتم پیمایش میان ترتیب(با استفاده از Tree-Min و Tree-Successor) متفاوت می باشد و برای بدست آوردن مرتبه زمانی آن نیز اثبات خاص خودش وجود داره. مگرنه در درخت BST اکثر توابع وابسته به ارتفاع هستند.